Friendly ping, have committee started discussion on this proposal? - Oleg On 4.11.2019 10.15, Oleg Grenrus wrote:
This is the third revision of the proposal.
The rendered version is available at https://oleg.fi/foldable1-proposal3.html
I'm submitting this to CLC for decision making.
Best regards, Oleg Grenrus
Add Foldable1 and Bifoldable1 to base =====================================
Motivation ----------
It's regularly asked whether `Foldable1` could be added to `base` (e.g. on reddit[^ref1], there're also GHC issue[^ref2] and old phabricator diff[^ref3]) Also there's work towards non-empty maps and sets[^ref4], which would benefit from `Foldable1`. Recently `nonempty-vector` was uploaded to Hackage as well[^refV].
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?
[^ref1]: https://www.reddit.com/r/haskell/comments/6d0vgt/could_we_have_foldable1_and... [^ref2]: https://gitlab.haskell.org/ghc/ghc/issues/13573 [^ref3]: https://phabricator.haskell.org/D4812 [^ref4]: https://github.com/haskell/containers/pull/616 [^refV]: https://hackage.haskell.org/package/nonempty-vector
Changelog ---------
<h3>Revision 3</h3>
- 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
<h3>Revision 2</h3>
- 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)
Change: Foldable1 -----------------
The change exist as merge request[^ghcMR] 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
```haskell 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`[^semigroupoids] 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:
```haskell 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`[^d.s.foldable], as other top-level definitions doesn't make sense without bringing in the `Apply` type-class. For example:
```haskell -- 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.
[^ghcMR]: https://gitlab.haskell.org/ghc/ghc/merge_requests/1973 [^semigroupoids]: https://hackage.haskell.org/package/semigroupoids [^d.s.foldable]: https://hackage.haskell.org/package/semigroupoids-5.3.3/docs/Data-Semigroup-...
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.
```haskell 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:
```haskell 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`[^bifunctorPR], 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`.
[^bifunctorPR]: https://github.com/ekmett/bifunctors/pull/78
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 tracker[^naming-issue].
In a comment nickname chessai list a table of possible renamings, essentially dropping `1`-suffix and adding `semi`- prefix.[^refComment1] 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[^refComment2]
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[^refComment3]:
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[^bikeshedding] 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.
```haskell -- feels like class Semifoldable f => Foldable f where ```
```haskell class Foldable f => Semifoldable f where ```
Alternatives mentioned are
```haskell -- 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[^containersNEpatch], which adds `NonEmptyMap`. Using this scheme `Traversable1` will become
```haskell class Traversable t => NonEmptyTraversable t where traverseNE :: SemiApplicative f => (a -> f b) -> t a -> f (t b) ```
[^naming-issue]: https://github.com/ekmett/semigroupoids/issues/26 [^refComment1]: https://github.com/ekmett/semigroupoids/issues/26#issuecomment-395565772 [^refComment2]: https://github.com/ekmett/semigroupoids/issues/26#issuecomment-395950042 [^refComment3]: https://github.com/ekmett/semigroupoids/issues/26#issuecomment-398117218 [^bikeshedding]: https://mail.haskell.org/pipermail/libraries/2019-October/030036.html [^containersNEpatch]: https://github.com/haskell/containers/pull/616
Inefficiency of foldr1 ----------------------
In another `semigroupoids` issue[^foldr1-issue], the inefficiency of `foldr1` is highlighted.
The proposal includes functions like:
```haskell 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:
```haskell foldr1 = foldr1Map id ```
Another option is to have function arguments flipped:
```haskell 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.
[^foldr1-issue]: https://github.com/ekmett/semigroupoids/issues/77
Compatibility & migration -------------------------
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[^hackageFoldable] by M Farkas-Dyck (cc'd). He kindly offered to donate the name if this proposal is accepted (with foldable1 name).[^refDonate]
`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`[^bifunctorsPatch] and `semigroupoids`[^semigroupoidsPatch] with
[^hackageFoldable]: https://hackage.haskell.org/package/foldable1 [^refDonate]: https://mail.haskell.org/pipermail/libraries/2019-October/030029.html [^bifunctorsPatch]: https://github.com/ekmett/bifunctors/pull/78 [^semigroupoidsPatch]: https://github.com/ekmett/semigroupoids/pull/87
Unresolved questions --------------------
- 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.
Appendix: Foldable1 synopsis ----------------------------
Module name: `Data.Foldable1` and `Data.Bifoldable1`
https://oleg.fi/haddocks/foldable1/Data-Foldable1.html
```haskell 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 ```
Appendix: Semifoldable synopsis -------------------------------
Module names`: `Data.Semifoldable` and `Data.Semibifoldable`
https://oleg.fi/haddocks/semifoldable/
```haskell 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 ```
Appendix: NonEmptyFoldable synopsis -------------------------------
Module name: `Data.Foldable.NonEmpty` and `Data.Bifoldable.NonEmpty`
```haskell 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 ```