为什么在Haskell中foldr适用于无限列表，而foldl不适用？

Question

我一直在研究Haskell中的foldl、foldr和foldl'之间的区别。我理解使用foldr时，当f的第二个参数是惰性的且它反映了列表的结构时，这是共识。如果我们知道需要处理整个列表并且f对其参数是严格的，则更好地使用foldl'。 我特别关注这样一种情况：

foldr (&&) False (repeat False)

返回False。

但是：

foldl (&&) False (repeat False)

永远不会完成。

foldr的展开形式为：

False && (False && (False && .... (False && *False*)) ... )

相较于 foldl：

  && (... (&& (&& *False* False) False) ...) False

星星是传递到折叠函数中的基本情况，其值为False。 foldr能够立即终止，因为左侧只有一个False，而foldl中单个False位于最右侧，直到处理完左侧后才会“检查”它。

- user2666425

---

你可以通过传递 flip (&&) 来检查你的假设。 - luqui

@luqui 他们俩都没有以 flip (&&) 结束，但我不确定 flip 在这种情况下有什么影响。同样，如果我的假设正确，我更加好奇的是 为什么 会这样，并且为什么不能检查两种情况下的一个参数是否为 False 并且在处理剩余部分之前返回 False。 - user2666425

Answer 1

让我们看一下相关的定义（不完全与Prelude相同，但对于这个分析来说是等效的）。

(&&) :: Bool -> Bool -> Bool
True && x = x
False && _ = False

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

观察foldr和foldl各自产生结果的机会。 它们在给定[]时都立即产生结果。 对于(x:xs)情况，如果f立即返回而不评估其右参数（递归调用），foldr也有机会产生结果。 但是foldl没有这个机会，因为它最外层的调用是它自己，所以foldl只能在[]情况下提供信息，而对于无限列表永远不会到达该情况。

在此类示例中，我发现手动计算有助于理解。回想一下Haskell的求值顺序，它从外到内进行：我们尽可能少地评估以达到最外层函数应用的可应用模式匹配。在每步中，我将用斜体表示要评估的下一个函数。 foldr很简单：

  foldr (&&) False (repeat False)
= foldr (&&) False (False : repeat False)
= False && foldr (&&) False (repeat False)
= False

foldl揭示了问题：

  foldl (&&) False (repeat False)
= foldl (&&) False (False : repeat False)
= foldl (&&) (False && False) (repeat False)
= foldl (&&) (False && False) (False : repeat False)
= foldl (&&) ((False && False) && False) (repeat False)
= foldl (&&) ((False && False) && False) (False : repeat False)
= foldl (&&) (((False && False) && False) && False) (repeat False)

等等。请注意，即使(&&)能够通过检查任一侧来简化，我们仍然永远没有机会返回，因为我们从未到达[]情况。

但是，(&&)评估其参数的顺序仍然很重要（由模式匹配语义确定它首先评估左参数）。我们可以用flip翻转参数的顺序并查看foldr的结果：

ghci> foldr (flip (&&)) False (repeat False)
^CInterrupted

(练习) 为什么？

- luqui

---

谢谢你的回答。所以如果传入了 flip (&&)，那么 foldr .. 是 && 的第一个参数，False 是第二个参数。因此，我会假设它尝试评估其第一个参数。所以，&& 只在其第一个参数上进行短路，它不检查第二个参数是否为平凡的情况？另外，这说明为什么 foldr 在这里比 foldl 更好，但是可以说 && 在这里的第二个参数是'lazy'，这不太公平，对吧？这更多地涉及到短路而不是懒惰，或者术语是相同的吗？ - user2666425

@user2666425，“（&&）”在其第二个参数上是有条件严格的。如果您想更精确地了解如何称呼事物，请阅读有关指示语义的内容。 - luqui

Answer 2

foldr op z [1..] 创建一个类似于这样的表达式树：

 op
 /\
1  op
   /\
  2  op
     /\
    3  .
        .
         .

那棵树除了有限的一部分在任何特定的op之下，所以如果任何一个op放弃它们的参数（甚至只是第二个参数），那么这棵树就会被减小到一个有限的大小，可以在有限的时间内完全求值。

foldl op z [1..]创建了如下的表达式树：

         .
        .
       .
     op
     /\
   op  3
   /\
 op  2
 /\
z  1

这棵树除了一个有限的部分是在任何特定的op之上，因此即使每个op都丢弃它的两个参数，也无法通过有限数量的缩减步骤将其缩小到有限大小。

如果这些列表是有限的，那么树的形状就是彼此镜像的，但从无限列表构建的树没有这种对称性，因为无限列表没有这种对称性：它们在右侧是无限的，而不是在左侧。

- benrg

---

实际上，对于一个无限列表，foldl 将永远不会停止构造表达式树，而 foldr 只会构造一个顶级节点并立即将控制权传递给缩减函数：foldl f z (x:xs) = foldl f (f z x) xs; foldr f z (x:xs) = f x (foldr f z xs)。 - Will Ness

@WillNess 我试图避免假设任何评估顺序。一个乐观的求值器可能会在foldr中比懒惰的求值器更晚地应用f，或者在foldl中更早地应用f，但是关于表达式树的论点仍然适用。 - benrg

啊，不错。也许可以在回答中提及一下？ :) - Will Ness