为什么foldr'不像foldl'那么严格？

Question

考虑这些对类似 last:

的尝试

Prelude> import Data.Foldable
Prelude Data.Foldable> foldr const undefined (reverse [1,2,3])
3
Prelude Data.Foldable> foldr' const undefined (reverse [1,2,3])
3
Prelude Data.Foldable> foldl (flip const) undefined [1,2,3]
3
Prelude Data.Foldable> foldl' (flip const) undefined [1,2,3]
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:79:14 in base:GHC.Err
  undefined, called at <interactive>:5:21 in interactive:Ghci4

对我来说，foldl 和 foldr 都有效，因为它们在累加器中不严格，对我来说，foldl' 没有，因为它是。但为什么 foldr' 有效？它的累加器不应该也很严格吗？

Answer 1

供参考，实例 Foldable [] 覆盖 foldr、foldl、foldl'，但不覆盖 foldr' (source)：

instance Foldable [] where
    elem    = List.elem
    foldl   = List.foldl
    foldl'  = List.foldl'
    foldl1  = List.foldl1
    foldr   = List.foldr
    {- ... -}

foldr' 默认定义为 (source):

foldr' :: (a -> b -> b) -> b -> t a -> b
foldr' f z0 xs = foldl f' id xs z0
  where f' k x z = k $! f x z

请注意，f的结果只有严格性注释。所以初始累加器不是强制的。

这表明一个不同的实现会强制累加器：

foldr'' :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldr'' f = foldr (\x z -> f x $! z)

（已编辑：之前的版本专门用于列表。）

我不知道为什么选择一个而不是另一个。大概是疏忽， foldr' 在 Foldable [] 实例中不使用默认实现会更加一致。

顺便说一句，foldl' 的默认定义也以相同的方式不同于列表：

-- Default (class Foldable t where ...)
foldl' :: (b -> a -> b) -> b -> t a -> b
foldl' f z0 xs = foldr f' id xs z0
  where f' x k z = k $! f z x

-- List implementation
foldl'           :: forall a b . (b -> a -> b) -> b -> [a] -> b
foldl' k z0 xs =
  foldr (\(v::a) (fn::b->b) -> oneShot (\(z::b) -> z `seq` fn (k z v))) (id :: b -> b) xs z0

为什么foldr'不像foldl'那么严格？

Why is foldr' not as strict as foldl'?

haskell

lazy-evaluation

fold

strictness