为什么 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) 可以短路，因为最外层 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

但这要花很长时间。

我以为 outermost andFn 会知道通过第二个参数的模式匹配，答案是 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

因此 foldl f z infiniteList 将总是发散，无论 f 是什么：整个 infiniteList 需要在任何之前完全迭代真正的计算发生了。（题外话：这就是为什么 foldl 即使有效，也经常有糟糕的表现，而 foldl' 在实践中使用得更多。）

特别是发布的例子

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

部分错误。 "outermost andFn" 实际上是 last 一个，即与 repeat False 中的 last 元素相关的那个。但是没有这样的野兽。

why foldl is not short circuiting with andFn function?