<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<p>This is second revision of proposal. Thanks to all commented so
far.<br>
<br>
The changes from the first revision are<br>
<br>
- Remove `toNonEmpty` from MINIMAL pragma (implementation driven,
it seems to be a bad idea to go via toNonEmpty)<br>
- Add `Semifoldable` naming-scheme alternative (see sections at
the end)<br>
- Discuss `Bifoldable1`<br>
- Discuss `foldr1` inefficiency<br>
- Migration plan for `tagged` and `bifunctors`<br>
- PoC patch to `semigroupoids`<br>
- `foldable1` package has doctest examples, and a test-suite<br>
- more members are manually implemented (and tested)<br>
- haddocks regenerated to reflect current state of
`foldable1`-package<br>
<br>
I set the deadline for discussion in two weeks, ending Monday
2019-11-04.</p>
<p>- Oleg<br>
</p>
<p><br>
Add Foldable1 to base<br>
=====================<br>
<br>
Motivation<br>
----------<br>
<br>
It's regularly asked whether `Foldable1` could be added to `base`<br>
(e.g. on reddit[^ref1], there're also GHC issue[^ref2] and old<br>
phabricator diff[^ref3])<br>
Also there's work towards non-empty maps and sets[^ref4],<br>
which would benefit from `Foldable1`.<br>
Recently `nonempty-vector` was upload to Hackage as well[^refV].<br>
<br>
As commented on reddit, `Foldable1` could be added without any
pain<br>
to the `base` as it's pure addition - no modifications needed in<br>
existing modules.<br>
<br>
[^ref1]:
<a class="moz-txt-link-freetext" href="https://www.reddit.com/r/haskell/comments/6d0vgt/could_we_have_foldable1_and_traversable1_in_base/">https://www.reddit.com/r/haskell/comments/6d0vgt/could_we_have_foldable1_and_traversable1_in_base/</a><br>
[^ref2]: <a class="moz-txt-link-freetext" href="https://gitlab.haskell.org/ghc/ghc/issues/13573">https://gitlab.haskell.org/ghc/ghc/issues/13573</a><br>
[^ref3]: <a class="moz-txt-link-freetext" href="https://phabricator.haskell.org/D4812">https://phabricator.haskell.org/D4812</a><br>
[^ref4]: <a class="moz-txt-link-freetext" href="https://github.com/haskell/containers/pull/616">https://github.com/haskell/containers/pull/616</a><br>
[^refV]: <a class="moz-txt-link-freetext" href="https://hackage.haskell.org/package/nonempty-vector">https://hackage.haskell.org/package/nonempty-vector</a><br>
<br>
Changelog<br>
---------<br>
<br>
- Remove `toNonEmpty` from MINIMAL pragma<br>
- Add `Semifoldable` naming-scheme alternative (see sections at
the end)<br>
- Discuss `Bifoldable1`<br>
- Discuss `foldr1` inefficiency<br>
- Migration plan for `tagged` and `bifunctors`<br>
- PoC patch to `semigroupoids`<br>
- `foldable1` package has doctest examples, and a test-suite<br>
- more members are manually implemented (and tested)<br>
- haddocks regenerated to reflect current state of
`foldable1`-package<br>
<br>
Change: Foldable1<br>
-----------------<br>
<br>
The change exist as merge request[^ghcMR] on gitlab.haskell.org.<br>
However the more up to date version of a proposed module is
visible from<br>
haddocks on<br>
<br>
<a class="moz-txt-link-freetext" href="https://oleg.fi/haddocks/foldable1/Data-Foldable1.html">https://oleg.fi/haddocks/foldable1/Data-Foldable1.html</a><br>
<br>
or<br>
<br>
<a class="moz-txt-link-freetext" href="http://oleg.fi/haddocks/semifoldable/Data-Semifoldable.html">http://oleg.fi/haddocks/semifoldable/Data-Semifoldable.html</a><br>
<br>
Importantly, this change **doesn't change** anything in other
modules<br>
of `base`, except of adding a `Foldable` instance to
`Data.Complex`.<br>
In particular, `foldl1` and `foldr1` in `Data.Foldable` remain
partial, etc.<br>
<br>
My version of `Foldable1` class is big, so I'll comment the
motivation<br>
for each member<br>
<br>
```haskell<br>
class Foldable t => Foldable1 t where<br>
{-# MINIMAL foldMap1 | foldr1map #-}<br>
<br>
fold1 :: Semigroup m => t m -> m<br>
<br>
-- the defining member, like foldMap but only asking for
Semigroup<br>
foldMap1 :: Semigroup m => (a -> m) -> t a -> m<br>
<br>
-- strict foldMap1, cf foldMap'<br>
foldMap1' :: Semigroup m => (a -> m) -> t a -> m<br>
<br>
-- analogue of toList<br>
toNonEmpty :: t a -> NonEmpty a<br>
<br>
-- left&right, strict&non-strict folds<br>
foldr1 :: (a -> a -> a) -> t a -> a<br>
foldr1' :: (a -> a -> a) -> t a -> a<br>
foldl1 :: (a -> a -> a) -> t a -> a<br>
foldl1' :: (a -> a -> a) -> t a -> a<br>
<br>
-- these can have efficient implementation for NonEmptySet<br>
maximum1 :: forall a. Ord a => t a -> a<br>
minimum1 :: forall a. Ord a => t a -> a<br>
<br>
-- head1 have efficient implementation for NonEmpty and Tree<br>
-- last1 for symmetry<br>
head1 :: t a -> a<br>
last1 :: t a -> a<br>
<br>
-- fold variants with premap.<br>
-- Without this map, we cannot implement foldl using foldr
etc.<br>
-- These will probably change, see foldr1 inefficiency section<br>
foldr1Map :: (a -> b) -> (b -> b -> b) -> t a
-> b<br>
foldl1'Map :: (a -> b) -> (b -> b -> b) -> t a
-> b<br>
foldl1Map :: (a -> b) -> (b -> b -> b) -> t a
-> b<br>
foldr1'Map :: (a -> b) -> (b -> b -> b) -> t a
-> b<br>
```<br>
<br>
The merge request also adds instances for everything non-empty in
`base`.<br>
<br>
I propose the `Data.Foldable1` as the module name (an alternative<br>
`Data.Semifoldable`).<br>
`semigroupoids`[^semigroupoids] uses `Data.Semigroup.Foldable`,<br>
but it's confusing; and using different name could help migration.<br>
<br>
Additionally, the `Data.Foldable1` module contains five top-level
functions,<br>
which should be self-explanatory:<br>
<br>
```haskell<br>
intercalate1 :: (Foldable1 t, Semigroup m) => m -> t m ->
m<br>
<br>
foldrM1 :: (Foldable1 t, Monad m) => (a -> a -> m a)
-> t a -> m a<br>
foldlM1 :: (Foldable1 t, Monad m) => (a -> a -> m a)
-> t a -> m a<br>
<br>
maximum1By :: Foldable1 t => (a -> a -> Ordering) -> t
a -> a<br>
minimum1By :: Foldable1 t => (a -> a -> Ordering) -> t
a -> a<br>
```<br>
<br>
This is less than in `Data.Semigroup.Foldable`[^d.s.foldable], as
other<br>
top-level definitions doesn't make sense without bringing in the
`Apply`<br>
type-class. For example:<br>
<br>
```haskell<br>
-- needs Apply, not in Data.Foldable1<br>
traverse1_ :: (Foldable1 t, Apply f) => (a -> f b) -> t a
-> f ()<br>
```<br>
<br>
And if we relax `Apply` to `Applicative`, we get `traverse_`.<br>
Bringing `Apply` into `base` is out-of-scope of this proposal.<br>
<br>
[^ghcMR]: <a class="moz-txt-link-freetext" href="https://gitlab.haskell.org/ghc/ghc/merge_requests/1973">https://gitlab.haskell.org/ghc/ghc/merge_requests/1973</a><br>
[^semigroupoids]:
<a class="moz-txt-link-freetext" href="https://hackage.haskell.org/package/semigroupoids">https://hackage.haskell.org/package/semigroupoids</a><br>
[^d.s.foldable]:
<a class="moz-txt-link-freetext" href="https://hackage.haskell.org/package/semigroupoids-5.3.3/docs/Data-Semigroup-Foldable-Class.html">https://hackage.haskell.org/package/semigroupoids-5.3.3/docs/Data-Semigroup-Foldable-Class.html</a><br>
<br>
Bifoldable1<br>
-----------<br>
<br>
`Bifoldable` class have `Bifoldable1` subclass in `semigroupoids`.<br>
We could move that class into `base` as well, but it's not
strictly necessary,<br>
as it can be done later too.<br>
<br>
However, `Bifoldable1` should migrate to `bifunctors` package.<br>
This is discussed in "Compatibility & migration" section.<br>
<br>
Name controversy<br>
----------------<br>
<br>
Adding `Foldable1` is considered controversial.<br>
Library submissions guidelines say:<br>
<br>
> Adding a new, useful function under a clear name is probably
not controversial<br>
<br>
Yet in this case, there doesn't seem to be clear names.<br>
The alternative naming scheme is discussed on `semigroupoids`
issue<br>
tracker[^naming-issue].<br>
<br>
In a comment nickname chessai list a table of possible renamings,<br>
essentially dropping `1`-suffix and adding `semi`-
prefix.[^refComment1]<br>
Following comments brainstorm more ideas like:<br>
<br>
- all the functions that aren't actual typeclass methods could
possibly just<br>
keep the `1` suffix<br>
- i'm struggling against consistency here, because some functions
sound great<br>
with `semi`- as their prefix, and some sound bad<br>
<br>
The bad sounding names are `semihead`, `semilast`, `semimaximum`
and<br>
`semiminimum`. In theory they could be prefixless and suffixless,<br>
i.e. plain `head`, `last`, `maximum`, and `minimum`. However,<br>
I consider that naming more controversial, as it clashes with
`Prelude`<br>
names, even one can argue that `Semifoldable` members should<br>
eventually replace them. Luckily, the names can be changed,<br>
if they are on the way into `Prelude`.<br>
<br>
A variation of this, is to use bare `s` as prefix to the members,
i.e.<br>
`sfoldMap`, `sfoldr`. It's shorter, but maybe too subtle?<br>
<br>
One justification to not use 1-suffix name is[^refComment2]<br>
<br>
> The 1 is still in conflict, but requires more Eq1, etc like
classes to<br>
> define. e.g. Monoid1 for taking a monoid to a monoid, then
Foldable1<br>
> consistently in that nomenclature would let you reduce
through a Monoid1.<br>
<br>
Also using qualified imports would prevent `Foldable1` class to be
ever<br>
imported unqualified[^refComment3]:<br>
<br>
> The haddocks for Semi.Monad being a superclass of Monad
someday in the far<br>
> flung future would be frankly pretty awful to read, and would
ensure that<br>
> they could never move into Prelude, forever dooming them to a
second class<br>
> existence.<br>
<br>
And finally, trying to unify `Foldable` with `Foldable1` into
single class<br>
using type families / some hackery requires
`QuantifiedConstraints` at the<br>
very least. That's not a realistic option to current, essentially
a Haskell98<br>
formulation.<br>
<br>
[^naming-issue]: <a class="moz-txt-link-freetext" href="https://github.com/ekmett/semigroupoids/issues/26">https://github.com/ekmett/semigroupoids/issues/26</a><br>
[^refComment1]:
<a class="moz-txt-link-freetext" href="https://github.com/ekmett/semigroupoids/issues/26#issuecomment-395565772">https://github.com/ekmett/semigroupoids/issues/26#issuecomment-395565772</a><br>
[^refComment2]:
<a class="moz-txt-link-freetext" href="https://github.com/ekmett/semigroupoids/issues/26#issuecomment-395950042">https://github.com/ekmett/semigroupoids/issues/26#issuecomment-395950042</a><br>
[^refComment3]:
<a class="moz-txt-link-freetext" href="https://github.com/ekmett/semigroupoids/issues/26#issuecomment-398117218">https://github.com/ekmett/semigroupoids/issues/26#issuecomment-398117218</a><br>
<br>
Inefficiency of foldr1<br>
----------------------<br>
<br>
In another `semigroupoids` issue[^foldr1-issue],<br>
the inefficiency of `foldr1` is highlighted.<br>
<br>
My original proposal included functions of the type:<br>
<br>
```haskell<br>
foldr1Map :: (a -> b) -> (b -> b -> b) -> t a ->
b<br>
```<br>
<br>
Yet, Andrew Martin points out, another better type:<br>
<br>
```haskell<br>
foldr1Map :: (a -> b) -> (a -> b -> b) -> t a ->
b<br>
```<br>
<br>
This helps differentiate between foldr and foldl variants,<br>
and also simplifies some implementation bits (to my surprise).<br>
I'm in favour of this change.<br>
<br>
The order of function arguments is chosen so:<br>
<br>
```haskell<br>
foldr1 = foldr1Map id<br>
```<br>
<br>
This variant is implemented in a PR in my repository[^foldrPR].<br>
But not yet incorporated into this proposal.<br>
<br>
[^foldr1-issue]: <a class="moz-txt-link-freetext" href="https://github.com/ekmett/semigroupoids/issues/77">https://github.com/ekmett/semigroupoids/issues/77</a><br>
[^foldrPR]: <a class="moz-txt-link-freetext" href="https://github.com/phadej/foldable1/pull/7">https://github.com/phadej/foldable1/pull/7</a><br>
<br>
Compatibility & migration<br>
-------------------------<br>
<br>
I drafted a compatibility package `foldable1`:<br>
<br>
- GitHub repository: <a class="moz-txt-link-freetext" href="https://github.com/phadej/foldable1">https://github.com/phadej/foldable1</a><br>
- haddocks: <a class="moz-txt-link-freetext" href="https://oleg.fi/haddocks/foldable1/">https://oleg.fi/haddocks/foldable1/</a><br>
- Semifoldable variant: <a class="moz-txt-link-freetext" href="https://github.com/phadej/foldable1/pull/5">https://github.com/phadej/foldable1/pull/5</a><br>
- its haddocks: <a class="moz-txt-link-freetext" href="https://oleg.fi/haddocks/semifoldable/">https://oleg.fi/haddocks/semifoldable/</a><br>
<br>
which I hope could be maintained under github.com/haskell
organization.<br>
I can act as a maintainer, with a hope that there won't be a lot<br>
of changes happening in `Data.Foldable1`.<br>
<br>
To my surprise, there's already a package with this name on<br>
Hackage[^hackageFoldable] by<br>
M Farkas-Dyck (cc'd). He kindly offered to donate the name if<br>
this proposal is accepted (with foldable1 name).[^refDonate]<br>
<br>
`Data.Foldable1` contains also instances for `Lift`, `Backwards`
and `Reverse`,<br>
and other data types from `transformers`. Perfectly, the
`transformers` bundled<br>
with GHC with this change would implement the instances as well.
This change<br>
should propage to `transformers-compat` too.<br>
<br>
Similarly, `containers` would have an instance for `Tree` (and
non-empty<br>
`Set` and `Map` when they are added).<br>
<br>
<br>
Other packages would be compat'd as follows:<br>
- `foldable1` would provide instances for `Tagged` from `tagged`<br>
- `Bifoldable1` class would migrate to `bifunctors`<br>
<br>
This is because current dependencies are:<br>
<br>
```<br>
semigroups <- tagged <- bifunctors <- semigroupoids<br>
```<br>
<br>
and `foldable1` would be more natural between `tagged` and
`bifunctors`:<br>
<br>
```<br>
semigroups <- tagged <- foldable1 <- bifunctors <-
semigroupoids<br>
```<br>
<br>
`foldable` have to be before `bifunctors` in the dependency tree,<br>
as `Bifoldable1` instances of some `Bifunctor`s need `Foldable1`
class.<br>
<br>
I also drafted a PR for compatibility patch to
`semigroupoids`[^semigroupoidsPatch]<br>
including `Foldable1` part; but doesn't include <br>
migrating `Bifoldable, nor other proposed renaming.<br>
<br>
The rest of renamings is straight-forward should be
straight-forward to do.<br>
Migration `Bifoldable` would be a lot easier, when the `foldable1`
package<br>
interface is stabilized.<br>
<br>
[^hackageFoldable]: <a class="moz-txt-link-freetext" href="https://hackage.haskell.org/package/foldable1">https://hackage.haskell.org/package/foldable1</a><br>
[^refDonate]:
<a class="moz-txt-link-freetext" href="https://mail.haskell.org/pipermail/libraries/2019-October/030029.html">https://mail.haskell.org/pipermail/libraries/2019-October/030029.html</a><br>
[^semigroupoidsPatch]:
<a class="moz-txt-link-freetext" href="https://github.com/ekmett/semigroupoids/pull/87">https://github.com/ekmett/semigroupoids/pull/87</a><br>
<br>
Unresolved questions<br>
--------------------<br>
<br>
- The names? Foldable1 or Semifoldable, members?<br>
- Bifoldable1 or Bisemifoldable (or Semibifoldable)?<br>
- Members: `semifoldMap` or just `sfoldMap`?<br>
See following Foldable1 and Semifoldable sections for synopsis<br>
- Which type signature `foldr1Map` / `semifoldr1Map` should have
(`a -> b -> b` is IMO better)<br>
- GHC-8.10 freeze is quite soon, is targeting GHC-8.12/base-4.15
more realistic.<br>
Note: this technically is a non-breaking change in `base`,<br>
so could be bundled with GHC-8.10.2, but I think sticking to
major would be<br>
preferable by GHC HQ.<br>
<br>
Appendix: Foldable1 synopsis<br>
----------------------------<br>
<br>
<a class="moz-txt-link-freetext" href="https://oleg.fi/haddocks/foldable1/Data-Foldable1.html">https://oleg.fi/haddocks/foldable1/Data-Foldable1.html</a><br>
<br>
```haskell<br>
class Foldable t => Foldable1 t where<br>
fold1 :: Semigroup m => t m -> m<br>
foldMap1 :: Semigroup m => (a -> m) -> t a -> m<br>
foldMap1' :: Semigroup m => (a -> m) -> t a -> m<br>
<br>
foldr1 :: (a -> a -> a) -> t a -> a<br>
foldr1' :: (a -> a -> a) -> t a -> a<br>
foldl1 :: (a -> a -> a) -> t a -> a<br>
foldl1' :: (a -> a -> a) -> t a -> a<br>
<br>
toNonEmpty :: t a -> NonEmpty a<br>
<br>
maximum1 :: forall a. Ord a => t a -> a<br>
minimum1 :: forall a. Ord a => t a -> a<br>
head1 :: t a -> a<br>
last1 :: t a -> a<br>
<br>
foldr1Map :: (a -> b) -> (b -> b -> b) -> t a
-> b<br>
foldl1'Map :: (a -> b) -> (b -> b -> b) -> t a
-> b<br>
foldl1Map :: (a -> b) -> (b -> b -> b) -> t a
-> b<br>
foldr1'Map :: (a -> b) -> (b -> b -> b) -> t a
-> b<br>
<br>
intercalate1 :: (Foldable1 t, Semigroup m) => m -> t m ->
m<br>
foldrM1 :: (Foldable1 t, Monad m) => (a -> a -> m a)
-> t a -> m a<br>
foldlM1 :: (Foldable1 t, Monad m) => (a -> a -> m a)
-> t a -> m a<br>
maximum1By :: Foldable1 t => (a -> a -> Ordering) ->
t a -> a<br>
minimum1By :: Foldable1 t => (a -> a -> Ordering) ->
t a -> a<br>
```<br>
<br>
Appendix: Semifoldable synopsis<br>
-------------------------------<br>
<br>
<a class="moz-txt-link-freetext" href="https://oleg.fi/haddocks/semifoldable/">https://oleg.fi/haddocks/semifoldable/</a><br>
<br>
```haskell<br>
class Foldable t => Semifoldable t where<br>
semifold :: Semigroup m => t m -> m<br>
semifoldMap :: Semigroup m => (a -> m) -> t a -> m<br>
semifoldMap' :: Semigroup m => (a -> m) -> t a -> m<br>
<br>
semifoldr :: (a -> a -> a) -> t a -> a<br>
semifoldr' :: (a -> a -> a) -> t a -> a<br>
semifoldl :: (a -> a -> a) -> t a -> a<br>
semifoldl' :: (a -> a -> a) -> t a -> a<br>
<br>
toNonEmpty :: t a -> NonEmpty a<br>
<br>
semimaximum :: forall a. Ord a => t a -> a<br>
semiminimum :: forall a. Ord a => t a -> a<br>
semihead :: t a -> a<br>
semilast :: t a -> a<br>
<br>
semifoldrMap :: (a -> b) -> (b -> b -> b) -> t a
-> b<br>
semifoldl'Map :: (a -> b) -> (b -> b -> b) -> t a
-> b<br>
semifoldlMap :: (a -> b) -> (b -> b -> b) -> t a
-> b<br>
semifoldr'Map :: (a -> b) -> (b -> b -> b) -> t a
-> b<br>
<br>
intercalate1 :: (Semifoldable t, Semigroup m) => m -> t m
-> m<br>
foldrM1 :: (Semifoldable t, Monad m) => (a -> a ->
m a) -> t a -> m a<br>
foldlM1 :: (Semifoldable t, Monad m) => (a -> a ->
m a) -> t a -> m a<br>
semimaximumBy :: Semifoldable t => (a -> a -> Ordering)
-> t a -> a<br>
semiminimumBy :: Semifoldable t => (a -> a -> Ordering)
-> t a -> a<br>
<br>
-- or alternatively<br>
semiintercalate<br>
semifoldrM<br>
semifoldlM<br>
```<br>
<br>
Appendix: Alternative foldr1Map<br>
-------------------------------<br>
<br>
```haskell<br>
class Foldable t => Foldable1 t where<br>
fold1 :: Semigroup m => t m -> m<br>
foldMap1 :: Semigroup m => (a -> m) -> t a -> m<br>
foldMap1' :: Semigroup m => (a -> m) -> t a -> m<br>
<br>
foldr1 :: (a -> a -> a) -> t a -> a<br>
foldr1' :: (a -> a -> a) -> t a -> a<br>
foldl1 :: (a -> a -> a) -> t a -> a<br>
foldl1' :: (a -> a -> a) -> t a -> a<br>
<br>
toNonEmpty :: t a -> NonEmpty a<br>
<br>
maximum1 :: forall a. Ord a => t a -> a<br>
minimum1 :: forall a. Ord a => t a -> a<br>
head1 :: t a -> a<br>
last1 :: t a -> a<br>
<br>
-- These four are changed compared to Foldable1 synopsis<br>
foldr1Map :: (a -> b) -> (a -> b -> b) -> t a
-> b<br>
foldl1'Map :: (a -> b) -> (b -> a -> b) -> t a
-> b<br>
foldl1Map :: (a -> b) -> (b -> a -> b) -> t a
-> b<br>
foldr1'Map :: (a -> b) -> (a -> b -> b) -> t a
-> b<br>
<br>
intercalate1 :: (Foldable1 t, Semigroup m) => m -> t m ->
m<br>
foldrM1 :: (Foldable1 t, Monad m) => (a -> a -> m a)
-> t a -> m a<br>
foldlM1 :: (Foldable1 t, Monad m) => (a -> a -> m a)
-> t a -> m a<br>
maximum1By :: Foldable1 t => (a -> a -> Ordering) ->
t a -> a<br>
minimum1By :: Foldable1 t => (a -> a -> Ordering) ->
t a -> a<br>
```<br>
<br>
</p>
<blockquote type="cite"
cite="mid:431b2ab2-d7df-d7f2-602d-15bcebdd36ed@iki.fi">
<fieldset class="mimeAttachmentHeader"></fieldset>
<pre class="moz-quote-pre" wrap="">_______________________________________________
Libraries mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Libraries@haskell.org">Libraries@haskell.org</a>
<a class="moz-txt-link-freetext" href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a>
</pre>
</blockquote>
</body>
</html>