foldl和foldr在处理无限列表时的行为差异

Question

这个问题中的myAny函数使用了foldr。当谓词满足时，它停止处理无限列表。

我用foldl重写了它：

myAny :: (a -> Bool) -> [a] -> Bool
myAny p list = foldl step False list
   where
      step acc item = p item || acc

请注意，step函数的参数被正确地颠倒了。

然而，它不再停止处理无限列表。

我尝试按照Apocalisp的答案追踪函数的执行：

myAny even [1..]
foldl step False [1..]
step (foldl step False [2..]) 1
even 1 || (foldl step False [2..])
False  || (foldl step False [2..])
foldl step False [2..]
step (foldl step False [3..]) 2
even 2 || (foldl step False [3..])
True   || (foldl step False [3..])
True

然而，这不是函数的行为方式。这有什么问题吗？

- titaniumdecoy

Answer 1

fold的区别似乎是常见的困惑源，下面是一个更一般性的概述:

考虑用某个函数f和种子z来折叠一个包含n个值的列表[x1, x2, x3, x4 ... xn ]。

foldl是:

• 左关联: f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• 尾递归: 它迭代整个列表，产生最终的值
• 惰性求值: 直到需要结果时才进行计算
• 反向: foldl (flip (:)) []将翻转一个列表。

foldr是:

• 右关联: f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
• 递归到参数中: 每次迭代将f应用于下一个值和剩余列表的折叠结果。
• 惰性求值: 直到需要结果时才进行计算
• 正向: foldr (:) []返回一个未改变的列表。

这里有一个微妙的点，有时会让人犯错：因为foldl是反向的，每个f的应用都添加到结果的外部；而且因为它是惰性的，在需要结果之前不会评估任何东西。这意味着要计算结果的任何部分，Haskell首先迭代整个列表构造一种嵌套函数应用的表达式，然后评估最外层的函数并根据需要评估其参数。如果f总是使用第一个参数，则这意味着Haskell必须递归到最内部的项，然后向后计算每个f的应用。

显然，这与大多数函数式程序员所知道和喜爱的高效尾递归相去甚远！

事实上，即使foldl在技术上是尾递归的，因为在评估任何内容之前构建了整个结果表达式，foldl可能导致堆栈溢出！ 另一方面，请考虑foldr。它也是惰性的，但由于它是正向的，每个f的应用都添加到结果的内部。因此，为了计算结果，Haskell构造了一个单个函数应用程序，其第二个参数是折叠列表的其余部分。如果f对其第二个参数惰性--例如数据构造器，则结果将逐步惰性，每个折叠步骤仅在需要评估其部分的某些结果时计算。

因此我们可以看出为什么有时foldr适用于无限列表而foldl不行：前者可以惰性地将一个无限列表转换为另一个惰性的无限数据结构，而后者必须检查整个列表才能生成任何部分结果。然而，使用需要立即使用两个参数的函数（例如(+)）的foldr与foldl非常相似（或者说，不工作），在评估之前构建一个巨大的表达式。

因此，需要注意的两个重要点是：

• foldr可以将一个惰性递归数据结构转换为另一个。
• 否则，惰性折叠将在大型或无限列表上崩溃并导致堆栈溢出。

您可能已经注意到这听起来像foldr可以做任何foldl可以做的事情，再加上更多。这是真的！实际上，foldl几乎没什么用处！

但是，如果我们想通过对一个大型（但不是无限的）列表进行折叠来产生非惰性结果呢？ 对此，我们需要一个严格的折叠，标准库提供了这个功能：

foldl'是：

• 左关联：f（...（f（f（f（f z x1）x2）x3）x4）...）xn
• 尾递归：它遍历列表并在之后产生值
• 严格：每个函数应用都会在过程中被求值
• 反向：foldl'（flip（：））[]将翻转列表。

因为 foldl' 是严格的，为了计算结果 Haskell 会在每一步 评估 f，而不是让左参数积累一个庞大的未评估表达式。这给我们想要的通常、高效的尾递归！换句话说：

• foldl' 可以高效地折叠大型列表。
• foldl' 在无限列表上会陷入无限循环（而不会导致堆栈溢出）。

Haskell 维基也有关于此的页面。

- C. A. McCann

---

我来这里是因为我好奇为什么在Haskell中foldr比foldl更好，而在Erlang中相反（我之前学过Haskell之前学的是Erlang）。由于Erlang不是惰性的，并且函数没有柯里化，所以在Erlang中的foldl的行为就像上面的foldl'。这是一个很好的答案！干得好，谢谢！ - Siu Ching Pong -Asuka Kenji-

这基本上是个很好的解释，但我认为将foldl描述为“向后”的函数，而将foldr描述为“向前”的函数有些问题。部分原因是在说明fold为什么是“向后”时，将(:)应用于flip，这让人自然地想到，“当然是向后了：你flip了列表拼接！” 另外，看到foldl被称为“向后”，也有些奇怪，因为在完整的计算中，foldl首先（最内层）将f应用于第一个列表元素。实际上，是foldr在“向后运行”，将f应用于最后一个元素。 - Dave Abrahams

@DaveAbrahams：在仅考虑foldl和foldr，并忽略严格性和优化的情况下，前者意味着“最外层”，而不是“最内层”。这就是为什么foldr可以处理无限列表而foldl不能 - 右折叠首先将f应用于第一个列表元素和（未求值的）折叠尾部的结果，而左折叠必须遍历整个列表以评估f的最外层应用。 - C. A. McCann

@kazuoua 在某些情况下，懒惰是必要的，例如 last xs = foldl (\a z-> z) undefined xs。 - Will Ness

很好的回答，但我认为将foldl的左结合表示为 f (foldl f [] [x1, x2,... xn-1]) xn，并将foldr的左结合表示为 f x1 (foldr f [] [x2, x3, ... xn]) 更加清晰。在这种表示中，很明显foldr可以处理无限列表。 - Dagang

Answer 2

myAny even [1..]
foldl step False [1..]
foldl step (step False 1) [2..]
foldl step (step (step False 1) 2) [3..]
foldl step (step (step (step False 1) 2) 3) [4..]

直觉上，foldl 总是处于“外部”或者“左侧”，因此它会首先被展开，无限循环。

- Artelius

Answer 3

你可以在Haskell的文档这里看到，foldl是尾递归的，如果传递了一个无限列表，它将永远不会结束，因为它在返回值之前会在下一个参数上调用自身...

- Romain

---

所以“诀窍”在于，如果 f 有时可以仅查看其第一个参数的值而无需查看其第二个参数，则 foldr 可以提前退出（因为对于 foldr，f 的第二个参数将是另一个 foldr 调用的结果）。而 foldl 则会立即递归，无论 f 做什么。 - BallpointBen

Answer 4

我不懂Haskell，但在Scheme中，fold-right总是先对列表的最后一个元素进行操作。因此，它对于循环列表（即无限列表）是无效的。

我不确定fold-right是否可以写成尾递归形式，但对于任何循环列表，你都会遇到堆栈溢出的问题。另一方面，fold-left通常采用尾递归实现，如果没有提前终止，它将陷入无限循环中。

- leppie

---

由于 Haskell 具有惰性求值特性，所以情况不同。 - Lifu Huang