`foldl` 与 `foldr` 的区别
编者注：这篇文章是重新发布一篇解释 foldr 与 foldl 区别的经典文章，涵盖严格与惰性两种版本。自其 2019 年 9 月 26 日首次出现在 hasura/graphql-engine!2933 以来，它一直被用于向初学者讲解相关知识，我们认为有必要将其保存在博客中。感谢 Alexis King 允许我们这么做。
首先，你需要明白，foldl 和 foldr 并不是“从左”或“从右”的折叠。两者遍历结构的顺序相同，对于列表而言，这意味着从左到右。它们的区别在于折叠的结合性。
图解 foldl 与 foldr
理解这一点最好的方式是看图。当你写出
foldl (⨂) v [e0, e1, e2, ..., en−1, en]你执行的是以下计算：
( ... (((v ⨂ e0) ⨂ e1) ⨂ e2) ⨂ ... ⨂ en−1) ⨂ en相比之下，当你写出
foldr (⨂) v [e0, e1, e2, ..., en−1, en]你执行的是这个计算：
e0 ⨂ (e1 ⨂ (e2 ⨂ ... ⨂ (en−1 ⨂ (en ⨂ v)) ... ))看出区别了吗？在这两个表达式中，列表元素在表达式中的出现顺序相同——都是从左到右——但分组方式改变了。在 foldl 中，(⨂) 的应用是左结合的，而在 foldr 中，它们是右结合的。
严格模式下的 foldl 与 foldr
问题是：这种区别实际上如何影响程序的行为？首先，让我们思考在严格语言中这种区别是什么。在严格语言中，求值顺序总是从“内部到外部”，从嵌套最深层的表达式开始。
让我们先在 foldl 的语境下思考这一点。假设我们写出了这个表达式：
foldl (+) 0 [1, 2, 3, 4]从上面的推导可以看出，该表达式等价于：
(((0 + 1) + 2) + 3) + 4由内向外化简，得到如下化简序列：
foldl (+) 0 [1, 2, 3, 4]
= (((0 + 1) + 2) + 3) + 4
= (( 1 + 2) + 3) + 4
= ( 3 + 3) + 4
= 6 + 4
= 10反之，如果改用 foldr，由于 (+) 满足结合律和交换律，结果相同，但化简序列略有不同：
foldr (+) 0 [1, 2, 3, 4]
= 1 + (2 + (3 + (4 + 0)))
= 1 + (2 + (3 + 4 ))
= 1 + (2 + 7 )
= 1 + 9
= 10这两者在实际应用上的区别是什么？注意一个细节：使用 foldl 时，只需列表的第一个元素即可开始化简；而使用 foldr 时，必须从列表的末尾开始，以“逆向”方式化简。1 这意味着 foldl 可以采用尾递归实现，在遍历列表时以常数空间完成化简；而 foldr 则不行：要对长度为 n 的列表执行 foldr，在化简开始之前，需要生成 n 个栈帧。
1 这就是为什么 foldr 有时被描述为“从右向左折叠”，尽管它实际上是从左向右遍历列表的。不过正如我们稍后会看到的，这一点在惰性语言中并不成立！
foldl 的惰性求值
那在 Haskell 等惰性语言中又是怎么回事呢？在惰性语言中，求值顺序不像严格语言那样“由内向外”，而是“由外向内”，仅当结果被需要时才对表达式求值。
在严格语言中，foldl (+) 0 [1, 2, 3, 4] 并不会真正转化为表达式 (((0 + 1) + 2) + 3) + 4；如前所述，它被实现为尾递归循环。但在 Haskell 中，在化简开始前，它基本上会被展开为那个表达式——每次 (+) 的应用都会惰性挂起在一个 thunk 中。
如果我们用 ⟨⟩ 括号显式表示 thunk，最终得到的 thunk 看起来是这样的：
⟨⟨⟨⟨0 + 1⟩ + 2⟩ + 3⟩ + 4⟩这些 thunk 只有在最外层的 thunk 被求值时才会被强制计算，这会让 (+) 作用于 ⟨⟨⟨0 + 1⟩ + 2⟩ + 3⟩ 和 4。由于 (+) 对两个参数都是严格的，它会接着强制计算下一个 thunk，也就是把 (+) 作用到 ⟨⟨0 + 1⟩ + 2⟩ 和 3 上，如此递归下去，直到整棵 thunk 树都被化简完毕。
最终结果是一样的，但从实际角度看，这非常糟糕：在严格语言里我们能以常数空间化简列表，而现在却创建了与输入列表长度成正比的 thunk！更糟的是，在严格语言中，输入列表占用的空间本来就与其自身大小成正比，所以产出/消费列表的整体空间消耗只是多了一个常数因子；但在惰性语言里，列表更像一个流（stream），如果整个流没有被完全物化到内存中，实际可能只占用常数空间。而使用了惰性的 foldl 之后，我们可能把一个常数空间算法变成了线性空间算法，这就很糟糕了。
我们想要的是恢复严格语言中 foldl 的行为：在遍历列表时高效地更新累加器，而不是不断构建 thunk。因此，我们需要一个更严格的 foldl 版本——这正是 foldl' 存在的意义。foldl' 在处理列表下一个元素之前，会先强制求值 ⟨0 + 1⟩ 这个 thunk，所以它构建的不是更大的 ⟨⟨0 + 1⟩ + 2⟩，而只是 ⟨1 + 2⟩。这样 foldl' 就能以常数空间遍历列表，构建的 thunk 永远不会超过一次 (+) 调用的大小。
惰性求值下的 foldr
那 foldr 呢？别忘了，在严格语言中，foldr 本来就需要与输入列表大小成正比的空间，因为它必须拿到列表的最后一个元素才能开始化简。事实上，如果把惰性的 foldr 与 (+) 这样的严格操作结合使用，结论依然成立——只是其表现形式与 foldl 截然不同，而且很有意思。
使用 foldl 时，我们在遍历列表的过程中不断累积 thunk，最终形成一个巨大且层层嵌套的 thunk。但用 foldr 就不会这样。为什么？再看一下展开过程：
foldr (+) 0 [1, 2, 3, 4]
= 1 + (2 + (3 + (4 + 0)))为了弄清这个展开是怎么来的，我们用显式的归纳方式把它写出来：
foldr (+) 0 [1, 2, 3, 4]
= 1 + foldr (+) 0 [2, 3, 4]
= 1 + (2 + foldr (+) 0 [3, 4])
= 1 + (2 + (3 + foldr (+) 0 [4]))
= 1 + (2 + (3 + (4 + foldr (+) 0 [])))
= 1 + (2 + (3 + (4 + 0)))这样 foldr 的递归调用就更清楚了。在严格求值的语言里，一旦调用 foldr，就必须立刻拿到结果，所以不得不遍历整个列表。但在惰性语言里，事情就有意思了——我们可以直接返回下面这个带挂起 thunk 的结果：
foldr (+) 0 [1, 2, 3, 4]
= 1 + ⟨foldr (+) 0 [2, 3, 4]⟩这看似没什么用：一旦强制求值这个结果，(+) 就会强制求值 ⟨foldr (+) 0 [2, 3, 4]⟩，最终得到的归约序列和之前一样。但注意，这只在 (+) 是严格操作的前提下成立。如果换成惰性操作，比如 (:)，会怎样？这时展开结果是：
foldr (:) [] [1, 2, 3, 4]
= 1 : ⟨foldr (:) [] [2, 3, 4]⟩你猜怎么着？这个结果已经处于 weak-head normal form（WHNF） 了！求值到此为止，除非其他地方显式要求剩余部分，否则不会再继续。当然，这个例子有点无聊，因为 foldr (:) [] 不过是列表的恒等函数换了个花哨写法。但可以想象一个稍微复杂点的函数，比如把列表中每个元素翻倍：
let f x xs = (x * 2) : xs
in foldr f [] [1, 2, 3, 4]它会展开成：
foldr f [] [1, 2, 3, 4]
= ⟨1 * 2⟩ : ⟨foldr f [] [2, 3, 4]⟩同样会停在这里，因为已经是 WHNF 了。这有什么用呢？想想看，如果我们并不需要完整的结果列表，比如只取前两个元素：
sum (take 2 (foldr f [] [1, 2, 3, 4]))由于 take 2 只会返回列表的前两个元素，当 sum 强制求值该列表并将其中的数值相加时，它甚至不会去评估 thunk ⟨foldr f [] [3, 4]⟩，列表也只会部分遍历。
这意味着什么？简单来说，如果归约函数对第二个参数是惰性求值，且结果列表未被完全消费，foldr 就能节省不必要的计算。事实上，foldr 可以利用这种特性处理无限列表，而 foldl 做不到。此外，foldr 通常比 foldl 更容易应用列表融合（list fusion），不过这是另一个话题了。
惰性视角下的 foldl 与 foldr
好的，简单回顾一下我前面的观点：
-
在惰性语言中，对列表使用
foldl是个坏主意，因为它太懒了，会累积大量的 thunk。应改用foldl'来逐步强制求值 thunk，从而以恒定空间消费列表。 -
在惰性语言中，对列表使用
foldr是好的，因为它具备惰性，如果归约函数对第二个参数是惰性求值，它就能节省计算量。
这两点看起来可能有点矛盾。为什么 foldl 因太懒而被视为不好，而 foldr 因惰性却被视为好呢？
为了理解其中的区别，让我们像之前处理 foldr 那样，对 foldl 进行归纳展开：
foldl (+) 0 [1, 2, 3, 4]
= foldl (+) (0 + 1) [2, 3, 4]
= foldl (+) ((0 + 1) + 2) [3, 4]
= foldl (+) (((0 + 1) + 2) + 3) [4]
= foldl (+) ((((0 + 1) + 2) + 3) + 4) []
= ((((0 + 1) + 2) + 3) + 4)看出区别了吗？在 foldr 中，递归调用被推到了结果表达式树的“叶子”节点；而在 foldl 中，递归调用始终位于树的根节点。顺便说一下，这正是 foldl 具备尾递归的原因——这正是尾递归的定义！——但也意味着它绝不可能表现出惰性，因为它永远无法……