It’s regularly asked whether `Foldable1`

could be added to `base`

(e.g. on reddit^{1}, there’re also GHC issue^{2} and old phabricator diff^{3}) Also there’s work towards non-empty maps and sets^{4}, which would benefit from `Foldable1`

. Recently `nonempty-vector`

was uploaded to Hackage as well^{5}.

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?

- Propose moving
`Bifoldable1`

(`Semibifoldable`

) to`base`

as well. Move compat`Bifoldable1`

to`bifunctors`

. - Changed the type of
`foldrMap1`

to be`(a -> b) -> (a -> b -> b) -> t a -> b`

- Add
`foldrMapM1`

and`foldlMapM1`

. These methods could use just`Bind`

(`Semimonad`

), but as that’s not available in base, they don’t.`semigroupoids`

could provide such variants. - Third naming variant:
`NonEmptyFoldable`

with`foldMapNE`

; and few other variations mentioned. - Patches: https://github.com/ekmett/bifunctors/pull/78 https://github.com/ekmett/semigroupoids/pull/87

- Remove
`toNonEmpty`

from MINIMAL pragma - Add
`Semifoldable`

naming-scheme alternative (see sections at the end) - Discuss
`Bifoldable1`

- Discuss
`foldr1`

inefficiency - Migration plan for
`tagged`

and`bifunctors`

- PoC patch to
`semigroupoids`

`foldable1`

package has doctest examples, and a test-suite- more members are manually implemented (and tested)

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

or

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) -> (b -> b -> b) -> t a -> b
foldl'Map1 :: (a -> b) -> (b -> b -> b) -> t a -> b
foldlMap1 :: (a -> b) -> (b -> b -> b) -> t a -> b
foldr'Map1 :: (a -> b) -> (b -> 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`

). `semigroupoids`

^{7} 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.Foldable`

^{8}, 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.

`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 `bifunctors`

^{9}, 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`

.

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 tracker^{10}.

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:

- all the functions that aren’t actual typeclass methods could possibly just keep the
`1`

suffix - I’m struggling against consistency here, because some functions sound great with
`semi`

- as their prefix, and some sound bad

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 is^{12}

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 unqualified^{13}:

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 noted^{14} 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.

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`

patch^{15}, 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)
```

In another `semigroupoids`

issue^{16}, 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:

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.

I drafted a compatibility package `foldable1`

:

- GitHub repository: https://github.com/phadej/foldable1
- haddocks: https://oleg.fi/haddocks/foldable1/
- Semifoldable variant: https://github.com/phadej/foldable1/pull/5
- its haddocks: https://oleg.fi/haddocks/semifoldable/

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 Hackage^{17} 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 `bifunctors`

^{19} and `semigroupoids`

^{20} with

- The names? Foldable1 or Semifoldable, members?
- Bifoldable1 or Semibifoldable (or Bisemifoldable)?
- Members:
`semifoldMap`

or just`sfoldMap`

? See following Foldable1 and Semifoldable sections for synopsis

- GHC-8.10 freeze is quite soon, is targeting GHC-8.12/base-4.15 more realistic. Note: this technically is a non-breaking change in
`base`

, so could be bundled with GHC-8.10.2, but I think sticking to major would be preferable by GHC HQ.

Module name: `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
maximum1 :: Ord a => t a -> a
minimum1 :: Ord a => t a -> a
head1 :: t a -> a
last1 :: t a -> a
foldrMap1 :: (a -> b) -> (b -> b -> b) -> t a -> b
foldl'Map1 :: (a -> b) -> (b -> b -> b) -> t a -> b
foldlMap1 :: (a -> b) -> (b -> b -> b) -> t a -> b
foldr'Map1 :: (a -> b) -> (b -> 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
```

Module names`:`

Data.Semifoldable`and`

Data.Semibifoldable`

https://oleg.fi/haddocks/semifoldable/

```
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) -> (b -> b -> b) -> t a -> b
semifoldl'Map :: (a -> b) -> (b -> b -> b) -> t a -> b
semifoldlMap :: (a -> b) -> (b -> b -> b) -> t a -> b
semifoldr'Map :: (a -> b) -> (b -> 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
```

Module name: `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) -> (b -> b -> b) -> t a -> b
foldl'MapNE :: (a -> b) -> (b -> b -> b) -> t a -> b
foldlMapNE :: (a -> b) -> (b -> b -> b) -> t a -> b
foldr'MapNE :: (a -> b) -> (b -> 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
```

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

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

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

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

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

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

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