Add Data.Foldable1 to base

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

Add Data.Foldable1 to base

Oleg Grenrus
I propose adding `Foldable1` type-class into `base1`.

Add Foldable1
=============


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

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

Change
------

The change exist as merge request[^ref4] on gitlab.haskell.org.

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 | toNonEmpty | foldr1map #-}

    -- the defining member, like foldMap but only asking for Semigroup
    foldMap1 :: Semigroup m => (a -> m) -> t a -> m

    fold1 :: Semigroup m => t m -> 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.
    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.
`semigroupoids`[^ref6] uses `Data.Semigroup.Foldable`,
but it's confusing; and using different name could help migration.

The 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`[^ref9],
as without `Apply` they don't make sense.
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_`.
 
[^ref5]: https://gitlab.haskell.org/ghc/ghc/merge_requests/1973
[^ref9]:
https://hackage.haskell.org/package/semigroupoids-5.3.3/docs/Data-Semigroup-Foldable-Class.html

[^ref5]: https://gitlab.haskell.org/ghc/ghc/merge_requests/1973

Compatibility & migration
-------------------------

I drafted a compatibility package `foldable1` (github[^ref6],
haddocks[^ref7]),
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[^ref8] by
M Farkas-Dyck (cc'd). I hope they would donate the name to Haskell.org /
CLC;
the package won't have any other good use when `Data.Foldable1` is in
`base`,
then act as a compat package.

`Data.Foldable1` contains also instances for `Lift`, `Backwards` and
`Reverse`
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).

`semigroupoids` would need a bit of work, to depend on `foldable1`,
yet the public changes can be kept quite minimal.
I don't think that anything in reverse dependencies of `lens` will be
broken by
this change, if "new" `Foldable1` is re-exported from `semigroupoids`'
`Data.Semigroup.Foldable`[^ref9]

Other "compat" packages -- like `tagged`, `bifunctors` -- have to be
dealt with
case by case. For example whether they should depend on `foldable1` or
other way around.

[^ref6]: https://github.com/phadej/foldable1
[^ref7]: https://oleg.fi/haddocks/foldable1/
[^ref8]: https://hackage.haskell.org/package/foldable1
[^ref9]:
https://hackage.haskell.org/package/semigroupoids-5.3.3/docs/Data-Semigroup-Foldable-Class.html

Unresolved questions
--------------------

- Should we add `Bifoldable1` too. That should be trivial.
- GHC-8.10 freeze is quite soon, is targeting GHC-8.12/base-4.15 more
realistic?



_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Add Data.Foldable1 to base

Dmitrii Kovanikov
I support this change and I would love to have `Foldable1` in the `base` as well. I find it so useful that we even have it in our alternative prelude called `relude`:


I would love to reexport this typeclass by default from `base` instead of maintaining one more `Extra.*` module in `relude`. However, at this point, I like the implementation in `relude` more because:

