Differences between foldl and foldr

Differences between foldl and foldr Alexis King | September 25, 2026 | [Deep Dives]

foldl 和 foldr 之间的区别 Alexis King | 2026年9月25日 | [深度解析]

Editor’s note: This article is a reproduction of a seminal explanation of the differences between foldr and foldl, both strict and lazy versions. As it has been used consistently to teach newcomers since its first appearance on hasura/graphql-engine!2933 on the 26th September 2019, we believe that it ought to be preserved in the blog. Our many thanks to Alexis King for giving her permission to do so.

编者按：本文转载自一篇关于 foldr 和 foldl（包括严格和惰性版本）区别的开创性解释。自 2019 年 9 月 26 日首次出现在 hasura/graphql-engine!2933 上以来，它一直被用于指导新手，我们认为有必要将其保留在博客中。非常感谢 Alexis King 授权我们转载。

To start, you have to understand that foldl and foldr are not folds “from the left” and “from the right.” Both foldl and foldr traverse the structure in the same order, which in the case of lists means left to right. The difference is the fold’s associativity.

首先，你必须明白 foldl 和 foldr 并不是所谓的“从左折叠”和“从右折叠”。foldl 和 foldr 遍历结构的顺序是相同的，对于列表而言，都是从左到右。它们的区别在于折叠的结合性（associativity）。

foldl vs foldr illustrated

foldl 与 foldr 图解

The best way to think about this is with an illustration. When you write foldl (⨂) v [e0, e1, e2, ..., en−1, en] you’re performing the following computation: (... (((v ⨂ e0) ⨂ e1) ⨂ e2) ⨂ ... ⨂ en−1) ⨂ en

理解这一点的最好方法是通过图解。当你编写 foldl (⨂) v [e0, e1, e2, ..., en−1, en] 时，你执行的是以下计算： (... (((v ⨂ e0) ⨂ e1) ⨂ e2) ⨂ ... ⨂ en−1) ⨂ en

In contrast, when you write foldr (⨂) v [e0, e1, e2, ..., en−1, en] you’re performing this computation: e0 ⨂ (e1 ⨂ (e2 ⨂ ... ⨂ (en−1 ⨂ (en ⨂ v)) ... ))

相比之下，当你编写 foldr (⨂) v [e0, e1, e2, ..., en−1, en] 时，你执行的是以下计算： e0 ⨂ (e1 ⨂ (e2 ⨂ ... ⨂ (en−1 ⨂ (en ⨂ v)) ... ))

See the difference? In both expressions, the elements of the list appear in the expression in the same order—from left to right—but the grouping changes. With foldl, the applications of (⨂) are left-associated, while with foldr, they’re right-associated.

看出区别了吗？在这两个表达式中，列表元素出现的顺序相同——都是从左到右——但分组方式发生了变化。对于 foldl，(⨂) 的应用是左结合的；而对于 foldr，它们是右结合的。

foldl vs. foldr, strictly

严格模式下的 foldl 与 foldr

The question is: how does this difference actually impact the behavior of a program? Well, let’s start by first thinking about what the difference would be in a strict language. In a strict language, evaluation order always proceeds from the “inside out,” starting with the most deeply nested expression.

问题是：这种差异实际上如何影响程序的行为？好吧，让我们先思考一下在严格语言中会有什么不同。在严格语言中，求值顺序总是从“由内而外”进行，从嵌套最深的表达式开始。

Let’s think about that in the context of foldl first. Let’s say we wrote this expression: foldl (+) 0 [1, 2, 3, 4] By the above illustration, we know that expression is equivalent to this one: (((0 + 1) + 2) + 3) + 4

让我们先在 foldl 的语境下思考。假设我们写了这样一个表达式：foldl (+) 0 [1, 2, 3, 4] 根据上面的图解，我们知道该表达式等同于：(((0 + 1) + 2) + 3) + 4

Reducing from the inside out, we get the following reduction sequence: foldl (+) 0 [1, 2, 3, 4] = (((0 + 1) + 2) + 3) + 4 = (( 1 + 2) + 3) + 4 = ( 3 + 3) + 4 = 6 + 4 = 10

从内向外归约，我们得到以下归约序列： foldl (+) 0 [1, 2, 3, 4] = (((0 + 1) + 2) + 3) + 4 = (( 1 + 2) + 3) + 4 = ( 3 + 3) + 4 = 6 + 4 = 10

In contrast, if we had used foldr, we’d get the same result (since (+) is an associative, commutative operation), but with a slightly different reduction sequence: foldr (+) 0 [1, 2, 3, 4] = 1 + (2 + (3 + (4 + 0))) = 1 + (2 + (3 + 4 )) = 1 + (2 + 7 ) = 1 + 9 = 10

相比之下，如果我们使用 foldr，也会得到相同的结果（因为 (+) 是结合且交换的运算），但归约序列略有不同： foldr (+) 0 [1, 2, 3, 4] = 1 + (2 + (3 + (4 + 0))) = 1 + (2 + (3 + 4 )) = 1 + (2 + 7 ) = 1 + 9 = 10

What’s the practical difference between these two things? Well, note the following detail: with foldl, to start reducing, we only need the first element of the list, but with foldr, we have to start from the end of the list and reduce “backwards.” Practically, this means foldl can be tail-recursive, reducing as it traverses the list in constant space, while foldr cannot be: to reduce a list of length n with foldr, you need to create n stack frames before any reduction can start.

