为什么foldr可以在Haskell中的无限列表上工作，而foldl却不能？

我一直在努力理解foldl vs foldr vs foldl'在哈斯克尔。我理解共识是使用foldr when f第二个参数是惰性的，因为它反映了列表的结构。foldl'当我们知道需要处理整个列表并且f其论点很严格。

我对这样的情况特别感兴趣：

foldr (&&) False (repeat False)

returns False.

But:

foldl (&&) False (repeat False)

永远不会完成。

The foldr扩展到：

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

Whereas foldl:

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

星星是基本情况False传递到fold.

Is foldr能够立即终止，因为 LHS 只是一个False, while foldl单身的False一直在右侧，并且在完成处理左侧之前它不会“检查”这一点？

我们看一下相关的定义（和上面的不完全一样）Prelude http://hackage.haskell.org/package/base-4.7.0.2/docs/Prelude.html，但与此分析等效）。

(&&) :: 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 and foldl必须产生一个结果。它们在给出时都会立即产生结果[]。在里面(x:xs) case, foldr也有机会产生结果，如果f立即返回而不评估其正确的参数（这是递归调用）。foldl没有这个，因为它最外层的调用是对它自己的，所以唯一的时间foldl可以返回任何信息[]情况，对于无限列表永远不会达到。

在这样的例子中，我发现进行一些手动评估很有帮助。回想一下，Haskell 的求值顺序是由外向内的：我们尽可能少地求值以获得最外层函数应用程序的适用模式匹配。我将在每个步骤中将要评估的下一个函数标记为斜体。foldr很简单：

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

And 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)
  

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

然而，该命令(&&)评估其论点does仍然很重要（它首先评估左侧，由模式匹配语义确定）。我们可以flip参数的顺序，看看会发生什么foldr does:

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

（锻炼）为什么是这样？