A better foldr1 for Foldable1

[andrewthad]

There is not a foldr1 function for Foldable, but I have something in mind that's more general. Consider the following:

semifoldr :: Semifoldable f => (a -> b -> b) -> (a -> b) -> f a -> b

This function behaves as follows:

semifoldr f g [a,b,c,d] = f a (f b (f c (g d)))

Trivially, we can recover foldr1 with:

foldr1 f = semifoldr f id

Going the other way, recovering semifoldr from foldr1 is possibly, but it incurs a hefty performance penalty. The really starts to matter when dealing with a data structure like a non-empty set. I originally stumbled across this variant of foldr1 when working with non-empty monomorphic foldable collections, where the type of foldr1 the base uses is unworkable.

[recursion-ninja]

I have run into this use case several times when working with non-empty structures. There is currently no nice type-class method for projecting the first element of the non-empty structure into the "zero" value for the fold, then to fold over the structure in a natural way with a binary operator.

I think this would be very useful and should be added.

We should add a semifoldl' method too:

semifoldr f g [a,b,c,d] = (((g a) `f` b) `f` c) `f` d

Along with semifoldrM & semifoldlM:

semifoldrM :: Semifoldable f => (a -> b -> m b) -> (a -> m b) -> f a -> m b

semifoldlM :: Semifoldable f => (b -> a -> m b) -> (a -> m b) -> f a -> m b

[andrewthad]

Any thoughts from any of the maintainers? Or is #26 blocking progress on this?

[phadej]

My proposal does include this kind of function, see my recent email https://mail.haskell.org/pipermail/libraries/2019-October/030040.html

I didn't add :: (Semifoldable f, Monad m) => (a -> b -> m b) -> (a -> m b) -> f a -> m b there, but it's uncontroversial. (Will do after bigger bikeshedding is/if settled).

[RyanGlScott]

Foldable1 is now defined in base, and semigroupoids simply re-exports Foldable1 from base. As such, this issue isn't really in scope for semigroupoids anymore. Closing.