Consider these various attempts at something that works like 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
It makes sense to me that foldl
and foldr
both work, since they aren't strict in their accumulator, and it makes sense to me that foldl'
doesn't, since it is. But why does foldr'
work? Isn't it supposed to be strict in its accumulator too?
For reference, the instance Foldable []
overrides foldr
, foldl
, foldl'
, but not foldr'
(source):
instance Foldable [] where
elem = List.elem
foldl = List.foldl
foldl' = List.foldl'
foldl1 = List.foldl1
foldr = List.foldr
{- ... -}
foldr'
is defined by default as (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
Note that there is only a strictness annotation on the result of f
. So the initial accumulator is not forced.
This suggests a different implementation which does force the accumulator:
foldr'' :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldr'' f = foldr (\x z -> f x $! z)
(Edited: the previous version was specialized to lists.)
I have no idea why one was chosen over the other. Probably an oversight,
and it would be more consistent for foldr'
to not use the default implementation in the Foldable []
instance.
As an aside, the default definition of foldl'
is also different from the list one in the same way:
-- 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