Foldr 与 foldl (或 foldl’)的含义

首先，我正在读的 真实世界 Haskell说永远不要使用 foldl而是使用 foldl'，所以我相信它。

但是我不清楚什么时候使用 foldr和 foldl'。虽然我可以看到它们如何以不同的方式摆在我面前，但是我太笨了，无法理解什么时候“哪个更好”我想在我看来，用哪个答案并不重要，因为它们都会得出相同的答案(不是吗?).事实上，我以前使用这个构造的经验来自 Ruby 的 inject和 Clojure 的 reduce，它们似乎没有“左”和“右”版本。(附带问题: 他们使用哪个版本?)

任何能够帮助像我这样缺乏智慧的人的见解都是非常感激的！

41158 次浏览
小开

它们的语义不同，所以不能只交换 foldl和 foldr。一个把元素从左边折叠起来，另一个从右边折叠起来。这样，操作符将以不同的顺序应用。这对于所有非关联运算都很重要，比如减法运算。

Haskell.org 有一个关于这个主题的有趣的 文章。

小开

简而言之，当累加器函数的第二个参数是惰性的时候，foldr更好。阅读更多哈斯克尔 wiki 的 堆栈溢出(双关语)。

小开
最佳答案

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

这里的一个重要区别是，如果只能使用 x的值来计算 f x y的结果，那么 foldr就不需要检查整个列表。比如说

foldr (&&) False (repeat False)

返回 False，而

foldl (&&) False (repeat False)

永远不会终止。(注意: repeat False创建一个无限列表，其中每个元素都是 False。)

另一方面，foldl'是尾递归和严格的。如果您知道无论如何都要遍历整个列表(例如，对列表中的数字求和) ，那么 foldl'比 foldr的空间(可能还有时间)效率更高。

小开

foldl'在99% 的使用中优于 foldl的原因是，在大多数情况下，它可以在常量空间中运行。

以函数 sum = foldl['] (+) 0为例。当使用 foldl'时，总和会立即被计算出来，因此将 sum应用于无限列表将永远运行下去，并且很可能在常量空间中运行(如果您使用的是诸如 Ints、 Doubles、 Floats 之类的东西)。如果数字大于 maxBound :: Int，则 Integer将使用比常量空间更多的空间)。

使用 foldl，可以构建一个 thunk (类似于如何得到答案的配方，可以在以后进行计算，而不是存储答案)。这些 thunk 可能会占用很多空间，在这种情况下，评估表达式比存储 thunk 要好得多(导致堆栈溢出 & hellip; 并导致 & hellip; 哦，没关系)

希望能帮上忙。

小开

顺便说一下，Ruby 的 inject和 Clojure 的 reduce是 foldl(或 foldl1，取决于您使用的版本)。通常，当一种语言中只有一种形式时，它是左折的，包括 Python 的 reduce、 Perl 的 List::Util::reduce、 C + + 的 accumulate、 C # 的 Aggregate、 Smalltalk 的 inject:into:、 PHP 的 array_reduce、 Mathematica 的 reduce0等等。Common Lisp 的 reduce默认为左折叠，但是有一个右折叠的选项。

小开

康拉德指出，它们的语义是不同的，它们甚至没有相同的类型:

ghci> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
ghci> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
ghci>

例如，列表追加操作符(+ +)可以用 foldr作为

(++) = flip (foldr (:))

同时

(++) = flip (foldl (:))

会给你一个类型错误。

小开

foldr是这样的:

Right-fold visualization

foldl是这样的:

Left-fold visualization

背景: Haskell wiki 上的 弃牌


提交答案