Add Data.Foldable1 to base

Thu Oct 17 16:26:27 UTC 2019

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

*
https://github.com/kowainik/relude/blob/45e112677c6e23759e4742cb695eed20a2cb964a/src/Relude/Extra/Foldable1.hs

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 <oleg.grenrus at iki.fi> 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
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20191017/3fcd5df0/attachment.html>