这两者在实际中有什么区别？请注意以下细节：使用 foldl 时，开始归约只需要列表的第一个元素；而使用 foldr 时，必须从列表末尾开始“向后”归约。实际上，这意味着 foldl 可以是尾递归的，在遍历列表时以常数空间进行归约，而 foldr 则不行：要用 foldr 归约一个长度为 n 的列表，在任何归约开始之前，你需要创建 n 个栈帧。

foldl, lazily

惰性模式下的 foldl

But what about in lazy languages, like Haskell? In a lazy language, evaluation order doesn’t proceed from the “inside out” like it does in strict languages, but rather from the “outside in,” evaluating expressions only as their results are demanded.

那么在像 Haskell 这样的惰性语言中呢？在惰性语言中，求值顺序不像严格语言那样“由内而外”，而是“由外而内”，仅在需要结果时才对表达式求值。

In a strict language, foldl (+) 0 [1, 2, 3, 4] doesn’t actually get turned into the expression (((0 + 1) + 2) + 3) + 4; as I mentioned earlier, it’s implemented as a tail-recursive loop. But in Haskell, it basically does get expanded into that expression before any reduction starts—each application of (+) is lazily suspended in a thunk.

在严格语言中，foldl (+) 0 [1, 2, 3, 4] 实际上并不会变成表达式 (((0 + 1) + 2) + 3) + 4；正如我之前提到的，它是作为尾递归循环实现的。但在 Haskell 中，它在任何归约开始前确实会被展开成那个表达式——每一个 (+) 的应用都被惰性地挂起在一个 thunk（惰性求值对象）中。

If we explicitly denote thunks with ⟨⟩ brackets, the thunk we’ll end up with looks like this: ⟨⟨⟨⟨0 + 1⟩ + 2⟩ + 3⟩ + 4⟩

如果我们用 ⟨⟩ 括号显式表示 thunk，最终得到的 thunk 看起来像这样：⟨⟨⟨⟨0 + 1⟩ + 2⟩ + 3⟩ + 4⟩

These thunks will only get forced when the outermost thunk is evaluated, which will cause (+) to be applied to the arguments ⟨⟨⟨0 + 1⟩ + 2⟩ + 3⟩ and 4. Since (+) is strict in both its arguments, it will force the next thunk, which will in turn apply (+) to ⟨⟨0 + 1⟩ + 2⟩ and 3, and so on until the whole thunk tree is reduced.

这些 thunk 只有在最外层的 thunk 被求值时才会被强制执行，这将导致 (+) 被应用于参数 ⟨⟨⟨0 + 1⟩ + 2⟩ + 3⟩ 和 4。由于 (+) 对其两个参数都是严格的，它会强制执行下一个 thunk，进而将 (+) 应用于 ⟨⟨0 + 1⟩ + 2⟩ 和 3，依此类推，直到整个 thunk 树被归约。

The result ends up being the same, but from a practical point of view, this is really bad, because instead of reducing the list in constant space, like we did in the strict language, we’re now creating a thunk linear in the size of the input list!

结果虽然相同，但从实际角度来看，这非常糟糕，因为我们没有像在严格语言中那样以常数空间归约列表，而是创建了一个与输入列表大小成线性关系的 thunk！

By using the lazy foldl, we’ve possibly gone from a constant-space algorithm to a linear-space algorithm, which is bad! What we want is to recover the behavior of the strict language’s foldl, efficiently updating an accumulator as we traverse the list, not building thunks. Therefore, we need a stricter version of foldl, which is exactly what foldl' is.

通过使用惰性 foldl，我们可能已经从常数空间算法变成了线性空间算法，这很糟糕！我们想要的是恢复严格语言中 foldl 的行为，在遍历列表时高效更新累加器，而不是构建 thunk。因此，我们需要一个更严格的 foldl 版本，这正是 foldl' 的作用。

foldl' places a demand on the ⟨0 + 1⟩ thunk before moving onto the next element of the list, so instead of building a larger ⟨⟨0 + 1⟩ + 2⟩ thunk, it simply builds a ⟨1 + 2⟩ thunk. foldl' continues traversing the list in constant space, never building a thunk larger than a single application of (+).

foldl' 在移动到列表的下一个元素之前，会对 ⟨0 + 1⟩ thunk 提出求值需求，因此它不会构建更大的 ⟨⟨0 + 1⟩ + 2⟩ thunk，而是简单地构建一个 ⟨1 + 2⟩ thunk。foldl' 继续以常数空间遍历列表，永远不会构建比单个 (+) 应用更大的 thunk。

foldr, lazily

惰性模式下的 foldr

But what about foldr? Remember that in a strict language, foldr already needed to consume space linear in the size of the input list, since it fundamentally needed the last element in the list before it could start reducing. Indeed, if we consider a lazy foldr with a strict operation like (+), this is still true—but in an interestingly different way from foldl.

那么 foldr 呢？请记住，在严格语言中，foldr 本身就需要消耗与输入列表大小成线性关系的空间，因为它从根本上需要列表中的最后一个元素才能开始归约。事实上，如果我们考虑带有像 (+) 这样严格运算的惰性 foldr，情况依然如此——但它与 foldl 的方式有着有趣的差异。