The default definitions of foldl1 and foldr1 are too strict
We currently have
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)
This has to traverse the entire container before it can do anything. What we want is
mf x r = Just $ case r of
Nothing -> x
Just y -> f x y