Foldr 与 Foldl（或 Foldl'）的含义

Question

首先，我正在阅读的Real World Haskell说永远不要使用foldl，而是使用foldl'。 所以我相信它。

但我不清楚何时使用 foldr 和 foldl'。 尽管我可以看到它们以不同方式工作的结构摆在我面前，但我太愚蠢了，无法理解什么时候“哪个更好”。 我想在我看来，使用哪个并不重要，因为它们都会产生相同的答案（不是吗？）。 事实上，我之前对这个构造的经验来自Ruby的inject和Clojure的reduce，它们似乎没有“左”和“右”版本。 （附带问题：他们使用哪个版本？）

任何可以帮助像我这样的聪明人的见解将不胜感激！

Answer 1

foldr fx ys 的递归，其中 ys = [y1,y2,...,yk] 看起来像，

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

而 foldl fx ys 的递归看起来

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

这里的一个重要区别是，如果可以仅使用 x 的值来计算 fx y 的结果，那么 foldr 则不能' 需要检查整个列表。 例如，

foldr (&&) False (repeat False)

返回 False 而

foldl (&&) False (repeat False)

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

另一方面，foldl' 是尾递归且严格的。 如果您知道无论如何都必须遍历整个列表（例如，对列表中的数字求和），那么 foldl' 比 foldl' 具有更高的空间（可能还有时间）效率。代码>文件夹。

Answer 2

foldr 看起来像这样：

foldl 看起来像这个：

上下文：折叠

Answer 3

它们的语义不同，因此您不能简单地互换 foldl 和 foldr。 一个从左侧向上折叠元素，另一个从右侧向上折叠。 这样，运算符就会以不同的顺序应用。 这对于所有非关联运算（例如减法）都很重要。

Haskell.org 有一个有趣的 。

Answer 4

不久之后，当累加器函数对其第二个参数惰性时，foldr 会更好。 阅读 Haskell wiki 的 Stack Overflow（双关语）了解更多信息。

Answer 5

在 99% 的所有用途中，foldl' 优于 foldl 的原因是，对于大多数用途，它可以在恒定空间中运行。

采用函数 sum = Foldl['] (+) 0。 当使用 foldl' 时，会立即计算总和，因此将 sum 应用于无限列表将永远运行，并且很可能在恒定空间中（如果您使用如果数字是 Int、Double、Float 等，那么 Integer 将使用比常量更大的空间。变得大于 maxBound :: Int ）。

使用foldl，构建了一个thunk（就像如何获取答案的秘诀，可以稍后对其进行评估，而不是存储答案）。 这些 thunk 可能会占用大量空间，在这种情况下，评估表达式比存储 thunk 要好得多（导致堆栈溢出......并导致你......哦没关系）

希望有所帮助。

Answer 6

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

Answer 7

正如 Konrad 指出的，它们的语义是不同的。 它们甚至没有相同的类型：

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

例如，列表追加运算符 (++) 可以使用 foldr 实现，因为

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

while

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

会给出类型错误。