Proposal: Make default impls for foldl1 and foldr1 lazier

29 Oct 2014

      We currently have (in Data.Foldable)

    foldr1 :: (a -> a -> a) -> t a -> a
    foldr1 f xs = fromMaybe (error "foldr1: empty structure")
                    (foldr mf Nothing xs)
      where
        mf x Nothing = Just x
        mf x (Just y) = Just (f x y)

and something similar for foldl1. This is strict in the entire spine,
unlike the list version, because it has to get all the way to the end of
the list before it starts laying down Justs. I propose we change this to
the obvious:

    foldr1 :: (a -> a -> a) -> t a -> a
    foldr1 f xs = fromMaybe (error "foldr1: empty structure")
                    (foldr mf Nothing xs)
      where
        mf x r = Just $ case r of
                          Nothing -> x
                          Just y  -> f x y

Since GHC 7.10.1 is fast approaching, I doubt we have the usual two weeks
to discuss this, so please speak up as soon as you can if you have concerns.

Proposal: Make default impls for foldl1 and foldr1 lazier

David Feuer