haskell - foldl' 和 foldr' 的默认定义看起来很奇怪

Question

foldl'的默认定义和 foldr'看起来很奇怪。它们的默认定义为:

class Foldable t where
    -- ...
    foldr' f z0 xs = foldl f' id xs z0
      where f' k x z = k $! f x z
    -- ...
    foldl' f z0 xs = foldr f' id xs z0
      where f' x k z = k $! f z x
    -- ...

为什么不？:

class Foldable t where
    -- ...
    foldr' f = foldr (\x z -> f x $! z)
    -- ...
    foldl' f = foldl (\z x -> flip f x $! z)
    -- ...

Answer 1

一般来说，foldl'最适合看起来有点像缺点列表和 foldr' 的东西最适合看起来有点像 snoc-lists 的东西。情况是对称的，所以让我们看看 cons-lists，其中 foldl'最好是好的。

您可能已经读过 foldl如果 cons-lists 的优化不够好，它可能会导致空间泄漏。嗯，这正是这里会发生的事情。 f'是严格的，但在折叠到达列表末尾之前不要求任何结果!

默认定义稍微有点扭曲，这使得即使是简单的编译(或解释)也能正常工作。