haskell - 为什么foldl没有与andFn功能短路？

Question

我的理解是，foldl执行foldr如下：

foldl f a [1..30]=>(f (f (f ... (f a 1) 2) 3) ... 30)

和

foldr f a [1..30]=>(f 1 (f 2 (f 3 (f ....(f 30 a)))))..)

所以.. foldr (&&) False (repeat False)can shortciruit as outermost fsees(&&) False ((&&) False (....))将第一个参数视为 false 并且不需要评估第二个参数（这是一个很大的 thunk）。

那么会发生什么

andFn :: Bool -> Bool -> Bool
andFn _ False = False
andFn x True  = x

和

foldl andFn True (repeat False)  -- =>

-- (andFn (andFn ...(andFn True False) ... False) False)
--  ^^ outermost andFn

但这需要永远。

我认为outermost andFn通过第二个参数的模式匹配会知道，答案是False..

这里还发生了什么？

score 17 · Accepted Answer

foldr和foldl的参数顺序之间存在更大的差异andFn。

foldr f z (x:xs) = f x (foldr f z xs)
foldl f z (x:xs) = foldl f (f z x) xs

注意如何foldr立即将控制转移到f：如果f是惰性的，它可以避免计算foldr f z xs.

相反，foldl将控制权转移到... foldl：该函数f仅在达到基本情况时才开始使用

foldl f z [] = z      -- z contains the chained f's, which NOW get evaluated

因此总是foldl f z infiniteList会发散，不管是什么：在任何真正的计算发生之前，整体需要完全迭代。（题外话：这就是为什么即使它有效，也经常表现糟糕，并且在实践中更多地使用。）finfiniteListfoldlfoldl'

特别是发布的示例

foldl andFn True (repeat False)  -- =>
-- (andFn (andFn ...(andFn True False) ... False) False)
--  ^^ outermost andFn

部分错误。“最外层”andFn实际上是最后一个，即与. 但是没有这样的野兽。repeat False

1 回答 1