1. It has usage examples tested with `doctest`.
2. Implements (almost) each function manually and uses {-# INLINE #-} pragmas for better performance.
3. In the next release, we're also going to add custom type errors of `Foldable1` instances for data types like ordinary lists to improve UX.

These improvements don't rely on anything `relude`-specific and can be done in `base` as well.

On Thu, Oct 17, 2019 at 5:43 PM Oleg Grenrus <[hidden email]> wrote:
I propose adding `Foldable1` type-class into `base1`.

Add Foldable1
=============


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

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

Change
------

The change exist as merge request[^ref4] on gitlab.haskell.org.

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 | toNonEmpty | foldr1map #-}

    -- the defining member, like foldMap but only asking for Semigroup
    foldMap1 :: Semigroup m => (a -> m) -> t a -> m

    fold1 :: Semigroup m => t m -> 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.
    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.
`semigroupoids`[^ref6] uses `Data.Semigroup.Foldable`,
but it's confusing; and using different name could help migration.

The 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`[^ref9],
as without `Apply` they don't make sense.
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_`.
 
[^ref5]: https://gitlab.haskell.org/ghc/ghc/merge_requests/1973
[^ref9]:
https://hackage.haskell.org/package/semigroupoids-5.3.3/docs/Data-Semigroup-Foldable-Class.html

[^ref5]: https://gitlab.haskell.org/ghc/ghc/merge_requests/1973

Compatibility & migration
-------------------------

I drafted a compatibility package `foldable1` (github[^ref6],
haddocks[^ref7]),
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[^ref8] by
M Farkas-Dyck (cc'd). I hope they would donate the name to Haskell.org /
CLC;
the package won't have any other good use when `Data.Foldable1` is in
`base`,
then act as a compat package.

`Data.Foldable1` contains also instances for `Lift`, `Backwards` and
`Reverse`
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).

`semigroupoids` would need a bit of work, to depend on `foldable1`,
yet the public changes can be kept quite minimal.
I don't think that anything in reverse dependencies of `lens` will be
broken by
this change, if "new" `Foldable1` is re-exported from `semigroupoids`'
`Data.Semigroup.Foldable`[^ref9]

Other "compat" packages -- like `tagged`, `bifunctors` -- have to be
dealt with
case by case. For example whether they should depend on `foldable1` or
other way around.

[^ref6]: https://github.com/phadej/foldable1
[^ref7]: https://oleg.fi/haddocks/foldable1/
[^ref8]: https://hackage.haskell.org/package/foldable1
[^ref9]:
https://hackage.haskell.org/package/semigroupoids-5.3.3/docs/Data-Semigroup-Foldable-Class.html

Unresolved questions
--------------------

- Should we add `Bifoldable1` too. That should be trivial.
- GHC-8.10 freeze is quite soon, is targeting GHC-8.12/base-4.15 more
realistic?


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add Data.Foldable1 to base

Oleg Grenrus

Thanks for the support and comments Dmitrii.

1. I can add usage examples, that's no brainer.
2. Yes, implementing selected members manually can help, that's the point of having a lot of members, and not bare foldMap1.
   - Yet I hope that is not a blocker
   - This may be motivated by GHC.Generics, but I don't see instances in `relude`?
   -  Non trivial manual implementations should be backed up by some benchmark that shows it's worth having more code (which one have test, that it's coherent!).
       - That said, I'll add more manual members when I have test setup ready. E.g. `head1 :: Compose f g a -> a`, and for `Product` (and Generics variants).
   - {-# INLINE #-} everywhere doesn't imply more performance.
   - The `foldable1` package is simple enough playground to add benchmarks, there are some already.
3. There is no prior art of disallowing instances with TypeErrors in `base`, so I'm wont consider it here either.
   - That's worth an own separate library proposal

- Oleg

On 17.10.2019 19.26, Dmitrii Kovanikov wrote:
I support this change and I would love to have `Foldable1` in the `base` as well. I find it so useful that we even have it in our alternative prelude called `relude`:


I would love to reexport this typeclass by default from `base` instead of maintaining one more `Extra.*` module in `relude`. However, at this point, I like the implementation in `relude` more because:

1. It has usage examples tested with `doctest`.
2. Implements (almost) each function manually and uses {-# INLINE #-} pragmas for better performance.
3. In the next release, we're also going to add custom type errors of `Foldable1` instances for data types like ordinary lists to improve UX.

These improvements don't rely on anything `relude`-specific and can be done in `base` as well.

On Thu, Oct 17, 2019 at 5:43 PM Oleg Grenrus <[hidden email]> wrote:
I propose adding `Foldable1` type-class into `base1`.

Add Foldable1
=============


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

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

Change
------

The change exist as merge request[^ref4] on gitlab.haskell.org.

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 | toNonEmpty | foldr1map #-}

    -- the defining member, like foldMap but only asking for Semigroup
    foldMap1 :: Semigroup m => (a -> m) -> t a -> m

    fold1 :: Semigroup m => t m -> 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.
    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.
`semigroupoids`[^ref6] uses `Data.Semigroup.Foldable`,
but it's confusing; and using different name could help migration.

The 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`[^ref9],
as without `Apply` they don't make sense.
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_`.
 
[^ref5]: https://gitlab.haskell.org/ghc/ghc/merge_requests/1973
[^ref9]:
https://hackage.haskell.org/package/semigroupoids-5.3.3/docs/Data-Semigroup-Foldable-Class.html

[^ref5]: https://gitlab.haskell.org/ghc/ghc/merge_requests/1973

Compatibility & migration
-------------------------

I drafted a compatibility package `foldable1` (github[^ref6],
haddocks[^ref7]),
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[^ref8] by
M Farkas-Dyck (cc'd). I hope they would donate the name to Haskell.org /
CLC;
the package won't have any other good use when `Data.Foldable1` is in
`base`,
then act as a compat package.

`Data.Foldable1` contains also instances for `Lift`, `Backwards` and
`Reverse`
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).

`semigroupoids` would need a bit of work, to depend on `foldable1`,
yet the public changes can be kept quite minimal.
I don't think that anything in reverse dependencies of `lens` will be
broken by
this change, if "new" `Foldable1` is re-exported from `semigroupoids`'
`Data.Semigroup.Foldable`[^ref9]

Other "compat" packages -- like `tagged`, `bifunctors` -- have to be
dealt with
case by case. For example whether they should depend on `foldable1` or
other way around.

[^ref6]: https://github.com/phadej/foldable1
[^ref7]: https://oleg.fi/haddocks/foldable1/
[^ref8]: https://hackage.haskell.org/package/foldable1
[^ref9]:
https://hackage.haskell.org/package/semigroupoids-5.3.3/docs/Data-Semigroup-Foldable-Class.html

Unresolved questions
--------------------

- Should we add `Bifoldable1` too. That should be trivial.
- GHC-8.10 freeze is quite soon, is targeting GHC-8.12/base-4.15 more
realistic?


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add Data.Foldable1 to base

M Farkas-Dyck
In reply to this post by Oleg Grenrus
Yes, i am willing to donate the name "foldable1" once `Foldable1` is in "base".
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add Data.Foldable1 to base

Andrew Martin
In reply to this post by Oleg Grenrus
While I want this abstraction in base, I don’t want it there yet. There is an open issue on semigroupoids about renaming everything: https://github.com/ekmett/semigroupoids/issues/26

This needs to be handled before the abstraction is brought into base. Also, foldr1 is awful in common situations. See https://github.com/ekmett/semigroupoids/issues/77

The problem is that refinements of this abstraction seem to have stalled in semigroupoids, but these are desperately needed before the abstraction is brought into base.

Sent from my iPhone

On Oct 17, 2019, at 10:42 AM, Oleg Grenrus <[hidden email]> wrote:

I propose adding `Foldable1` type-class into `base1`.

Add Foldable1
=============


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

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

Change
------

The change exist as merge request[^ref4] on gitlab.haskell.org.

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 | toNonEmpty | foldr1map #-}

    -- the defining member, like foldMap but only asking for Semigroup
    foldMap1 :: Semigroup m => (a -> m) -> t a -> m

    fold1 :: Semigroup m => t m -> 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.
    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.
`semigroupoids`[^ref6] uses `Data.Semigroup.Foldable`,
but it's confusing; and using different name could help migration.

The 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`[^ref9],
as without `Apply` they don't make sense.
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_`.
 
[^ref5]: https://gitlab.haskell.org/ghc/ghc/merge_requests/1973
[^ref9]:
https://hackage.haskell.org/package/semigroupoids-5.3.3/docs/Data-Semigroup-Foldable-Class.html

[^ref5]: https://gitlab.haskell.org/ghc/ghc/merge_requests/1973

Compatibility & migration
-------------------------

I drafted a compatibility package `foldable1` (github[^ref6],
haddocks[^ref7]),
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[^ref8] by
M Farkas-Dyck (cc'd). I hope they would donate the name to Haskell.org /
CLC;
the package won't have any other good use when `Data.Foldable1` is in
`base`,
then act as a compat package.

`Data.Foldable1` contains also instances for `Lift`, `Backwards` and
`Reverse`
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).

`semigroupoids` would need a bit of work, to depend on `foldable1`,
yet the public changes can be kept quite minimal.
I don't think that anything in reverse dependencies of `lens` will be
broken by
this change, if "new" `Foldable1` is re-exported from `semigroupoids`'
`Data.Semigroup.Foldable`[^ref9]

Other "compat" packages -- like `tagged`, `bifunctors` -- have to be
dealt with
case by case. For example whether they should depend on `foldable1` or
other way around.

[^ref6]: https://github.com/phadej/foldable1
[^ref7]: https://oleg.fi/haddocks/foldable1/
[^ref8]: https://hackage.haskell.org/package/foldable1
[^ref9]:
https://hackage.haskell.org/package/semigroupoids-5.3.3/docs/Data-Semigroup-Foldable-Class.html

Unresolved questions
--------------------

- Should we add `Bifoldable1` too. That should be trivial.
- GHC-8.10 freeze is quite soon, is targeting GHC-8.12/base-4.15 more
realistic?


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add Data.Foldable1 to base

Edward Kmett-2
I’m happy to take patches to move things along in semigroupoids. My focus has been elsewhere, I admit.

-Edward

On Oct 17, 2019, at 5:03 PM, Andrew Martin <[hidden email]> wrote:

While I want this abstraction in base, I don’t want it there yet. There is an open issue on semigroupoids about renaming everything: https://github.com/ekmett/semigroupoids/issues/26

This needs to be handled before the abstraction is brought into base. Also, foldr1 is awful in common situations. See https://github.com/ekmett/semigroupoids/issues/77

The problem is that refinements of this abstraction seem to have stalled in semigroupoids, but these are desperately needed before the abstraction is brought into base.

Sent from my iPhone

On Oct 17, 2019, at 10:42 AM, Oleg Grenrus <[hidden email]> wrote:

I propose adding `Foldable1` type-class into `base1`.

Add Foldable1
=============


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

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

Change
------

The change exist as merge request[^ref4] on gitlab.haskell.org.

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 | toNonEmpty | foldr1map #-}

    -- the defining member, like foldMap but only asking for Semigroup
    foldMap1 :: Semigroup m => (a -> m) -> t a -> m

    fold1 :: Semigroup m => t m -> 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.
    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.
`semigroupoids`[^ref6] uses `Data.Semigroup.Foldable`,
but it's confusing; and using different name could help migration.

The 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`[^ref9],
as without `Apply` they don't make sense.
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_`.
 
[^ref5]: https://gitlab.haskell.org/ghc/ghc/merge_requests/1973
[^ref9]:
https://hackage.haskell.org/package/semigroupoids-5.3.3/docs/Data-Semigroup-Foldable-Class.html

[^ref5]: https://gitlab.haskell.org/ghc/ghc/merge_requests/1973

Compatibility & migration
-------------------------

I drafted a compatibility package `foldable1` (github[^ref6],
haddocks[^ref7]),
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[^ref8] by
M Farkas-Dyck (cc'd). I hope they would donate the name to Haskell.org /
CLC;
the package won't have any other good use when `Data.Foldable1` is in
`base`,
then act as a compat package.

`Data.Foldable1` contains also instances for `Lift`, `Backwards` and
`Reverse`
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).

`semigroupoids` would need a bit of work, to depend on `foldable1`,
yet the public changes can be kept quite minimal.
I don't think that anything in reverse dependencies of `lens` will be
broken by
this change, if "new" `Foldable1` is re-exported from `semigroupoids`'
`Data.Semigroup.Foldable`[^ref9]

Other "compat" packages -- like `tagged`, `bifunctors` -- have to be
dealt with
case by case. For example whether they should depend on `foldable1` or
other way around.

[^ref6]: https://github.com/phadej/foldable1
[^ref7]: https://oleg.fi/haddocks/foldable1/
[^ref8]: https://hackage.haskell.org/package/foldable1
[^ref9]:
https://hackage.haskell.org/package/semigroupoids-5.3.3/docs/Data-Semigroup-Foldable-Class.html

Unresolved questions
--------------------

- Should we add `Bifoldable1` too. That should be trivial.
- GHC-8.10 freeze is quite soon, is targeting GHC-8.12/base-4.15 more
realistic?


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add Data.Foldable1 to base

Oleg Grenrus

What is the proposed change in semigroupoids, I don't see any decisive conclusion comment. To get this going, I suggest limiting discussion to the Foldable1 only
and if after this proposal is accepted, extrapolate for the rest of `semigroupoids`.

So if someone can propose a concrete list how to rename symbols in https://oleg.fi/haddocks/foldable1/Data-Foldable1.html, I'll make a separate branch & haddock page.

Is the wanted renaming s/1//; s/^/semi/:

- Foldable1    -> Semifoldable
- fold1        -> semifold
- foldMap1     -> semifoldMap
- foldr1       -> semifoldr
- foldr1map    -> semifoldr1map
- toNonEmpty   -> toNonEmpty
- ...
- head1        -> semihead
- last1        -> semilast
- minimum1     -> semiminimum
- maximum1     -> semimaximum

- intercalate1 -> semiintercalate
- foldl1M      -> semifoldl
- ...
- maximum1By   -> semimaximumBy
- ...

I'm fine with this.
The head1/semihead are both silly, but the suffix was there to avoid name clash, so prefix is fine for that purpose too.

---

The synopsis of current state of proposed Data.Foldable1

module Data.Foldable1 where

class Foldable t => Foldable1 t
  fold1      :: (Foldable1 t, Semigroup m) => t m -> m
  foldMap1   :: (Foldable1 t, Semigroup m) => (a -> m) -> t a -> m
  foldMap1'  :: (Foldable1 t, Semigroup m) => (a -> m) -> t a -> m
  foldr1     :: Foldable1 t => (a -> a -> a) -> t a -> a
  foldr1'    :: Foldable1 t => (a -> a -> a) -> t a -> a
  foldl1     :: Foldable1 t => (a -> a -> a) -> t a -> a
  foldl1'    :: Foldable1 t => (a -> a -> a) -> t a -> a
  toNonEmpty :: Foldable1 t => t a -> NonEmpty a
  maximum1   :: forall a. (Foldable1 t, Ord a) => t a -> a
  minimum1   :: forall a. (Foldable1 t, Ord a) => t a -> a
  head1      :: Foldable1 t => t a -> a
  last1      :: Foldable1 t => t a -> a
  foldr1map  :: Foldable1 t => (a -> b) -> (b -> b -> b) -> t a -> b
  foldl1'map :: Foldable1 t => (a -> b) -> (b -> b -> b) -> t a -> b
  foldl1map  :: Foldable1 t => (a -> b) -> (b -> b -> b) -> t a -> b
  foldr1'map :: Foldable1 t => (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

- Oleg

On 18.10.2019 3.06, Edward Kmett wrote:
I’m happy to take patches to move things along in semigroupoids. My focus has been elsewhere, I admit.

-Edward

On Oct 17, 2019, at 5:03 PM, Andrew Martin [hidden email] wrote:

 While I want this abstraction in base, I don’t want it there yet. There is an open issue on semigroupoids about renaming everything: https://github.com/ekmett/semigroupoids/issues/26

This needs to be handled before the abstraction is brought into base. Also, foldr1 is awful in common situations. See https://github.com/ekmett/semigroupoids/issues/77

The problem is that refinements of this abstraction seem to have stalled in semigroupoids, but these are desperately needed before the abstraction is brought into base.

Sent from my iPhone

On Oct 17, 2019, at 10:42 AM, Oleg Grenrus <[hidden email]> wrote:

I propose adding `Foldable1` type-class into `base1`.

Add Foldable1
=============


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

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

Change
------

The change exist as merge request[^ref4] on gitlab.haskell.org.

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 | toNonEmpty | foldr1map #-}

    -- the defining member, like foldMap but only asking for Semigroup
    foldMap1 :: Semigroup m => (a -> m) -> t a -> m

    fold1 :: Semigroup m => t m -> 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.
    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.
`semigroupoids`[^ref6] uses `Data.Semigroup.Foldable`,
but it's confusing; and using different name could help migration.

The 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`[^ref9],
as without `Apply` they don't make sense.
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_`.
 
[^ref5]: https://gitlab.haskell.org/ghc/ghc/merge_requests/1973
[^ref9]:
https://hackage.haskell.org/package/semigroupoids-5.3.3/docs/Data-Semigroup-Foldable-Class.html

[^ref5]: https://gitlab.haskell.org/ghc/ghc/merge_requests/1973

Compatibility & migration
-------------------------

I drafted a compatibility package `foldable1` (github[^ref6],
haddocks[^ref7]),
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[^ref8] by
M Farkas-Dyck (cc'd). I hope they would donate the name to Haskell.org /
CLC;
the package won't have any other good use when `Data.Foldable1` is in
`base`,
then act as a compat package.

`Data.Foldable1` contains also instances for `Lift`, `Backwards` and
`Reverse`
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).

`semigroupoids` would need a bit of work, to depend on `foldable1`,
yet the public changes can be kept quite minimal.
I don't think that anything in reverse dependencies of `lens` will be
broken by
this change, if "new" `Foldable1` is re-exported from `semigroupoids`'
`Data.Semigroup.Foldable`[^ref9]

Other "compat" packages -- like `tagged`, `bifunctors` -- have to be
dealt with
case by case. For example whether they should depend on `foldable1` or
other way around.

[^ref6]: https://github.com/phadej/foldable1
[^ref7]: https://oleg.fi/haddocks/foldable1/
[^ref8]: https://hackage.haskell.org/package/foldable1
[^ref9]:
https://hackage.haskell.org/package/semigroupoids-5.3.3/docs/Data-Semigroup-Foldable-Class.html

Unresolved questions
--------------------

- Should we add `Bifoldable1` too. That should be trivial.
- GHC-8.10 freeze is quite soon, is targeting GHC-8.12/base-4.15 more
realistic?


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add Data.Foldable1 to base

Tony Morris
I agree Foldable1 in base would be great, but I think the most bang for buck would be to include several others; at least also Traversable1 and possibly even Apply,Bind,Alt

I second the comment about the issue related to addressing the names, etc in semigroupoids, in preparation for inclusion to base.

On Fri, Oct 18, 2019 at 11:12 AM Oleg Grenrus <[hidden email]> wrote:

What is the proposed change in semigroupoids, I don't see any decisive conclusion comment. To get this going, I suggest limiting discussion to the Foldable1 only
and if after this proposal is accepted, extrapolate for the rest of `semigroupoids`.

So if someone can propose a concrete list how to rename symbols in https://oleg.fi/haddocks/foldable1/Data-Foldable1.html, I'll make a separate branch & haddock page.

Is the wanted renaming s/1//; s/^/semi/:

- Foldable1    -> Semifoldable
- fold1        -> semifold
- foldMap1     -> semifoldMap
- foldr1       -> semifoldr
- foldr1map    -> semifoldr1map
- toNonEmpty   -> toNonEmpty
- ...
- head1        -> semihead
- last1        -> semilast
- minimum1     -> semiminimum
- maximum1     -> semimaximum

- intercalate1 -> semiintercalate
- foldl1M      -> semifoldl
- ...
- maximum1By   -> semimaximumBy
- ...

I'm fine with this.
The head1/semihead are both silly, but the suffix was there to avoid name clash, so prefix is fine for that purpose too.

---

The synopsis of current state of proposed Data.Foldable1

module Data.Foldable1 where

class Foldable t => Foldable1 t
  fold1      :: (Foldable1 t, Semigroup m) => t m -> m
  foldMap1   :: (Foldable1 t, Semigroup m) => (a -> m) -> t a -> m
  foldMap1'  :: (Foldable1 t, Semigroup m) => (a -> m) -> t a -> m
  foldr1     :: Foldable1 t => (a -> a -> a) -> t a -> a
  foldr1'    :: Foldable1 t => (a -> a -> a) -> t a -> a
  foldl1     :: Foldable1 t => (a -> a -> a) -> t a -> a
  foldl1'    :: Foldable1 t => (a -> a -> a) -> t a -> a
  toNonEmpty :: Foldable1 t => t a -> NonEmpty a
  maximum1   :: forall a. (Foldable1 t, Ord a) => t a -> a
  minimum1   :: forall a. (Foldable1 t, Ord a) => t a -> a
  head1      :: Foldable1 t => t a -> a
  last1      :: Foldable1 t => t a -> a
  foldr1map  :: Foldable1 t => (a -> b) -> (b -> b -> b) -> t a -> b
  foldl1'map :: Foldable1 t => (a -> b) -> (b -> b -> b) -> t a -> b
  foldl1map  :: Foldable1 t => (a -> b) -> (b -> b -> b) -> t a -> b
  foldr1'map :: Foldable1 t => (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

- Oleg

On 18.10.2019 3.06, Edward Kmett wrote:
I’m happy to take patches to move things along in semigroupoids. My focus has been elsewhere, I admit.

-Edward

On Oct 17, 2019, at 5:03 PM, Andrew Martin [hidden email] wrote:

 While I want this abstraction in base, I don’t want it there yet. There is an open issue on semigroupoids about renaming everything: https://github.com/ekmett/semigroupoids/issues/26

This needs to be handled before the abstraction is brought into base. Also, foldr1 is awful in common situations. See https://github.com/ekmett/semigroupoids/issues/77

The problem is that refinements of this abstraction seem to have stalled in semigroupoids, but these are desperately needed before the abstraction is brought into base.

Sent from my iPhone

On Oct 17, 2019, at 10:42 AM, Oleg Grenrus <[hidden email]> wrote:

I propose adding `Foldable1` type-class into `base1`.

Add Foldable1
=============


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

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

Change
------

The change exist as merge request[^ref4] on gitlab.haskell.org.

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 | toNonEmpty | foldr1map #-}

    -- the defining member, like foldMap but only asking for Semigroup
    foldMap1 :: Semigroup m => (a -> m) -> t a -> m

    fold1 :: Semigroup m => t m -> 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.
    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.
`semigroupoids`[^ref6] uses `Data.Semigroup.Foldable`,
but it's confusing; and using different name could help migration.

The 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`[^ref9],
as without `Apply` they don't make sense.
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_`.
 
[^ref5]: https://gitlab.haskell.org/ghc/ghc/merge_requests/1973
[^ref9]:
https://hackage.haskell.org/package/semigroupoids-5.3.3/docs/Data-Semigroup-Foldable-Class.html

[^ref5]: https://gitlab.haskell.org/ghc/ghc/merge_requests/1973

Compatibility & migration
-------------------------

I drafted a compatibility package `foldable1` (github[^ref6],
haddocks[^ref7]),
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[^ref8] by
M Farkas-Dyck (cc'd). I hope they would donate the name to Haskell.org /
CLC;
the package won't have any other good use when `Data.Foldable1` is in
`base`,
then act as a compat package.

`Data.Foldable1` contains also instances for `Lift`, `Backwards` and
`Reverse`
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).

`semigroupoids` would need a bit of work, to depend on `foldable1`,
yet the public changes can be kept quite minimal.
I don't think that anything in reverse dependencies of `lens` will be
broken by
this change, if "new" `Foldable1` is re-exported from `semigroupoids`'
`Data.Semigroup.Foldable`[^ref9]

Other "compat" packages -- like `tagged`, `bifunctors` -- have to be
dealt with
case by case. For example whether they should depend on `foldable1` or
other way around.

[^ref6]: https://github.com/phadej/foldable1
[^ref7]: https://oleg.fi/haddocks/foldable1/
[^ref8]: https://hackage.haskell.org/package/foldable1
[^ref9]:
https://hackage.haskell.org/package/semigroupoids-5.3.3/docs/Data-Semigroup-Foldable-Class.html

Unresolved questions
--------------------

- Should we add `Bifoldable1` too. That should be trivial.
- GHC-8.10 freeze is quite soon, is targeting GHC-8.12/base-4.15 more
realistic?


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add Data.Foldable1 to base

Oleg Grenrus

I won't try to include Traversable1, nor Apply, Bind, Alt; not yet. It would extend the scope of a patch way too much, and rise AMP-like questions, which I don't have answers to.
Foldable1 is something which "could move into base without pain" [1], so let's do that first.

- Oleg

[1]: https://www.reddit.com/r/haskell/comments/6d0vgt/could_we_have_foldable1_and_traversable1_in_base/dhz42ie/

On 18.10.2019 10.26, Tony Morris wrote:
I agree Foldable1 in base would be great, but I think the most bang for buck would be to include several others; at least also Traversable1 and possibly even Apply,Bind,Alt

I second the comment about the issue related to addressing the names, etc in semigroupoids, in preparation for inclusion to base.

On Fri, Oct 18, 2019 at 11:12 AM Oleg Grenrus <[hidden email]> wrote:

What is the proposed change in semigroupoids, I don't see any decisive conclusion comment. To get this going, I suggest limiting discussion to the Foldable1 only
and if after this proposal is accepted, extrapolate for the rest of `semigroupoids`.

So if someone can propose a concrete list how to rename symbols in https://oleg.fi/haddocks/foldable1/Data-Foldable1.html, I'll make a separate branch & haddock page.

Is the wanted renaming s/1//; s/^/semi/:

- Foldable1    -> Semifoldable
- fold1        -> semifold
- foldMap1     -> semifoldMap
- foldr1       -> semifoldr
- foldr1map    -> semifoldr1map
- toNonEmpty   -> toNonEmpty
- ...
- head1        -> semihead
- last1        -> semilast
- minimum1     -> semiminimum
- maximum1     -> semimaximum

- intercalate1 -> semiintercalate
- foldl1M      -> semifoldl
- ...
- maximum1By   -> semimaximumBy
- ...

I'm fine with this.
The head1/semihead are both silly, but the suffix was there to avoid name clash, so prefix is fine for that purpose too.

---

The synopsis of current state of proposed Data.Foldable1

module Data.Foldable1 where

class Foldable t => Foldable1 t
  fold1      :: (Foldable1 t, Semigroup m) => t m -> m
  foldMap1   :: (Foldable1 t, Semigroup m) => (a -> m) -> t a -> m
  foldMap1'  :: (Foldable1 t, Semigroup m) => (a -> m) -> t a -> m
  foldr1     :: Foldable1 t => (a -> a -> a) -> t a -> a
  foldr1'    :: Foldable1 t => (a -> a -> a) -> t a -> a
  foldl1     :: Foldable1 t => (a -> a -> a) -> t a -> a
  foldl1'    :: Foldable1 t => (a -> a -> a) -> t a -> a
  toNonEmpty :: Foldable1 t => t a -> NonEmpty a
  maximum1   :: forall a. (Foldable1 t, Ord a) => t a -> a
  minimum1   :: forall a. (Foldable1 t, Ord a) => t a -> a
  head1      :: Foldable1 t => t a -> a
  last1      :: Foldable1 t => t a -> a
  foldr1map  :: Foldable1 t => (a -> b) -> (b -> b -> b) -> t a -> b
  foldl1'map :: Foldable1 t => (a -> b) -> (b -> b -> b) -> t a -> b
  foldl1map  :: Foldable1 t => (a -> b) -> (b -> b -> b) -> t a -> b
  foldr1'map :: Foldable1 t => (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

- Oleg

On 18.10.2019 3.06, Edward Kmett wrote:
I’m happy to take patches to move things along in semigroupoids. My focus has been elsewhere, I admit.

-Edward

On Oct 17, 2019, at 5:03 PM, Andrew Martin [hidden email] wrote:

 While I want this abstraction in base, I don’t want it there yet. There is an open issue on semigroupoids about renaming everything: https://github.com/ekmett/semigroupoids/issues/26

This needs to be handled before the abstraction is brought into base. Also, foldr1 is awful in common situations. See https://github.com/ekmett/semigroupoids/issues/77

The problem is that refinements of this abstraction seem to have stalled in semigroupoids, but these are desperately needed before the abstraction is brought into base.

Sent from my iPhone

On Oct 17, 2019, at 10:42 AM, Oleg Grenrus <[hidden email]> wrote:

I propose adding `Foldable1` type-class into `base1`.

Add Foldable1
=============


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

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

Change
------

The change exist as merge request[^ref4] on gitlab.haskell.org.

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 | toNonEmpty | foldr1map #-}

    -- the defining member, like foldMap but only asking for Semigroup
    foldMap1 :: Semigroup m => (a -> m) -> t a -> m

    fold1 :: Semigroup m => t m -> 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.
    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.
`semigroupoids`[^ref6] uses `Data.Semigroup.Foldable`,
but it's confusing; and using different name could help migration.

The 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`[^ref9],
as without `Apply` they don't make sense.
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_`.
 
[^ref5]: https://gitlab.haskell.org/ghc/ghc/merge_requests/1973
[^ref9]:
https://hackage.haskell.org/package/semigroupoids-5.3.3/docs/Data-Semigroup-Foldable-Class.html

[^ref5]: https://gitlab.haskell.org/ghc/ghc/merge_requests/1973

Compatibility & migration
-------------------------

I drafted a compatibility package `foldable1` (github[^ref6],
haddocks[^ref7]),
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[^ref8] by
M Farkas-Dyck (cc'd). I hope they would donate the name to Haskell.org /
CLC;
the package won't have any other good use when `Data.Foldable1` is in
`base`,
then act as a compat package.

`Data.Foldable1` contains also instances for `Lift`, `Backwards` and
`Reverse`
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).

`semigroupoids` would need a bit of work, to depend on `foldable1`,
yet the public changes can be kept quite minimal.
I don't think that anything in reverse dependencies of `lens` will be
broken by
this change, if "new" `Foldable1` is re-exported from `semigroupoids`'
`Data.Semigroup.Foldable`[^ref9]

Other "compat" packages -- like `tagged`, `bifunctors` -- have to be
dealt with
case by case. For example whether they should depend on `foldable1` or
other way around.

[^ref6]: https://github.com/phadej/foldable1
[^ref7]: https://oleg.fi/haddocks/foldable1/
[^ref8]: https://hackage.haskell.org/package/foldable1
[^ref9]:
https://hackage.haskell.org/package/semigroupoids-5.3.3/docs/Data-Semigroup-Foldable-Class.html

Unresolved questions
--------------------

- Should we add `Bifoldable1` too. That should be trivial.
- GHC-8.10 freeze is quite soon, is targeting GHC-8.12/base-4.15 more
realistic?


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add Data.Foldable1 to base

Oleg Grenrus
In reply to this post by Oleg Grenrus

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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add Data.Foldable1 to base

Oleg Grenrus

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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add Data.Foldable1 to base

Oleg Grenrus
In reply to this post by Oleg Grenrus
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
```
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add Data.Foldable1 to base

Oleg Grenrus
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
> ```
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries