Why isn't `foldl1` defined in terms of `foldr`?
Posting it here as suggested by @meooow.
I recently posted on Reddit regarding defining foldl1
and foldl1'
by default in a more fusion-friendly manner. Basically, instead of
foldl1 :: Foldable t => (a -> a -> a) -> t a -> a
foldl1 f xs = fromMaybe (errorWithoutStackTrace "foldl1: empty structure")
(foldl mf Nothing xs)
where
mf m y = Just (case m of
Nothing -> y
Just x -> f x y)
we could have
foldl1 :: Foldable t => (a -> a -> a) -> t a -> a
foldl1 f xs =
foldr step (const id) xs (const id) $
errorWithoutStackTrace "foldl1: empty structure"
where
step x k f' z = k f $ f' z x
{-# INLINE step #-}
{-# INLINE foldl1 #-}
and for foldl1'
it would be the same except step
would be step x k f' z = k f $! f' z x
.
@Tarmen investigated the idea further and verified that we indeed get the same effect as with the current definitions plus -fspec-constr
.
There was also some pushback from @foBrowsing regarding the inconvenience of the proposed new defaults: the proposed implementation wouldn't work as desired for left-nested structures (such as snoc-lists) and so the user would have to implement foldl1
and foldl1'
manually instead of getting the right behavior out of the box by only implementing manually foldl
. My response was that this is already the case for a number of functions and so the new defaults for foldl1
and foldl1'
wouldn't make the situation much worse. I do however agree that they would make it somewhat worse for the specific case of left-nested structures.
One clear problem of course is that foldl1'
isn't a method of Foldable
and so it doesn't make much sense to talk about defaults here, so maybe it's all waste?
Sorry for the messy rant!