foldl是尾递归的，那么为什么foldr比foldl运行得更快？

Question

我想测试foldl和foldr。从我看到的来看，只要可以，应该使用foldl而不是foldr，因为可以进行尾递归优化。

这很有道理。然而，运行这个测试后我感到困惑：

使用time命令时，foldr（需要0.057秒）：

a::a -> [a] -> [a]
a x = ([x] ++ )

main = putStrLn(show ( sum (foldr a [] [0.. 100000])))

使用 time 命令时，foldl 需要 0.089 秒：

b::[b] -> b -> [b]
b xs = ( ++ xs). (\y->[y])

main = putStrLn(show ( sum (foldl b [] [0.. 100000])))

显然，这个例子很简单，但我不明白为什么foldr会比foldl快。难道这不是一个明显的情况，foldl应该胜出吗？

- Ori

---

顺便提一下，我会使用列表构造器把 a 写成 a = (:)。 - John L

我之所以将它写成([x]++)，是为了尽可能让a和b接近，以便尽可能地比较折叠。 - Ori

...并且将 b 定义为 b = flip (:)。 - Will Ness

Answer 1

欢迎来到惰性求值的世界。

当你从严格求值的角度考虑时，foldl看起来“不错”，而foldr看起来“糟糕”，因为foldl是尾递归的，但是foldr必须在堆栈中构建一个塔来首先处理最后一项。

然而，惰性求值扭转了这种情况。以map函数的定义为例：

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

如果 Haskell 使用严格求值，那么这不太好，因为它必须先计算尾部，然后再将项（对于列表中的所有项）前置。似乎唯一有效的方法是以相反的顺序构建元素。

然而，由于 Haskell 的惰性求值，这个 map 函数实际上是高效的。在 Haskell 中，列表可以被认为是生成器，而此 map 函数通过将 f 应用于输入列表的第一个项来生成其第一个项。当它需要第二个项时，它只需重复执行相同的操作即可（而不使用额外的空间）。

事实证明，map 可以用 foldr 来描述：

map f xs = foldr (\x ys -> f x : ys) [] xs

从外观上很难判断，但延迟求值的原因是因为foldr可以立即将第一个参数传递给f：

foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

因为由map定义的f可以仅使用第一个参数返回结果列表的第一项，所以折叠可以在常数空间中进行惰性操作。

现在，惰性求值确实会反噬回来。例如，尝试运行sum [1..1000000]。它会导致堆栈溢出。为什么呢？它应该只是从左到右进行求值，对吧？

让我们看看Haskell如何评估它：

foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

sum = foldl (+) 0

sum [1..1000000] = foldl (+) 0 [1..1000000]
                 = foldl (+) ((+) 0 1) [2..1000000]
                 = foldl (+) ((+) ((+) 0 1) 2) [3..1000000]
                 = foldl (+) ((+) ((+) ((+) 0 1) 2) 3) [4..1000000]
                   ...
                 = (+) ((+) ((+) (...) 999999) 1000000)

Haskell的惰性计算导致它不会在执行加法时得到结果。相反，它最终会得到一堆未求值的表达式序列，需要强制求值才能得到数字。在这个求值过程中出现递归超出栈空间错误，因为它必须要递归深入地求值所有的表达式序列。

幸运的是，Data.List中有一个特殊的函数叫做foldl'，它是严格求值的。用foldl' (+) 0 [1..1000000]就可以避免栈溢出。（注意：我尝试将你的测试中的foldl换成foldl'，但实际上它使得执行速度更慢了。）

- Joey Adams

---

如果您的编译器执行尾递归模合并优化，效率提升的唯一方法似乎是反向构建元素。然后，它就像具有严格数据构造函数的受保护递归一样工作。 - Will Ness

@WillNess： GHC 没有那个优化吗？ - Elliot Cameron

据我所知，@3noch并没有。但它大多数情况下并不适用，因为Haskell是惰性的，并且如我上面暗示的那样，惰性的保护递归等效于它。还有，更正一下：应该是惰性数据构造器，我想：在map f (x:xs) = f x : map f xs中，map的递归由惰性列表构造器:保护。如果:是严格的，就没有保护了，只有普通的递归。我认为这里少了一个逗号：“......然后它的工作原理就像保护递归一样，（即使）使用严格数据构造器”- 如果TRMCO存在的话。 - Will Ness

