foldr与foldl(或foldl')的含义是什么?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (18)

foldr与foldl(或foldl')的含义是什么?

提问于
用户回答回答于

递归的foldr f x ys地方ys = [y1,y2,...,yk]看起来像

f y1 (f y2 (... (f yk x) ...))

而递归foldl f x ys看起来像

f (... (f (f x y1) y2) ...) yk

这里的一个重要区别是,如果f x y只能使用值的计算结果x,则foldr不需要检查整个列表。例如

foldr (&&) False (repeat False)

返回,False

foldl (&&) False (repeat False)

永不终止。(注:repeat False创建一个无限列表,每个元素都是False。)

另一方面,foldl'是尾递归和严格的。如果你知道你不得不遍历整个列表(例如,将列表中的数字相加),那么foldl'更多的空间(可能是时间)比foldr

用户回答回答于

扫码关注云+社区