6

考虑以下各种尝试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'有效？它的累加器不应该也很严格吗？

4

1 回答 1

3

作为参考，该实例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
于 2020-08-06T16:14:06.947 回答