Add Data.Foldable1 to base
Oleg Grenrus
oleg.grenrus at iki.fi
Tue Oct 22 17:07:03 UTC 2019
To keep committee well equipped to make final decision
- Show support or disapproval for both proposed naming schemes
(Foldable1 and Semifoldable)
- If you don't like either, propose new ones
Otherwise these proposal will linger forever "because naming is hard".
We can do better.
To be explicit, I myself is fine with both naming schemes, and either
using semi- or just single s- prefix (e.g. sfoldMap).
I encourage everyone to brainstorm the names. The proposal mentions some
reasons why Foldable1 is not considered good choice. So if you think
Semifoldable is not optimal either, now is good opportunity to make
history, by inventing a "contravariant" variant of Semi- prefix.
- Oleg
On 22.10.2019 17.51, John Cotton Ericson wrote:
>
> Echoing Keith's point, "semi" to me means a weaker algebra; i.e. a
> super-class. Foldable => Semifoldable is thus totally wrong,
> "Semifoldable" is the sub-class. In particular. The Monoid and
> Semigroup constraints on their respective methods further show that
> the fold class hierarchy is *contravariant* with respect to the binary
> operator class hierarchy. Putting semi-* with semi-* only makes sense
> for something covariant (e.g. the if methods *returned* `Dict
> (Semigroup a)` etc).
>
> Semimonad and Semiapplicative are fine with me (I don't really care,
> not worth fighting one way or the other) but strong -1 on Semifoldable.
>
> John
On 21.10.2019 0.31, Oleg Grenrus wrote:
>
> This is second revision of proposal. Thanks to all commented so far.
>
> The changes from the first revision are
>
> - Remove `toNonEmpty` from MINIMAL pragma (implementation driven, it
> seems to be a bad idea to go via toNonEmpty)
> - 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)
> - haddocks regenerated to reflect current state of `foldable1`-package
>
> I set the deadline for discussion in two weeks, ending Monday 2019-11-04.
>
> - Oleg
>
>
> Add Foldable1 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 upload 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.
>
> [^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
> ---------
>
> - 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)
> - haddocks regenerated to reflect current state of `foldable1`-package
>
> 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 :: forall a. Ord a => t a -> a
> minimum1 :: forall a. 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.
> -- These will probably change, see foldr1 inefficiency section
> foldr1Map :: (a -> b) -> (b -> b -> b) -> t a -> b
> foldl1'Map :: (a -> b) -> (b -> b -> b) -> t a -> b
> foldl1Map :: (a -> b) -> (b -> b -> b) -> t a -> b
> foldr1'Map :: (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 five 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
>
> 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 could move that class into `base` as well, but it's not strictly
> necessary,
> as it can be done later too.
>
> However, `Bifoldable1` should migrate to `bifunctors` package.
> This is discussed in "Compatibility & migration" section.
>
> 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.
>
> [^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
>
> Inefficiency of foldr1
> ----------------------
>
> In another `semigroupoids` issue[^foldr1-issue],
> the inefficiency of `foldr1` is highlighted.
>
> My original proposal included functions of the type:
>
> ```haskell
> foldr1Map :: (a -> b) -> (b -> b -> b) -> t a -> b
> ```
>
> Yet, Andrew Martin points out, another better type:
>
> ```haskell
> foldr1Map :: (a -> b) -> (a -> b -> b) -> t a -> b
> ```
>
> This helps differentiate between foldr and foldl variants,
> and also simplifies some implementation bits (to my surprise).
> I'm in favour of this change.
>
> The order of function arguments is chosen so:
>
> ```haskell
> foldr1 = foldr1Map id
> ```
>
> This variant is implemented in a PR in my repository[^foldrPR].
> But not yet incorporated into this proposal.
>
> [^foldr1-issue]: https://github.com/ekmett/semigroupoids/issues/77
> [^foldrPR]: https://github.com/phadej/foldable1/pull/7
>
> 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 propage 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 `Bifunctor`s need `Foldable1` class.
>
> I also drafted a PR for compatibility patch to
> `semigroupoids`[^semigroupoidsPatch]
> including `Foldable1` part; but doesn't include
> migrating `Bifoldable, nor other proposed renaming.
>
> The rest of renamings is straight-forward should be straight-forward
> to do.
> Migration `Bifoldable` would be a lot easier, when the `foldable1` package
> interface is stabilized.
>
> [^hackageFoldable]: https://hackage.haskell.org/package/foldable1
> [^refDonate]:
> https://mail.haskell.org/pipermail/libraries/2019-October/030029.html
> [^semigroupoidsPatch]: https://github.com/ekmett/semigroupoids/pull/87
>
> Unresolved questions
> --------------------
>
> - The names? Foldable1 or Semifoldable, members?
> - Bifoldable1 or Bisemifoldable (or Semibifoldable)?
> - Members: `semifoldMap` or just `sfoldMap`?
> See following Foldable1 and Semifoldable sections for synopsis
> - Which type signature `foldr1Map` / `semifoldr1Map` should have (`a
> -> b -> b` is IMO better)
> - 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
> ----------------------------
>
> 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 :: forall a. Ord a => t a -> a
> minimum1 :: forall a. Ord a => t a -> a
> head1 :: t a -> a
> last1 :: t a -> a
>
> foldr1Map :: (a -> b) -> (b -> b -> b) -> t a -> b
> foldl1'Map :: (a -> b) -> (b -> b -> b) -> t a -> b
> foldl1Map :: (a -> b) -> (b -> b -> b) -> t a -> b
> foldr1'Map :: (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
> maximum1By :: Foldable1 t => (a -> a -> Ordering) -> t a -> a
> minimum1By :: Foldable1 t => (a -> a -> Ordering) -> t a -> a
> ```
>
> Appendix: Semifoldable synopsis
> -------------------------------
>
> 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 :: forall a. Ord a => t a -> a
> semiminimum :: forall a. 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
> foldrM1 :: (Semifoldable t, Monad m) => (a -> a -> m a) -> t a
> -> m a
> foldlM1 :: (Semifoldable t, Monad m) => (a -> a -> m a) -> t a
> -> m a
> semimaximumBy :: Semifoldable t => (a -> a -> Ordering) -> t a -> a
> semiminimumBy :: Semifoldable t => (a -> a -> Ordering) -> t a -> a
>
> -- or alternatively
> semiintercalate
> semifoldrM
> semifoldlM
> ```
>
> Appendix: Alternative foldr1Map
> -------------------------------
>
> ```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 :: forall a. Ord a => t a -> a
> minimum1 :: forall a. Ord a => t a -> a
> head1 :: t a -> a
> last1 :: t a -> a
>
> -- These four are changed compared to Foldable1 synopsis
> foldr1Map :: (a -> b) -> (a -> b -> b) -> t a -> b
> foldl1'Map :: (a -> b) -> (b -> a -> b) -> t a -> b
> foldl1Map :: (a -> b) -> (b -> a -> b) -> t a -> b
> foldr1'Map :: (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
> maximum1By :: Foldable1 t => (a -> a -> Ordering) -> t a -> a
> minimum1By :: Foldable1 t => (a -> a -> Ordering) -> t a -> a
> ```
>
>> _______________________________________________
>> Libraries mailing list
>> Libraries at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20191022/839170e8/attachment.html>
More information about the Libraries
mailing list