Opened 3 years ago

Closed 3 years ago

Last modified 11 months ago

#10365 closed feature request (fixed)

Implement Semigroup as a superclass of Monoid Proposal (Phase 1)

Reported by: gidyn Owned by: quchen
Priority: high Milestone: 8.0.1
Component: libraries/base Version: 7.10.1
Keywords: report-impact Cc: hvr, ekmett, bergmark, RyanGlScott
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: #14191 Differential Rev(s): Phab:D1284
Wiki Page: prime:Libraries/Proposals/SemigroupMonoid

Description (last modified by hvr)

More details in prime:Libraries/Proposals/SemigroupMonoid

Phase 1 (GHC 7.12)

Phase 1 consists in (at the very least) moving Data.Semigroup and Data.List.NonEmpty into base for GHC 7.12 (aka 8.0).

If there's enough time we will also implement a warning as part of the first phase:

Add a warning about definitions of an operator named (<>) that indicate it will be coming into Prelude in 7.14. We should warn about missing Semigroup instances at any use site of (<>) as they'll break in 7.14.

Attachments (1)

0001-add-Semigroup.patch (17.8 KB) - added by strake888 3 years ago.

Download all attachments as: .zip

Change History (47)

comment:1 Changed 3 years ago by gidyn

Owner: set to ekmett

comment:2 Changed 3 years ago by hvr

This topic just came up again over at http://www.reddit.com/r/haskell/comments/39tumu/make_semigroup_a_superclass_of_monoid/

...and the associated previous reddit discussion for the proposal referenced in the ticket description can be found at http://www.reddit.com/r/haskell/comments/30s1t2/proposal_make_semigroup_as_a_superclass_of_monoid/

comment:3 Changed 3 years ago by thomie

And Data.List.NonEmpty will be added, according to this reddit comment by ekmett.

comment:4 Changed 3 years ago by bergmark

Cc: bergmark added

comment:5 Changed 3 years ago by hvr

Description: modified (diff)
Keywords: report-impact added
Milestone: 7.12.1
Priority: normalhigh
Summary: Make Semigroup as a superclass of MonoidMake Semigroup as a superclass of Monoid (Phase 1)

comment:6 Changed 3 years ago by hvr

Description: modified (diff)
Summary: Make Semigroup as a superclass of Monoid (Phase 1)Implement Semigroup as a superclass of Monoid Proposal (Phase 1)

added link to new Proposal/SemigroupMonoid wiki page (still a draft)

comment:7 Changed 3 years ago by thoughtpolice

Milestone: 7.12.18.0.1

Milestone renamed

comment:8 Changed 3 years ago by thomie

Owner: ekmett deleted

comment:9 Changed 3 years ago by RyanGlScott

Cc: RyanGlScott added

Changed 3 years ago by strake888

Attachment: 0001-add-Semigroup.patch added

comment:10 Changed 3 years ago by strake888

Owner: set to strake888

comment:11 in reply to:  10 Changed 3 years ago by hvr

I don't recognize the implementation, is this actually based on the the latest semigroups package release?

Moreover, the patch contains unrelated changes (e.g. the Void type)

Last edited 3 years ago by hvr (previous) (diff)

comment:12 Changed 3 years ago by hvr

Status: newpatch

comment:13 Changed 3 years ago by ekmett

I'm not sure what is going on here with this patch.

When I last checked we were looking at more or less porting the state of semigroups 0.17.0.1 directly into base. In fact that eas the reason for the 0.17 release, to get it into a state suitable for direct inclusion with a longer ramp-up period.

comment:14 Changed 3 years ago by hvr

Owner: changed from strake888 to hvr

@strake888, thanks for preparing the patch, but we had already planned out a much more elaborate patch (which I've just completed and published as Phab:D1284). I have to apologize as this was a miscommunication error on our end to remove the owner from this ticket and make it appear as if this task was looking for a volunteer.

To be on the safe side in the future, please give a short heads-up notice if you see another task you may be interested in tackling, especially if the task description seems incomplete or still in work-in-progress state (as for this ticket).

comment:15 Changed 3 years ago by hvr

Differential Rev(s): Phab:D1284

comment:16 Changed 3 years ago by strake888

Ah, cool. I merely saw this unowned with no patch and panicked cuz I seriously want this to happen this year.

comment:17 Changed 3 years ago by ekmett

All good. This served as a forcing function, driving us to flesh out the plan from start to finish and to get something ready for release. =)

comment:18 Changed 3 years ago by Herbert Valerio Riedel <hvr@…>

In 03b38042/ghc:

Add Data.Semigroup and Data.List.NonEmpty (re #10365)

This implements phase 1 of the semigroup-as-monoid-superclass
proposal (https://ghc.haskell.org/wiki/Proposal/SemigroupMonoid).

The modules were migrated from the `semigroups-0.17` release mostly
as-is, except for dropping several trivial `{-# INLINE #-}`s,
removing CPP usage, and instances for types & classes provided
outside of `base` (e.g. `containers`, `deepseq`, `hashable`, `tagged`,
`bytestring`, `text`)

Differential Revision: https://phabricator.haskell.org/D1284

comment:19 Changed 3 years ago by hvr

Owner: changed from hvr to quchen

For the record, David is working on the warning-feature

comment:20 Changed 3 years ago by bgamari

I realize that this has all been discussed before but I do wonder whether we really need to fold in Data.List.NonEmpty at this juncture? It does not appear to be a widely used type in practice and the interface has a few quirks. What do we gain by it being in base?

The reason I ask is that I've noticed that NonEmpty introduces yet more partial functions to base. For instance, why must words have type NonEmpty Char -> NonEmpty String? Why not NonEmpty Char -> [String]? After all it seems quite reasonable for a non-empty string to nevertheless contain no words. Given that these are design decisions that reasonable people may disagree over, might it be best just to defer them packages outside of base?

Sorry bringing this up so long after the initial consideration but I just wanted to make sure we have thoroughly considered this angle.

comment:21 Changed 3 years ago by bergmark

I would like to see the partial functions removed as well. toList is total, which makes fromList the most natural name for converting to a NonEmpty, but nope it's partial! Use nonEmpty instead. There's also a partial IsList instance, I really don't want literals to be able to crash at runtime.

comment:22 in reply to:  21 ; Changed 3 years ago by RyanGlScott

Replying to bergmark:

I really don't want literals to be able to crash at runtime.

Bear in mind that it's already possible for literals to crash at runtime:

$ ghci
GHCi, version 7.10.2: http://www.haskell.org/ghc/  :? for help
λ> import Numeric.Natural
λ> -1 :: Natural
*** Exception: arithmetic underflow

comment:23 in reply to:  22 ; Changed 3 years ago by hvr

Replying to RyanGlScott:

Bear in mind that it's already possible for literals to crash at runtime:

λ> -1 :: Natural
*** Exception: arithmetic underflow

Somewhat related, #10930 wants GHC to at least emit a compiler warning in that case

comment:24 in reply to:  23 Changed 3 years ago by RyanGlScott

Replying to hvr:

Somewhat related, #10930 wants GHC to at least emit a compiler warning in that case

Ah, that's good to know. Perhaps we could add a similar warning for [] :: NonEmpty (when using -XOverloadedLists) in one of the phases of this proposal.

While we're on this topic, I have another question about things to come from the SMP (SemigroupMonoid Proposal). Adding Data.List.NonEmpty brings in the First, Last, and Option data types, which are (intentionally) quite similar in behavior to First and Last (from Data.Monoid) and Maybe. Are there plans to consolidate (or strategically deprecate) some of these data types at some phase of the SMP?

Last edited 3 years ago by RyanGlScott (previous) (diff)

comment:25 Changed 3 years ago by ekmett

RyanGIScott:

The plan around any sort of eventual consolidation of First and Last is definitely punted several years down the road.

Once Maybe has the Semigroup-based Monoid instance, Maybe (First a) using the semigroup First has more or less the semantics of the existing monoidal First a.

However, at this current moment such things have to be implemented in terms of Option, which is considerably more painful!

After enough time has passed I can envision a situation where we might eventually choose to deprecate the existing Monoid versions, but that is far enough out that any proposal about it at this stage would be so much hand-waving. If it takes us 3 years to get Semigroup in as a superclass of Monoid, it'd likely take us another 3 years to get to where the new Semigroup forms of those constructions have wide enough distribution to even start considering deprecation of the originals.

comment:26 Changed 3 years ago by ekmett

bgamari: Regarding words, that simply looks like a bug and it should have the type you've suggested.

comment:27 in reply to:  21 Changed 3 years ago by Lemming

Replying to bergmark:

I would like to see the partial functions removed as well. toList is total, which makes fromList the most natural name for converting to a NonEmpty, but nope it's partial! Use nonEmpty instead. There's also a partial IsList instance, I really don't want literals to be able to crash at runtime.

In the non-empty package I fall back to infix operators for non-empty list construction. E.g. constructing a list with at least two elements looks like this: 0 !: 1 !: 2 : 3 : 4 : [].

Last edited 3 years ago by Lemming (previous) (diff)

comment:28 Changed 3 years ago by ekmett

@bgamari: I've removed words/unwords/lines/unlines.

comment:29 Changed 3 years ago by Herbert Valerio Riedel <hvr@…>

In 8f02baa/ghc:

Remove Data.List.NonEmpty.{words,unwords,lines,unlines}

This change mirrors the change that occured for the recent
`semigroups-0.18` release, i.e.

  https://github.com/ekmett/semigroups/commit/7a000212847b0d309892f34e4754a25ddec7100b

This removal addresses concerns raised in #10365

comment:30 Changed 3 years ago by rwbarton

However, the real concern raised in #10365 is why Data.List.NonEmpty should be in base at all, causing extra work for GHC developers, and tying future fixes (once base is released) of this type to new versions of GHC, with no perceivable advantages.

comment:31 Changed 3 years ago by ekmett

@rwbarton: The short version of it is this: We have mconcat for Monoid today. It actually sees a fair bit of use and I've seen folks implement it in the wild to do things like Kahan summation or better short circuiting than the base monoid can (it gets to assume an associativity.) fold gets to know the container, mconcat gets to know the Monoid.

The moral equivalent in Semigroup requires some form of canonical non-empty type to fold over. The net effect of removing it is that the semigroups package would continue to exist just to supply this type, the class would lose its canonical structure to fold over, and sconcat becomes unimplementable.

Why should moving Semigroup into base cost users functionality?

comment:32 in reply to:  31 Changed 3 years ago by Lemming

Replying to ekmett:

The moral equivalent in Semigroup requires some form of canonical non-empty type to fold over. The net effect of removing it is that the semigroups package would continue to exist just to supply this type, the class would lose its canonical structure to fold over, and sconcat becomes unimplementable.

sconcat in base could have type s -> [s] -> s. Then there is no need for NonEmpty to be in base and people can define top-level functions that use sconcat to implement a counterpart for their favourite NonEmpty type (e.g. Data.List.NonEmpty or Data.NonEmpty).

comment:33 Changed 3 years ago by ekmett

Lemming: It is clear that any choice that includes it won't make you happy.

However, randomly carving it up into two pieces and changing the API ensures that nobody who has existing code that supplies an sconcat in their instances winds up with code that will work across the transition.

semigroups is the most downloaded package in all of Hackage, I don't like the idea of randomly bikeshedding the API here to get an end state that is less useful and which ensures work on the behalf of every package maintainer who currently implements sconcat.

The transition story is better if we include it than if we don't, and the result is more usable out of the box.

comment:34 Changed 3 years ago by rwbarton

Yes, just give sconcat type s -> [s] -> s.

A module being included in a package that is a dependency of a popular package is not a compelling reason to move that module into base! I mean I don't even know what to say to that.

comment:35 Changed 3 years ago by ekmett

Both are reasonable colors for this bikeshed, but one doesn't break users. I'll refer this to the rest of the CLC to get a judgment.

comment:36 Changed 3 years ago by nomeata

I follow ekmett’s argument that Monoid to [] is like semigroups to ?, and to me it makes sense of have a type for non-empty sets in base. (If having a slim base were a goal, then maybe not, but I don’t see that being a goal for the community in general).

But it is true that things are harder to fix once they are in base, so we should aim to pick the “right” implementation. According to https://wiki.haskell.org/Non-empty_list#Packages there are 6(!) implementations of non-empty lists on hackage. I did not look at them right now, so I’ll lazily pose the question: Is there any good reason to prefer any of these over the implementation from semigroups?

comment:37 Changed 3 years ago by ekmett

@nomeata:

FWIW- the implementation in semigroups was crafted by mixing and matching parts between the 2-3 implementations of non-empty lists at the time. The skeleton of it was built mostly by raiding the NonEmptyList package for parts with permission of the owners. AFAIK, Tony has deprecated his NonEmptyList package in favor of the one in semigroups (hence the lack of updates in the last 5 years -- this changeover predated having any deprecation mechanism on hackage.)

Robin Kay's NonEmpty package is just a data type with no instances and no methods, also 6 years old.

Cardinality also hasn't seen a patch in 6 years. Remarkably it still builds, because it too simply provides no instances.

MinLen requires a ton of type system extensions.

Out of the things that are suitable to consider as a base-ready encoding of a non-empty list, only Henning's Data.NonEmpty is actively maintained, and it tackles a more general problem, and brings with it a dozen different ad hoc classes for inserts and the like.

So if you're hunting for materials to use to rebuild the bikeshed completely, I'd say out of the packages on hackage today, that non-empty is the only real source of lumber.

Last edited 3 years ago by ekmett (previous) (diff)

comment:38 Changed 3 years ago by nomeata

Right. Data.NonEmpty looks interesting, but a tad too interesting for a plain non-empty-list-type suitable for base.

With all the others, the data type definition is equivalent, and rest of the API seems to be straight forward to me. So I have no qualms about this particular color of the shed.

comment:39 Changed 3 years ago by rwbarton

You can rename the method of Semigroup with type a -> [a] -> a and move sconcat to a top-level definition in Data.List.NonEmpty, and that should hardly break anyone compared to the rather substantial Semigroup => Monoid superclass addition that is the main part of this proposal.

comment:40 Changed 3 years ago by ekmett

@rwbarton:

That is the most reasonable version of the "non-NonEmpty" version of the proposal I've heard.

I'm not yet sold one way or the other, but I'll bring that up at the CLC meeting Thursday and see if that sways folks your way.

comment:41 Changed 3 years ago by hvr

Description: modified (diff)
Wiki Page: prime:Libraries/Proposals/SemigroupMonoid

update wiki page link

comment:42 Changed 3 years ago by bgamari

@ekmett, has there been any motion on this front?

At this point I have no horse in this race; nevertheless I do want to make sure that whatever option we do end up with was chosen not by chance by but conscious decision. Sadly time is quickly running out for 8.0.

comment:43 Changed 3 years ago by nomeata

The committee decided to keep sconcat, and hence NonEmpty: https://prime.haskell.org/wiki/Libraries/Meetings/2015-11-05

comment:44 Changed 3 years ago by bgamari

Resolution: fixed
Status: patchclosed

Alright then. I believe this issue is then resolved.

Thanks everyone!

comment:45 Changed 3 years ago by quchen

AMP for Semigroup is in review status on Phab:D1539, Trac #11139

comment:46 Changed 11 months ago by hvr

Phase 2 is tracked in #14191

Note: See TracTickets for help on using tickets.