Skip to content

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!

To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information