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' 最适合看起来像 cons-lists 的东西，foldr' 最适合看起来像 snoc-lists 的东西。情况是对称的，所以我们只看缺点列表，其中 foldl' 最好是好的。

您可能读过 foldl for cons-lists 如果优化不够好会导致 space 泄漏。好吧，这正是这里会发生的事情。 f' 是严格的，但在折叠到达列表末尾之前需要 none 个结果！

默认定义略有不同，即使是简单的编译（或解释）也能正常工作。

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

Default definitions of foldl' and foldr' seem weird

haskell

evaluation

fold