我有一个疑问..你在上一个foldl的例子中说：“Haskell太懒了，无法继续执行加法，因此会导致堆栈溢出”...我认为foldl需要大量的内存，因为它需要新的thunks，所以会耗尽内存，而不是耗尽堆栈内存..这就是为什么..foldr会立即崩溃，因为堆栈内存比总系统内存小。 - Ashish Negi

@JoeyAdams 评估thunks是否总是在堆栈上发生，还是取决于函数f？例如，在（：）的情况下，它会占用堆栈吗？我的意思是当函数立即需要第一个参数时，它是否会使用堆栈？或者有特殊情况...抱歉，问这个问题，但我真的想了解它。 - Ashish Negi

Answer 2

重新审视这个问题，我认为目前的所有解释都有些不足，因此我写了一个更长的解释。

区别在于foldl和foldr如何应用它们的约简函数。看一下foldr的情况，我们可以将其展开为

foldr (\x -> [x] ++ ) [] [0..10000]
[0] ++ foldr a [] [1..10000]
[0] ++ ([1] ++ foldr a [] [2..10000])
...

这个列表由 sum 处理，它按以下方式消耗它：

sum = foldl' (+) 0
foldl' (+) 0 ([0] ++ ([1] ++ ... ++ [10000]))
foldl' (+) 0 (0 : [1] ++ ... ++ [10000])     -- get head of list from '++' definition
foldl' (+) 0 ([1] ++ [2] ++ ... ++ [10000])  -- add accumulator and head of list
foldl' (+) 0 (1 : [2] ++ ... ++ [10000])
foldl' (+) 1 ([2] ++ ... ++ [10000])
...

我省略了列表连接的细节，但这就是规约过程。重要的部分是为了最小化列表遍历而对所有内容进行处理。foldr仅遍历一次列表，连接操作不需要连续的列表遍历，并且sum最终以一次遍历消耗列表。关键是，foldr立即将列表头传递给sum，因此sum可以立即开始工作，并且在生成值时可以进行垃圾回收。使用类似于vector的融合框架，甚至中间列表也可能被融合掉。

与此相比，foldl函数如下：

b xs = ( ++xs) . (\y->[y])
foldl b [] [0..10000]
foldl b ( [0] ++ [] ) [1..10000]
foldl b ( [1] ++ ([0] ++ []) ) [2..10000]
foldl b ( [2] ++ ([1] ++ ([0] ++ [])) ) [3..10000]
...

请注意，现在列表的头部直到foldl完成后才可用。这意味着整个列表必须在sum开始工作之前被构造在内存中。总体效率要低得多。使用+ RTS-s运行两个版本将显示从foldl版本的悲惨垃圾收集表现。

这也是foldl'无法帮助的情况。 foldl'的额外严格性不会改变中间列表创建的方式。列表的头仍然无法使用，直到foldl'完成，因此结果仍然比foldr慢。

我使用以下规则来确定最佳的fold选择：

• 对于是reduction的折叠，使用foldl'（例如，这将是唯一/最终遍历）
• 否则，请使用foldr。
• 不要使用foldl。

在大多数情况下，由于其遍历方向对于列表的惰性评估是最优的，因此foldr是最好的折叠函数。它还是唯一能够处理无限列表的函数。 foldl'的额外严格性可以使其在某些情况下更快，但这取决于您将如何使用该结构以及它的惰性程度。

- John L

---

不幸的是，sum使用的是foldl而不是foldl'（除非他们最近修复了这个问题）。 - Joey Adams

我的想法有些一厢情愿。但这个论点仍然成立；你只需要用一个巨大的thunk替换累加器。 - John L

foldl1' (+) [1..100000000] 几乎瞬间完成，而所有其他的 folds 要花费几秒钟或者导致堆栈溢出。 - Mateen Ulhaq

Answer 3

我认为到目前为止没有人说出真正的答案，除非我漏掉了什么（这可能是真的并且会受到负评的欢迎）。

我认为在这种情况下最大的不同之处在于foldr像这样构建列表:

[0] ++ ([1] ++ ([2] ++ (... ++ [1000000])))

而foldl像这样构建列表:

((([0] ++ [1]) ++ [2]) ++ ... ) ++ [999888]) ++ [999999]) ++ [1000000]

细微的区别在于，在foldr版本中，++的左参数始终只有一个列表元素。对于foldl版本，++的左参数中最多有999999个元素（平均约为500000），但是右参数只有一个元素。

但是，++所需的时间与左参数的大小成比例，因为它必须查看整个左参数列表直到末尾，然后将最后一个元素指向右参数的第一个元素（在最好的情况下，可能实际上需要进行复制）。右参数列表没有更改，因此它的大小无关紧要。

