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 |
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`. _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
Thanks for the support and comments Dmitrii. - Oleg On 17.10.2019 19.26, Dmitrii Kovanikov
wrote:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
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 |
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
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
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:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
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 - 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. _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
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:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
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. On 18.10.2019 10.26, Tony Morris wrote:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by Oleg Grenrus
This is second revision of proposal. Thanks to all commented so
far. - Oleg
_______________________________________________ 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 |
To keep committee well equipped to make final decision - Oleg
On 22.10.2019 17.51, John Cotton
Ericson wrote:
On 21.10.2019 0.31, Oleg Grenrus wrote:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
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 |
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 |
Free forum by Nabble | Edit this page |