Add Data.Foldable1 to base
Oleg Grenrus
oleg.grenrus at iki.fi
Tue Nov 19 21:34:17 UTC 2019
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_traversable1_in_base/>
> [^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
>
> > <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
>
> ```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-Foldable-Class.html>
>
> 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
> ```
More information about the Libraries
mailing list