Add Foldable1 and Bifoldable1 to base

Motivation

It’s regularly asked whether Foldable1 could be added to base (e.g. on reddit1, there’re also GHC issue2 and old phabricator diff3) Also there’s work towards non-empty maps and sets4, which would benefit from Foldable1. Recently nonempty-vector was uploaded to Hackage as well5.

As commented on reddit, Foldable1 could be added without any pain to the base as it’s pure addition - no modifications needed in existing modules.

The most difficult question is the names: Foldable1, Semifoldable, NonEmptyFoldable, or something else?

Changelog

Revision 3

Revision 2

Change: Foldable1

The change exist as merge request6 on gitlab.haskell.org. However the more up to date version of a proposed module is visible from haddocks on

https://oleg.fi/haddocks/foldable1/Data-Foldable1.html

or

http://oleg.fi/haddocks/semifoldable/Data-Semifoldable.html

Importantly, this change doesn’t change anything in other modules of base, except of adding a Foldable instance to Data.Complex. In particular, foldl1 and foldr1 in Data.Foldable remain partial, etc.

My version of Foldable1 class is big, so I’ll comment the motivation for each member

class Foldable t => Foldable1 t where
    {-# MINIMAL foldMap1 | foldr1map #-}

    fold1 :: Semigroup m => t m -> m

    -- the defining member, like foldMap but only asking for Semigroup
    foldMap1 :: Semigroup m => (a -> m) -> t a -> m

    -- strict foldMap1, cf foldMap'
    foldMap1' :: Semigroup m => (a -> m) -> t a -> m

    -- analogue of toList
    toNonEmpty :: t a -> NonEmpty a

    -- left&right, strict&non-strict folds
    foldr1  :: (a -> a -> a) -> t a -> a
    foldr1' :: (a -> a -> a) -> t a -> a
    foldl1  :: (a -> a -> a) -> t a -> a
    foldl1' :: (a -> a -> a) -> t a -> a

    -- these can have efficient implementation for NonEmptySet
    maximum1 :: Ord a => t a -> a
    minimum1 :: Ord a => t a -> a

    -- head1 have efficient implementation for NonEmpty and Tree
    -- last1 for symmetry
    head1 :: t a -> a
    last1 :: t a -> a

    -- fold variants with premap.
    -- Without this map, we cannot implement foldl using foldr etc.
    foldrMap1  :: (a -> b) -> (a -> b -> b) -> t a -> b
    foldlMap1' :: (a -> b) -> (b -> a -> b) -> t a -> b
    foldlMap1  :: (a -> b) -> (b -> a -> b) -> t a -> b
    foldrMap1' :: (a -> b) -> (a -> b -> b) -> t a -> b

The merge request also adds instances for everything non-empty in base.

I propose the Data.Foldable1 as the module name (an alternative Data.Semifoldable). semigroupoids7 uses Data.Semigroup.Foldable, but it’s confusing; and using different name could help migration.

Additionally, the Data.Foldable1 module contains seven top-level functions, which should be self-explanatory:

intercalate1 :: (Foldable1 t, Semigroup m) => m -> t m -> m

foldrM1 :: (Foldable1 t, Monad m) => (a -> a -> m a) -> t a -> m a
foldlM1 :: (Foldable1 t, Monad m) => (a -> a -> m a) -> t a -> m a

foldrMapM1 :: (Foldable1 t, Monad m) => (a -> m b) -> (a -> b -> m b) -> t a -> m b
foldlMapM1 :: (Foldable1 t, Monad m) => (a -> m b) -> (b -> a -> m b) -> t a -> m b

maximum1By :: Foldable1 t => (a -> a -> Ordering) -> t a -> a
minimum1By :: Foldable1 t => (a -> a -> Ordering) -> t a -> a

This is less than in Data.Semigroup.Foldable8, as other top-level definitions doesn’t make sense without bringing in the Apply type-class. For example:

-- needs Apply, not in Data.Foldable1
traverse1_ :: (Foldable1 t, Apply f) => (a -> f b) -> t a -> f ()

And if we relax Apply to Applicative, we get traverse_. Bringing Apply into base is out-of-scope of this proposal.

Bifoldable1

Bifoldable class have Bifoldable1 subclass in semigroupoids. We propose moving that class to base as well.

The propose module would be very tiny and simple.

class Bifoldable t => Bifoldable1 t where
  bifold1 :: Semigroup m => t m m -> m
  bifold1 = bifoldMap1 id id
  {-# INLINE bifold1 #-}

  bifoldMap1 :: Semigroup m => (a -> m) -> (b -> m) -> t a b -> m
  bifoldMap1 f g = maybe (error "bifoldMap1") id . getOption . bifoldMap (Option . Just . f) (Option . Just . g)
  {-# INLINE bifoldMap1 #-}

or using Semi prefix:

class Bifoldable t => Semibifoldable t where
  semibifold :: Semigroup m => t m m -> m
  semibifold = semibifoldMap id id
  {-# INLINE semibifold #-}

  semibifoldMap :: Semigroup m => (a -> m) -> (b -> m) -> t a b -> m
  semibifoldMap f g = maybe (error "semibifoldMap") id . getOption . bifoldMap (Option . Just . f) (Option . Just . g)
  {-# INLINE semibifoldMap #-}

There is a pull-request to bifunctors9, as a proof-of-concept, using Semibifoldable naming scheme.

Bisemifoldable is also a variant, yet Semibifoldable sounds more correct: take Bifoldable and remove empty things resulting into Semibifoldable.

Name controversy

Adding Foldable1 is considered controversial. Library submissions guidelines say:

Adding a new, useful function under a clear name is probably not controversial

Yet in this case, there doesn’t seem to be clear names. The alternative naming scheme is discussed on semigroupoids issue tracker10.

In a comment nickname chessai list a table of possible renamings, essentially dropping 1-suffix and adding semi- prefix.11 Following comments brainstorm more ideas like:

The bad sounding names are semihead, semilast, semimaximum and semiminimum. In theory they could be prefixless and suffixless, i.e. plain head, last, maximum, and minimum. However, I consider that naming more controversial, as it clashes with Prelude names, even one can argue that Semifoldable members should eventually replace them. Luckily, the names can be changed, if they are on the way into Prelude.

A variation of this, is to use bare s as prefix to the members, i.e. sfoldMap, sfoldr. It’s shorter, but maybe too subtle?

One justification to not use 1-suffix name is12

The 1 is still in conflict, but requires more Eq1, etc like classes to define. e.g. Monoid1 for taking a monoid to a monoid, then Foldable1 consistently in that nomenclature would let you reduce through a Monoid1.

Also using qualified imports would prevent Foldable1 class to be ever imported unqualified13:

The haddocks for Semi.Monad being a superclass of Monad someday in the far flung future would be frankly pretty awful to read, and would ensure that they could never move into Prelude, forever dooming them to a second class existence.

And finally, trying to unify Foldable with Foldable1 into single class using type families / some hackery requires QuantifiedConstraints at the very least. That’s not a realistic option to current, essentially a Haskell98 formulation.

On the other hand few people noted14 that where Semiapplicative and Semimonad would be good names for what’s currently called Apply and Bind, Semifoldable feels like a superclass of Foldable, i.e.

-- feels like
class Semifoldable f => Foldable f where
class Foldable f => Semifoldable f where

Alternatives mentioned are

-- class prefix NonEmpty,
-- method prefix bare s
class Foldable f => NonEmptyFoldable f where
    sfoldMap :: Semigroup s => (a -> s) -> f a -> s

    sminimum :: Ord a => f a -> a
    shead    :: f a -> a

class Bifoldable p => NonEmptyBifoldable p where
    sbifoldMap :: Semigroup s => (a -> s) -> (b -> s) -> p a b -> s

-- or alternatively: method prefix `ne` (for nonempty):

    nefoldMap
    neminimum
    nehead
    nebifoldMap

-- or suffix `NE`

    foldMapNE
    minimumNE
    headNE
    bifoldMapNE

The last function naming scheme is used in containers patch15, which adds NonEmptyMap. Using this scheme Traversable1 will become

class Traversable t => NonEmptyTraversable t where
    traverseNE :: SemiApplicative f => (a -> f b) -> t a -> f (t b)

Inefficiency of foldr1

In another semigroupoids issue16, the inefficiency of foldr1 is highlighted.

The proposal includes functions like:

foldrMap1 :: (a -> b) -> (a -> b -> b) -> t a -> b
foldlMap1 :: (a -> b) -> (b -> a -> b) -> t a -> b

And in fact the minimal pragma is {-# MINIMAL foldMap1 | foldrMap1 #-}

The order of function arguments is chosen so:

foldr1 = foldr1Map id

Another option is to have function arguments flipped:

foldrMap1 :: (a -> b -> b) -> (a -> b) -> t a -> b
foldlMap1 :: (b -> a -> b) -> (a -> b) -> t a -> b

which more closely resembles foldr and foldl. The start element of a fold is seed with the right or the left element.

Compatibility & migration

I drafted a compatibility package foldable1:

which I hope could be maintained under github.com/haskell organization. I can act as a maintainer, with a hope that there won’t be a lot of changes happening in Data.Foldable1.

To my surprise, there’s already a package with this name on Hackage17 by M Farkas-Dyck (cc’d). He kindly offered to donate the name if this proposal is accepted (with foldable1 name).18

Data.Foldable1 contains also instances for Lift, Backwards and Reverse, and other data types from transformers. Perfectly, the transformers bundled with GHC with this change would implement the instances as well. This change should propagate to transformers-compat too.

Similarly, containers would have an instance for Tree (and non-empty Set and Map when they are added).

Other packages would be compat’d as follows: - foldable1 would provide instances for Tagged from tagged - Bifoldable1 class would migrate to bifunctors

This is because current dependencies are:

semigroups <- tagged <- bifunctors <- semigroupoids

and foldable1 would be more natural between tagged and bifunctors:

semigroups <- tagged <- foldable1 <- bifunctors <- semigroupoids

foldable have to be before bifunctors in the dependency tree, as Bifoldable1 instances of some bifunctors need Foldable1 class.

I also drafted a pull requests for compatibility patches to bifunctors19 and semigroupoids20 with

Unresolved questions

Appendix: Foldable1 synopsis

Module names: Data.Foldable1 and Data.Bifoldable1

class Foldable t => Foldable1 t where
  fold1      :: Semigroup m => t m -> m
  foldMap1   :: Semigroup m => (a -> m) -> t a -> m
  foldMap1'  :: Semigroup m => (a -> m) -> t a -> m

  foldr1     :: (a -> a -> a) -> t a -> a
  foldr1'    :: (a -> a -> a) -> t a -> a
  foldl1     :: (a -> a -> a) -> t a -> a
  foldl1'    :: (a -> a -> a) -> t a -> a

  toNonEmpty :: t a -> NonEmpty a

  maximum1   :: Ord a => t a -> a
  minimum1   :: Ord a => t a -> a
  head1      :: t a -> a
  last1      :: t a -> a

  foldrMap1  :: (a -> b) -> (a -> b -> b) -> t a -> b
  foldlMap1' :: (a -> b) -> (b -> a -> b) -> t a -> b
  foldlMap1  :: (a -> b) -> (b -> a -> b) -> t a -> b
  foldrMap1' :: (a -> b) -> (a -> b -> b) -> t a -> b

intercalate1 :: (Foldable1 t, Semigroup m) => m -> t m -> m
foldrM1      :: (Foldable1 t, Monad m) => (a -> a -> m a) -> t a -> m a
foldlM1      :: (Foldable1 t, Monad m) => (a -> a -> m a) -> t a -> m a
foldrMapM1   :: (Foldable1 t, Monad m) => (a -> m b) -> (a -> b -> m b) -> t a -> m b
foldlMapM1   :: (Foldable1 t, Monad m) => (a -> m b) -> (b -> a -> m b) -> t a -> m b
maximum1By   :: Foldable1 t => (a -> a -> Ordering) -> t a -> a
minimum1By   :: Foldable1 t => (a -> a -> Ordering) -> t a -> a

class Bifunctor p => Bifunctor1 p where
  bifoldMap1 :: Semigroup s => (a -> s) -> (b -> s) -> p a b -> s

Appendix: Foldable1 synopsis with clashing names

Module names: Data.Foldable1 and Data.Bifoldable1

https://oleg.fi/haddocks/foldable1/Data-Foldable1.html

class Foldable t => Foldable1 t where
  fold1      :: Semigroup m => t m -> m
  foldMap1   :: Semigroup m => (a -> m) -> t a -> m
  foldMap1'  :: Semigroup m => (a -> m) -> t a -> m

  foldr1     :: (a -> a -> a) -> t a -> a
  foldr1'    :: (a -> a -> a) -> t a -> a
  foldl1     :: (a -> a -> a) -> t a -> a
  foldl1'    :: (a -> a -> a) -> t a -> a

  toNonEmpty :: t a -> NonEmpty a

  maximum    :: Ord a => t a -> a
  minimum    :: Ord a => t a -> a
  head       :: t a -> a
  last       :: t a -> a

  foldrMap1  :: (a -> b) -> (a -> b -> b) -> t a -> b
  foldlMap1' :: (a -> b) -> (b -> a -> b) -> t a -> b
  foldlMap1  :: (a -> b) -> (b -> a -> b) -> t a -> b
  foldrMap1' :: (a -> b) -> (a -> b -> b) -> t a -> b

intercalate1 :: (Foldable1 t, Semigroup m) => m -> t m -> m
foldrM1      :: (Foldable1 t, Monad m) => (a -> a -> m a) -> t a -> m a
foldlM1      :: (Foldable1 t, Monad m) => (a -> a -> m a) -> t a -> m a
foldrMapM1   :: (Foldable1 t, Monad m) => (a -> m b) -> (a -> b -> m b) -> t a -> m b
foldlMapM1   :: (Foldable1 t, Monad m) => (a -> m b) -> (b -> a -> m b) -> t a -> m b
maximumBy    :: Foldable1 t => (a -> a -> Ordering) -> t a -> a
minimumBy    :: Foldable1 t => (a -> a -> Ordering) -> t a -> a

class Bifunctor p => Bifunctor1 p where
  bifoldMap1 :: Semigroup s => (a -> s) -> (b -> s) -> p a b -> s

Appendix: Semifoldable synopsis

Module names: Data.Semifoldable and Data.Semibifoldable

class Foldable t => Semifoldable t where
  semifold      :: Semigroup m => t m -> m
  semifoldMap   :: Semigroup m => (a -> m) -> t a -> m
  semifoldMap'  :: Semigroup m => (a -> m) -> t a -> m

  semifoldr     :: (a -> a -> a) -> t a -> a
  semifoldr'    :: (a -> a -> a) -> t a -> a
  semifoldl     :: (a -> a -> a) -> t a -> a
  semifoldl'    :: (a -> a -> a) -> t a -> a

  toNonEmpty    :: t a -> NonEmpty a

  semimaximum   :: Ord a => t a -> a
  semiminimum   :: Ord a => t a -> a
  semihead      :: t a -> a
  semilast      :: t a -> a

  semifoldrMap  :: (a -> b) -> (a -> b -> b) -> t a -> b
  semifoldlMap' :: (a -> b) -> (b -> a -> b) -> t a -> b
  semifoldlMap  :: (a -> b) -> (b -> a -> b) -> t a -> b
  semifoldrMap' :: (a -> b) -> (a -> b -> b) -> t a -> b

intercalate1  :: (Semifoldable t, Semigroup m) => m -> t m -> m
semifoldrM    :: (Semifoldable t, Monad m) => (a -> a -> m a) -> t a -> m a
semifoldlM    :: (Semifoldable t, Monad m) => (a -> a -> m a) -> t a -> m a
semifoldrMapM :: (Foldable1 t, Monad m) => (a -> m b) -> (a -> b -> m b) -> t a -> m b
semifoldlMapM :: (Foldable1 t, Monad m) => (a -> m b) -> (b -> a -> m b) -> t a -> m b
semimaximumBy :: Semifoldable t => (a -> a -> Ordering) -> t a -> a
semiminimumBy :: Semifoldable t => (a -> a -> Ordering) -> t a -> a

-- or alternatively
semiintercalate

class Bifunctor p => NonEmptyBifunctor p where
  semifoldMap :: Semigroup s => (a -> s) -> (b -> s) -> p a b -> s

Appendix: NonEmptyFoldable synopsis

Module names: Data.Foldable.NonEmpty and Data.Bifoldable.NonEmpty

class Foldable t => NonEmptyFoldable t where
  foldNE      :: Semigroup m => t m -> m
  foldMapNE   :: Semigroup m => (a -> m) -> t a -> m
  foldMapNE'  :: Semigroup m => (a -> m) -> t a -> m

  foldrNE     :: (a -> a -> a) -> t a -> a
  foldrNE'    :: (a -> a -> a) -> t a -> a
  foldlNE     :: (a -> a -> a) -> t a -> a
  foldlNE'    :: (a -> a -> a) -> t a -> a

  toNonEmpty  :: t a -> NonEmpty a

  maximumNE   :: Ord a => t a -> a
  minimumNE   :: Ord a => t a -> a
  headNE      :: t a -> a
  lastNE      :: t a -> a

  foldrMapNE  :: (a -> b) -> (a -> b -> b) -> t a -> b
  foldlMapNE' :: (a -> b) -> (b -> a -> b) -> t a -> b
  foldlMapNE  :: (a -> b) -> (b -> a -> b) -> t a -> b
  foldrMapNE' :: (a -> b) -> (a -> b -> b) -> t a -> b

intercalateNE :: (NonEmptyFoldable t, Semigroup m) => m -> t m -> m
foldrMNE      :: (NonEmptyFoldable t, Monad m) => (a -> a -> m a) -> t a -> m a
foldlMNE      :: (NonEmptyFoldable t, Monad m) => (a -> a -> m a) -> t a -> m a
foldrMapMNE   :: (NonEmptyFoldable t, Monad m) => (a -> m b) -> (a -> b -> m b) -> t a -> m b
foldlMapMNE   :: (NonEmptyFoldable t, Monad m) => (a -> m b) -> (b -> a -> m b) -> t a -> m b
maximumNEBy   :: NonEmptyFoldable t => (a -> a -> Ordering) -> t a -> a
minimumNEBy   :: NonEmptyFoldable t => (a -> a -> Ordering) -> t a -> a

class Bifunctor p => NonEmptyBifunctor p where
  bifoldMapNE :: Semigroup s => (a -> s) -> (b -> s) -> p a b -> s

  1. https://www.reddit.com/r/haskell/comments/6d0vgt/could_we_have_foldable1_and_traversable1_in_base/↩︎

  2. https://gitlab.haskell.org/ghc/ghc/issues/13573↩︎

  3. https://phabricator.haskell.org/D4812↩︎

  4. https://github.com/haskell/containers/pull/616↩︎

  5. https://hackage.haskell.org/package/nonempty-vector↩︎

  6. https://gitlab.haskell.org/ghc/ghc/merge_requests/1973↩︎

  7. https://hackage.haskell.org/package/semigroupoids↩︎

  8. https://hackage.haskell.org/package/semigroupoids-5.3.3/docs/Data-Semigroup-Foldable-Class.html↩︎

  9. https://github.com/ekmett/bifunctors/pull/78↩︎

  10. https://github.com/ekmett/semigroupoids/issues/26↩︎

  11. https://github.com/ekmett/semigroupoids/issues/26#issuecomment-395565772↩︎

  12. https://github.com/ekmett/semigroupoids/issues/26#issuecomment-395950042↩︎

  13. https://github.com/ekmett/semigroupoids/issues/26#issuecomment-398117218↩︎

  14. https://mail.haskell.org/pipermail/libraries/2019-October/030036.html↩︎

  15. https://github.com/haskell/containers/pull/616↩︎

  16. https://github.com/ekmett/semigroupoids/issues/77↩︎

  17. https://hackage.haskell.org/package/foldable1↩︎

  18. https://mail.haskell.org/pipermail/libraries/2019-October/030029.html↩︎

  19. https://github.com/ekmett/bifunctors/pull/78↩︎

  20. https://github.com/ekmett/semigroupoids/pull/87↩︎