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

so.. foldr (&&) False (repeat False) 可以缩短，因为最外层的 f 看到 (&&) 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

但这需要很长时间。

我认为最外层和Fn会知道，通过第二个参数的模式匹配，答案是False..

这里还发生了什么？

Answer 1

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

因此，无论 f 是什么，foldl f zInfiniteList 将总是发散:整个 infiniteList 需要在任何实际计算发生之前完全迭代。 (题外话:这就是为什么，即使它有效，foldl 常常表现得很糟糕，而 foldl' 在实践中使用得更多。)

特别是发布的示例

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

部分错误。 “最外面的 andFn” 实际上是最后一个，即与 repeat False 中的 last 元素相关的那个>。但没有这样的野兽。