这就是为什么foldl版本要慢得多的原因。在我看来，这与惰性无关。

- Clinton

---

foldr对于操作来说所需的时间更少了。 - Ashish Negi

@Clinton 有道理。但是你的回答只解释了 OP 的具体示例，还是讲解了 foldl 和 foldr 之间的一般区别？对我来说，OP选择了一个不好的例子开始，因为这两个折叠函数差异很大。 - dhu

Answer 4

问题在于尾递归优化是一种内存优化，而非执行时间优化！

尾递归优化避免了需要为每个递归调用记住值的需求。

因此，foldl实际上是"好的"，而foldr是"糟糕的"。

例如，考虑foldr和foldl的定义：

foldl f z [] = z
foldl f z (x:xs) = foldl f (z `f` x) xs

foldr f z [] = z
foldr f z (x:xs) = x `f` (foldr f z xs)

这就是表达式“foldl (+) 0 [1,2,3]”的计算方式：

foldl (+) 0 [1, 2, 3]
foldl (+) (0+1) [2, 3]
foldl (+) ((0+1)+2) [3]
foldl (+) (((0+1)+2)+3) [ ]
(((0+1)+2)+3)
((1+2)+3)
(3+3)
6

请注意，foldl不会记住值0、1、2…，而是将整个表达式(((0+1)+2)+3)作为参数进行惰性传递，并且直到最后一次foldl的评估才对其进行评估，在此时它达到基本情况并返回传递的第二个参数(z)的值，该值尚未被评估。

另一方面，这就是foldr的工作方式：

foldr (+) 0 [1, 2, 3]
1 + (foldr (+) 0 [2, 3])
1 + (2 + (foldr (+) 0 [3]))
1 + (2 + (3 + (foldr (+) 0 [])))
1 + (2 + (3 + 0)))
1 + (2 + 3)
1 + 5
6

这里的重要区别在于，foldl在最后一次调用时评估整个表达式，避免了需要回到记住的值的需求，而foldr则不同。foldr为每个调用记住一个整数，并在每个调用中执行加法。

需要记住的是，foldr和foldl并不总是等价的。例如，在hugs中尝试计算这些表达式：

foldr (&&) True (False:(repeat True))

foldl (&&) True (False:(repeat True))

在特定条件下，foldr和foldl是等价的，这些条件在这里进行了描述。

（对不起我的英语不太好）

- matiascelasco

Answer 5

对于a，需要立即扩展[0.. 100000]列表，以便foldr可以从最后一个元素开始。然后，随着它将东西折叠在一起，中间结果会逐步出现。

[100000]
[99999, 100000]
[99998, 99999, 100000]
...
[0.. 100000] -- i.e., the original list

因为没有人被允许改变这个列表的值（Haskell是一种纯函数式语言），编译器可以自由地重用这个值。中间值，比如[99999, 100000]甚至可以简单地成为扩展的[0.. 100000]列表的指针，而不是单独的列表。

对于b，看看中间值：

[0]
[0, 1]
[0, 1, 2]
...
[0, 1, ..., 99999]
[0.. 100000]

每个中间列表都不能被重复使用，因为如果你改变了列表的结尾，那么指向它的任何其他值也会发生改变。因此，你创建了一堆额外的列表，这需要花费时间来构建内存。在这种情况下，你花费更多的时间来分配和填充这些中间值的列表。

由于你只是复制列表，所以 A函数比B函数更快，因为它首先扩展完整列表，然后只需从列表的末尾向前移动指针即可。

- Harold L

Answer 6

foldl和foldr都没有进行尾部优化。只有foldl'进行了优化。

但在您的情况下，使用++与foldl'不是一个好主意，因为++的连续评估将会再次遍历增长的累加器。

- Hynek -Pichi- Vychodil

Answer 7

好的，让我用一种明显不同的方式重新编写您的函数 -

a :: a -> [a] -> [a]
a = (:)

b :: [b] -> b -> [b]
b = flip (:)

你可以看到 b 比 a 更复杂。如果你想要精确计算，a 需要进行一次约简才能计算出值，但是 b 需要进行两次。这就导致了你所测量的时间差异，在第二个例子中必须执行两倍的约简操作。

//编辑：但是时间复杂度是相同的，所以我不会过于担心它。

- Martin Jonáš

---

我尝试将它改成a = flip $ flip (:)，但它并没有明显改变执行时间，所以我认为翻转参数来适应foldl不是问题所在。 - Harold L