为什么foldl与forFn函数没有短路？

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)可以shortciruit,因为外部f看到(&&) 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

部分是错误的."最外层andFn"实际上是最后一个,即与最后一个元素相关的那个repeat False.但是没有这样的野兽.