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