为什么foldr在Haskell中的无限列表上工作但是foldl不工作？

Question

我一直致力于在Haskell中理解foldlvs foldrvs.foldl'我理解,共识是在第二个参数中使用foldr何时f是惰性的,因为它反映了列表的结构.foldl'当我们知道需要处理整个列表并且f其参数严格时,会更好.

我特别感兴趣的是这样的情况:

foldr (&&) False (repeat False)

回报False.

但:

foldl (&&) False (repeat False)

从未完成.

该foldr扩展为:

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

鉴于foldl:

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

星星是False传入的基础案例fold.

是否foldr能立即终止,因为LHS只是一个单一的False,而foldl单False是在右边一路,它不"检查"直到它完成处理左边？

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)情况下,foldr如果f立即返回而不评估其正确的参数(这是递归调用),也有机会产生结果. 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

(运动)这是为什么？