There is no such general extension as far as I know, but the same code that produced warnings about impending AMP in 7.8 should work for this. On Mar 29, 2015 10:31 AM, "Mario Blažević" wrote:

On 03/29/2015 08:20 AM, Jeremy wrote:

...

The proposal to make Semigroup a superclass of Monoid was discussed a while ago [1], and the conclusion was to "put this off until the dust has settled from the AMP and FT changes".

Now that 7.10 is out, I would like to re-propose. The proposed plan is similar to AMP, but less invasive, as (in my subjective experience) user-defined Monoids are much less common than user-defined Monads.

1. GHC 7.12 will include Semigroup and NonEmpty in base. All Monoid instances, and anything else which forms a Semigroup, will have a Semigroup instance. GHC will issue a warning when it encounters an instance of Monoid which is not an instance of Semigroup.

I wasn't aware GHC provided a mechanism to do something like this. If it does, that is great news indeed. Can you point to the GHC extension (or, if not implemented yet, the ticket for creating the extension)?

Just to clarify, I'm +1 for the proposal. Even without any GHC magic, I'd be +1 for making Semigroup a superclass of Monoid even if it went through the same code-breaking steps as AMP.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

I like this idea, but I'm not exactly clear on the mechanics. Will mappend move to Semigroup, or <>, or will we get more redundant operations? On Mar 29, 2015 11:04 AM, "Herbert Valerio Riedel" wrote:

On 2015-03-29 at 14:20:33 +0200, Jeremy wrote:

...

Now that 7.10 is out, I would like to re-propose. The proposed plan is similar to AMP, but less invasive, as (in my subjective experience) user-defined Monoids are much less common than user-defined Monads.

1. GHC 7.12 will include Semigroup and NonEmpty in base. All Monoid instances, and anything else which forms a Semigroup, will have a Semigroup instance. GHC will issue a warning when it encounters an instance of Monoid which is not an instance of Semigroup.

2. GHC >7.12 will define Monoid as a subclass of Semigroup.

+1 _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

On 2015-03-29 at 17:23:19 +0200, David Feuer wrote:

I guess I should get a dog in the fight—I think <> should be the Semigroup method.

+1

my one concern is that we'd be force to give all the various map data structures out there a left biased "First" style semigroup instance if we keep the current default monoid instances that containers and list-tries provide for historical reasons. and at least in the applications i write, i want the semigroup that merges those keys. On Sun, Mar 29, 2015 at 3:14 PM, Evan Laforge wrote:

On Sun, Mar 29, 2015 at 5:20 AM, Jeremy wrote:

...

Now that 7.10 is out, I would like to re-propose. The proposed plan is similar to AMP, but less invasive, as (in my subjective experience) user-defined Monoids are much less common than user-defined Monads.

I think I'm generally in favor, but in my experience is the reverse of this. I have tons of Monoids and only a few Monads. All of my Monads also had Applicative defined because I wanted to use (<$>) and (<*>), however none of my Monoids have Semigroup, because they all have a natural mempty, and there's nothing "extra" in Semigroup that would tempt me to add an instance. So while AMP meant no changes for me, "Semi MP" would definitely force code changes in many places (every 'instance .*Monoid', which is 31 in one project).

That said I don't have to worry about backward compatibility so I don't mind. For someone who maintains libraries, they would have to add a dependency on 'semigroup', which is going to pull in a number of other dependencies, but it mostly seems to be stuff people are probably already depending on. Except unordered-containers maybe. _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Greg, the proposal is for Semigroup s => Monoid s, not for Monoid s => Semigroup s , which is what i believe you're reading the proposal to say. a large number of statistical aggregatory and analytical data structures are semigroups but emphatically not monoids because they lack the notion of a zero element! over the past 8 months alone i've probably 5-10 different data structures for statistical ingestion that were semigroups but not monoids. point being, semigroups are well defined mathematical objects, and i deal with many many things that are semigroups and not monoids, especially in data analysis application domains. I can provide a few example later this week if you want. On Sun, Mar 29, 2015 at 8:33 PM, Greg Weber wrote:

...

1. GHC 7.12 will include Semigroup and NonEmpty in base. All Monoid instances, and anything else which forms a Semigroup, will have a Semigroup instance. GHC will issue a warning when it encounters an instance of Monoid which is not an instance of Semigroup.

There is going to be some push-back on this proposal from those that point out the lack of mempty makes Semigroup less rigorous that a Monoid. That concept can create a debate around what is "anything else which forms a semigroup". I would try to amend the proposal to something much more specific. Here is how I have used Semigroup

1) a structure that is already a Monoid 2) a structure that is a non-empty form of a Monoid 3) a structure where mempty is not constant but a function of the element you would concatenate it to

An example of 3) is concatenating bounding boxes. A zeroed box is certainly an empty box, but it will create a larger box when concatenated with an existing box.The identity concatenation of the current bounding box is always the current bounding box.

What other structures do you use Semigroup for? Are there structures in base where there would be a debate about adding an instance? Can we come up with rules for when a Semigroup instance should be added to base?

On Sun, Mar 29, 2015 at 5:20 AM, Jeremy wrote:

...

The proposal to make Semigroup a superclass of Monoid was discussed a while ago [1], and the conclusion was to "put this off until the dust has settled from the AMP and FT changes".

Now that 7.10 is out, I would like to re-propose. The proposed plan is similar to AMP, but less invasive, as (in my subjective experience) user-defined Monoids are much less common than user-defined Monads.

1. GHC 7.12 will include Semigroup and NonEmpty in base. All Monoid instances, and anything else which forms a Semigroup, will have a Semigroup instance. GHC will issue a warning when it encounters an instance of Monoid which is not an instance of Semigroup.

2. GHC >7.12 will define Monoid as a subclass of Semigroup.

Stage 2 could be delayed - or in the extreme case, cancelled - if the warnings following stage 1 indicate that the proposal would cause significant breakage of existing code, although this is not anticipated.

The rationale for this change is:

1. Semigroup is a popular package (this is relevant in combination with the following point). 2. Using an existing Monoid as a Semigroup requires redefining it (or WrappedMonoid), leading to much boilerplate and duplication. 3. NonEmpty is often redefined by beginners (or those who don't think it's worth having an extra dependency for).

[1] https://mail.haskell.org/pipermail/libraries/2013-June/020188.html

-- View this message in context: http://haskell.1045720.n5.nabble.com/Proposal-Make-Semigroup-as-a-superclass... Sent from the Haskell - Libraries mailing list archive at Nabble.com. _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Jeremy, Do you propose: Monoid a => Monoid (Maybe a) be changed to: Semigroup a => Monoid (Maybe a) as the documentation indicates? +1, but I think there are some technicalities that I think would benefit from a more concrete proposal including as a patch or hackage analysis. On Sun, Mar 29, 2015 at 8:16 PM, M Farkas-Dyck wrote:

On 29/03/2015 at 05:20:33 -0700, Jeremy wrote:

...

1. GHC 7.12 will include Semigroup and NonEmpty in base.

+1 for Semigroup at least.

NonEmpty is simply the cofree comonad of Maybe, so I think we ought to define it either as such or to be compatibly redefinitile as such, e.g.

now: data NonEmpty a = a .: Maybe (NonEmpty a)

so potentially later: data Cofree f a = a .: f (Cofree f a) type NonEmpty = Cofree Maybe

as otherwise we shall have various code using nonsame isomorphic types which one must convert or coerce between for no good reason.

+1 for NonEmpty if so defined, -1 otherwise.

...

2. GHC >7.12 will define Monoid as a subclass of Semigroup.

+1

On 29/03/2015 at 11:23:19 -0400, David Feuer wrote:

...

I guess I should get a dog in the fight—I think <> should be the Semigroup method.

+1 _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

-- Love in Jesus Christ, John Alfred Nathanael Chee http://www.biblegateway.com/ http://web.cecs.pdx.edu/~chee/

František Farka [1] worked in detail on a proposal that would make such refactorings painless, see *Maintainable type classes for Haskell* [2] Cheers, Petr [1] http://staff.computing.dundee.ac.uk/frantisekfarka/ [2] http://staff.computing.dundee.ac.uk/frantisekfarka/publications.html po 30. 3. 2015 v 11:24 odesílatel Merijn Verstraaten napsal:

-2 from me.

Not because I oppose Semigroup as a superclass of Monoid, but because of brittle migration path.

I would much rather put the resurrection of DefaultSuperclassInstances [1], IntrinsicSuperclasses [2], or some new proposal on the roadmap that would allow us to more easily refactor and update the typeclass hierarchy without breaking everything all the time.

Cheers, Merijn

[1] - https://ghc.haskell.org/trac/ghc/wiki/DefaultSuperclassInstances [2] - https://ghc.haskell.org/trac/ghc/wiki/IntrinsicSuperclasses

...

On 30 Mar 2015, at 5:39, John Alfred Nathanael Chee wrote:

Jeremy,

Do you propose:

Monoid a => Monoid (Maybe a)

be changed to:

Semigroup a => Monoid (Maybe a)

as the documentation indicates?

+1, but I think there are some technicalities that I think would benefit from a more concrete proposal including as a patch or hackage analysis.

On Sun, Mar 29, 2015 at 8:16 PM, M Farkas-Dyck wrote: On 29/03/2015 at 05:20:33 -0700, Jeremy wrote:

...

1. GHC 7.12 will include Semigroup and NonEmpty in base.

+1 for Semigroup at least.

NonEmpty is simply the cofree comonad of Maybe, so I think we ought to define it either as such or to be compatibly redefinitile as such, e.g.

now: data NonEmpty a = a .: Maybe (NonEmpty a)

so potentially later: data Cofree f a = a .: f (Cofree f a) type NonEmpty = Cofree Maybe

as otherwise we shall have various code using nonsame isomorphic types which one must convert or coerce between for no good reason.

+1 for NonEmpty if so defined, -1 otherwise.

...

2. GHC >7.12 will define Monoid as a subclass of Semigroup.

+1

On 29/03/2015 at 11:23:19 -0400, David Feuer wrote:

...

I guess I should get a dog in the fight—I think <> should be the Semigroup method.

+1 _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

-- Love in Jesus Christ, John Alfred Nathanael Chee http://www.biblegateway.com/ http://web.cecs.pdx.edu/~chee/ _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

On Mon, 11 Apr 2016, Ben Franksen wrote:

Petr Pudlák wrote:

...

František Farka [1] worked in detail on a proposal that would make such refactorings painless, see *Maintainable type classes for Haskell* [2]

I am just reading the paper (from 2015) for the first time and have noted at least one factual error. On page 6 it says:

""" a4 – remove a superclass constraint from an existing class This change does not cause any problems. Some instances from be- fore the change may be superfluous as these are no longer re- quired by superclass constraint. """

Even though it does not invalidate the essence of what the author is claiming (it merely weakens the argument slightly), this particular assessment is clearly wrong: If the superclass has methods, removing the superclass breaks all functions that use superclass methods and that have a type signature which mentions only the child class in the constraints. Such client code must be fixed by adding a constraint that mentions the former superclass to its type.

The paper has clearly not been proofread by an expert(*), so I guess its results should be taken with a grain of salt. Which is sad because I do like the ideas expressed in it.

I already wrote to the author regarding this mistake. I gave him the practical example of the removal of Show superclass from Num.

On Mon, 30 Mar 2015, Edward Kmett wrote:

Collapse the first two steps into one step, but this means that nobody gets any warning of new names coming into the Prelude. On the other hand this would get us all the way to done by 7.14. On one hand, the first order consequence the amount of breakage caused by adding Semigroup to Prelude and taking (<>) is almost entirely confined to a handful of pretty printing libraries -- and we already broke those same libraries by taking (<$>).

Btw. hmatrix is another prominent package defining (<>) for matrix and related multiplications.

I am (+1) on adding Semigroup as superclass of Monoid, being mappend/(<>) included in Semigroup. More than once I felt encouraged to include a neutral element in a type where I would have gladly go without having it. Importing semigroups from Hackage would mean to have two identical operators, idea I do not find attractive. About the path to choose for adoption, any of the ways described by Edward Kmett seems good to me (I can quickly update any of my packages to the change), but I'd rather avoid the longest one. Daniel Díaz On Mar 30, 2015 9:09 PM, "Edward Kmett" wrote:

That definitely pushes me towards one of the "long" adoption paths.

Here adding a Semigroup instance for Matrix actually works to get the same symbol, but it has a different fixity (infixr 8). Same with (<>) in the pretty printing libraries (infixl 6).

In Data.Monoid and Data.Semigroup we have infixr 6 <>

-Edward

On Mon, Mar 30, 2015 at 2:51 PM, Henning Thielemann < lemming@henning-thielemann.de> wrote:

...

On Mon, 30 Mar 2015, Edward Kmett wrote:

Collapse the first two steps into one step, but this means that nobody

...

gets any warning of new names coming into the Prelude. On the other hand this would get us all the way to done by 7.14. On one hand, the first order consequence the amount of breakage caused by adding Semigroup to Prelude and taking (<>) is almost entirely confined to a handful of pretty printing libraries -- and we already broke those same libraries by taking (<$>).

Btw. hmatrix is another prominent package defining (<>) for matrix and related multiplications.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

The most likely path forward would bring in: class Semigroup a where (<>) :: a -> a -> a (... and sconcat :: NonEmpty a -> a probably hidden in a submodule to avoid bringing NonEmpty into Prelude, and times1p possibly bikeshedded to stimes1p for naming consistency, both probably exiled to Data.Semigroup) class Semigroup a => Monoid a where mappend :: a -> a -> a mappend = (<>) mempty :: a with a path towards eventually removing mappend from Monoid in 7.18+, which would get you more or less to your ObBikeshed in the long run, minus a couple of things, plus a couple of others. (and possibly a top level mtimes can then be defined in terms of stimes1p and mempty, giving peasant exponentiation for log time construction of many monoids and O(1) for idempotent ones.) As an aside: having a concat that is parameterized on Foldable on the other hand as a member of the class actually turns out to almost paradoxically prevent you from doing almost any optimizations for it. (I say almost, since because we added some members to Foldable in 7.10 this isn't quite the case any more.) Also to fold you need at least one member, so Foldable/[] is too weak. -Edward On Mon, Apr 6, 2015 at 11:15 PM, wren romano wrote:

I'm +1 for getting the Prelude to eventually say:

class Semigroup a where mappend :: a -> a -> a mconcat :: [a] -> a

(<>) = mappend infixr 6 <>

class Semigroup a => Monoid a where mempty :: a

instance Semigroup a => Monoid (Maybe a) where...

The long path seems the most sensible way to get here with a minimum of breakage. Tis a shame it'll take so long to complete.

(ObBikeshed: Honestly, I'd rather see:

class Semigroup a where (<>) :: a -> a -> a concat :: [a] -> a -- or: concat :: Foldable f => f a -> a

...getting rid of the mwhatever naming scheme and avoiding taking two names for one function. The name "concat" is pretty ubiquitously used for monomorphic variants of the [a]->a type. The notable exception being Foldable.concat, which relies specifically on using the [a] semigroup for no especially interesting reason I can discern. But I'm pretty sure that ship has sailed unless we give up hope of providing a breakage-free upgrade path.)

-- Live well, ~wren _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

As is probably well-known, I am definitely +1 on this. I don't have strong opinions about which particular path we take to get there. On Tue, Apr 7, 2015 at 1:37 PM wren romano wrote:

On Tue, Apr 7, 2015 at 12:52 AM, Edward Kmett wrote:

...

The most likely path forward would bring in:

class Semigroup a where (<>) :: a -> a -> a (... and sconcat :: NonEmpty a -> a probably hidden in a submodule to avoid bringing NonEmpty into Prelude, and times1p possibly bikeshedded to stimes1p for naming consistency, both probably exiled to Data.Semigroup)

Whoops! Yes, that's the type I meant for concatenation ::chagrin::

-- Live well, ~wren _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

On 04/05/2015 11:56 AM, Roman Cheplyaka wrote:

FWIW, Ed Kmett has this already in his semigroupoids package as Data.Functor.Alt: https://hackage.haskell.org/package/semigroupoids

Of course he does, I don't know why I didn't look there. Well I like the Alt class name but I'd still prefer to reuse <|> if possible. If I had to guess, I'd assume the operator was a strict variant of <$> or <*>.

On 05/04/15 18:05, Mario Blažević wrote:

...

...

The proposal to make Semigroup a superclass of Monoid was discussed a while ago [1], and the conclusion was to "put this off until the dust has settled from the AMP and FT changes". It has occurred to me that the Alternative class, which is pretty much a constructor version of Monoid, would benefit from the same

On 03/29/2015 08:20 AM, Jeremy wrote: treatment. The greatest difficulty seems to be in finding the name for the Semigroup-equivalent superclass of Alternative. For lack of imagination,I'll just call it Semigroup1:

class Applicative f => Semigroup1 f where (<|>) :: f a -> f a -> f a some :: f a -> f [a] many :: f a -> f [a]

class Semigroup1 f => Alternative f where empty :: f a

The rationale for this change:

1. All the theoretical arguments for introducing Semigroup carry over with no change.

2. There are existing data types that could be made instances of Semigroup1, and not of Alternative. I have not performed any comprehensive survey, but QuickCheck's Gen type can provide one example:

instance Semigroup1 Gen where f <|> g = oneof [f, g]

3. Most interesting instances of Alternative are various parser types. A parser type that doesn't define empty is a parser that cannot fail by construction. That makes intuitive sense. I can imagine some benefits from a set of parser combinators that generated two types, only one of which could fail. Fill in the blanks:

instance Semigroup1 IrrefutableParser instance Alternative Parser

token :: a -> Parser a optional :: Parser a -> IrrefutableParser (Maybe a) many0 :: Parser a -> IrrefutableParser [a]

There are, of course, two important differences between the Monoid and Alternative situation. First, the Semigroup class already exists, if not in base. That only means the proposal outlined above requires more critique and bikeshedding.

The other difference is that the Semigroup operator (<>) is different from the Monoid operator mappend. This is mostly an unfortunate backward compatibility issue, but it does have a benefit of allowing the two classes to exist independently for a while before they are brought together. If we really, *really* desire the same doubtful benefit for Alternative, we can use a new operator name for the Semigroup1 class (I refuse to provide one in this proposal) and then eventually stipulate (<|>) = i-refuse-to-provide-one-in-this-proposal.

My preference, if available, would be to just move the <|> operator into the superclass in 7.12. It's such a perfect operator name. Without a new GHC extension, however, this would mean that every existing instance of Alternative would be broken in 7.12. Furthermore, there would be no way to write an Alternative instance valid in both 7.10 and 7.12 without CPP directives. The only saving grace here is that the Alternative instances are relatively few, and it may just be possible to coordinate all the changes.

So, here's a question to all authors of parser libraries and everybody else that has defined Alternative instances: would you be able and willing to add CPP directives to your code for this purpose?

For everybody else: this is a proposal, so vote on it.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Rather, the Alt in semigroups is an indexed version with a Functor constraint: a sort of middle ground. There is also a possibly quite useful indexed version without a Functor constraint that can be polykinded. That one is useful for working with things like Conor McBride's Kleisli Arrows of Outrageous Fortune, when it comes time to talk about indexed writer monads and indexed update monads. -Edward On Sun, Apr 5, 2015 at 12:13 PM, Edward Kmett wrote:

There are many points in the design space.

* There is a pure Semigroup1, which acts as an indexed semigroup, without the Applicative superclass, which is the Alt class in the semigroupoids package.

* There is a Alternative minus empty, which you've proposed here.

But then even within each of those options we have several choices.

The laws for how Applicative and Alternative relate are subject to all the same problems as the laws between Monad and MonadPlus and the situation doesn't get any better here. catch vs. right distribution rears its head all over again.

The empty laws, which get much more complicated on the Alternative front at least don't show up.

Finally, there is another discussion this proposal may actively interfere with that has frankly, a lot more traction: What to do with 'fail' in Monad. Lennart has been a rather vocal proponent about finally doing something about that situation. To produce a viable MonadFail story one very solid path would be to lift the question up to the Applicative level, at which point in time, moving fail to an mfail in side of a class that depends on Applicative may be a good home, but that is more or less switching to a unit-then-add-an-associative operation style, rather than this.

With Applicative as a superclass of Monad we were asking folks to adopt an abstraction they had already accepted and used for several years.

With Semigroup as a superclass of Monoid, the abstraction has already seen many years of productive use.

Haskell is remarkably bad at dealing with very fine-grained class hierarchies.

With all of that in mind, I'm personally -1 on this addition. I don't think it rises to the level of traction needed to ask everyone everywhere to change all the code that they have ever written that involves MonadPlus, when the design space remains as large as it is.

-Edward

On Sun, Apr 5, 2015 at 11:05 AM, Mario Blažević wrote:

...

On 03/29/2015 08:20 AM, Jeremy wrote:

...

The proposal to make Semigroup a superclass of Monoid was discussed a while ago [1], and the conclusion was to "put this off until the dust has settled from the AMP and FT changes".

It has occurred to me that the Alternative class, which is pretty much a constructor version of Monoid, would benefit from the same treatment. The greatest difficulty seems to be in finding the name for the Semigroup-equivalent superclass of Alternative. For lack of imagination,I'll just call it Semigroup1:

class Applicative f => Semigroup1 f where (<|>) :: f a -> f a -> f a some :: f a -> f [a] many :: f a -> f [a]

class Semigroup1 f => Alternative f where empty :: f a

The rationale for this change:

1. All the theoretical arguments for introducing Semigroup carry over with no change.

2. There are existing data types that could be made instances of Semigroup1, and not of Alternative. I have not performed any comprehensive survey, but QuickCheck's Gen type can provide one example:

instance Semigroup1 Gen where f <|> g = oneof [f, g]

3. Most interesting instances of Alternative are various parser types. A parser type that doesn't define empty is a parser that cannot fail by construction. That makes intuitive sense. I can imagine some benefits from a set of parser combinators that generated two types, only one of which could fail. Fill in the blanks:

instance Semigroup1 IrrefutableParser instance Alternative Parser

token :: a -> Parser a optional :: Parser a -> IrrefutableParser (Maybe a) many0 :: Parser a -> IrrefutableParser [a]

There are, of course, two important differences between the Monoid and Alternative situation. First, the Semigroup class already exists, if not in base. That only means the proposal outlined above requires more critique and bikeshedding.

The other difference is that the Semigroup operator (<>) is different from the Monoid operator mappend. This is mostly an unfortunate backward compatibility issue, but it does have a benefit of allowing the two classes to exist independently for a while before they are brought together. If we really, *really* desire the same doubtful benefit for Alternative, we can use a new operator name for the Semigroup1 class (I refuse to provide one in this proposal) and then eventually stipulate (<|>) = i-refuse-to-provide-one-in-this-proposal.

My preference, if available, would be to just move the <|> operator into the superclass in 7.12. It's such a perfect operator name. Without a new GHC extension, however, this would mean that every existing instance of Alternative would be broken in 7.12. Furthermore, there would be no way to write an Alternative instance valid in both 7.10 and 7.12 without CPP directives. The only saving grace here is that the Alternative instances are relatively few, and it may just be possible to coordinate all the changes.

So, here's a question to all authors of parser libraries and everybody else that has defined Alternative instances: would you be able and willing to add CPP directives to your code for this purpose?

For everybody else: this is a proposal, so vote on it.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

On Sun, Apr 5, 2015 at 1:05 PM, Mario Blažević wrote:

On 04/05/2015 12:13 PM, Edward Kmett wrote:

...

There are many points in the design space. ... Haskell is remarkably bad at dealing with very fine-grained class hierarchies.

You've blogged about this in

https://www.fpcomplete.com/user/edwardk/editorial/procrustean-mathematics

and I understand your concerns, even if I'm personally rooting for the centipedes. I have to say that, both when I read the article, and re-reading it again now, I wished for a clearer statement of the problem. Is it so fundamental in mathematics, as you seem to imply, that no programming language will ever be able to reconcile alternative abstractions? Or is it only a problem with Haskell and the proposed superclass extensions, as you suggest in

I'm all for centipedes, but I agree that Haskell's type classes are pretty terrible at it. The main problems I see are Haskell's type classes (a) do not properly have laws attached to them, thus law-only classes don't work well, (b) lack a language for deriving instances from other instances, proving multiple instances equivalent, etc., and (c) require newtype hackery to have more than one instance per type. None of these are fundamentally mathematical in nature. In maths we routinely dissociate instances/structures from their carrier type, construct new structures from old ones, prove that various constructions are idempotent/inverse/coherent/etc, and so on. The problem is that Haskell's type classes don't faithfully implement the structures of this style of mathematics. For example, we have many different points in the design space, like the indexed semigroup and the non-empty Alternative. As structures, they each have different laws. Whereas many of their instances have both structures and thus satisfy both sets of laws (in addition to whatever appropriate cohesion laws), thus allowing us to equivocate between which fine structure we're referring to whenever using these instances. In addition to not being able to talk about the cohesion, Haskell doesn't let us unify the names of the structures, thus introducing a namespacing issue that doesn't arise in maths. Moreover, Haskell doesn't offer a good upgrade path to move from equivocating between two structures to settling on one or the other. Often, when we can equivocate, that means we have a huge library of combinators which work equally well for both structures; but if we stop equivocating then that forces us to duplicate (almost) the whole API, one copy for each of the fine structures we're disambiguating. Again, introducing namespacing issues. We can try to unify these APIs by making an even *more* fine-grained hierarchy, but that's just pushing the namespacing issues into the methods of the type classes, or running headlong towards law-only classes. The fundamental issue, IMO, is that type classes aren't designed to solve the problems of centipede mathematics. Type classes are designed for capturing a certain style of overloading, they aren't designed for solving namespacing issues. For centipede mathematics we need not only to be able to recognize a group of implementations as (semantically) "the same" function (à la overloading), but also to recognize a group of (semantically distinct) functions as having the same implementation (dual to overloading, "underloading"?). -- Live well, ~wren

So what's the conclusion on this? We seem to have a strong consensus on going ahead with the proposal, and a weaker consensus for doing so via the long path. -- View this message in context: http://haskell.1045720.n5.nabble.com/Proposal-Make-Semigroup-as-a-superclass... Sent from the Haskell - Libraries mailing list archive at Nabble.com.

What's problematic about empty lists for semigroups? On Wed, Apr 29, 2015 at 8:51 AM, Stephen Tetley wrote:

The consensus seems largely to favour the high level proposal to add a Semigroup class, but there hasn't been much discussion of the implementation details i.e. what to do about mappend or a Semigroup-like candidate (problematic for empty lists, of course).

On 29 April 2015 at 12:24, Jeremy wrote:

...

So what's the conclusion on this? We seem to have a strong consensus on going ahead with the proposal, and a weaker consensus for doing so via the long path.

-- View this message in context: http://haskell.1045720.n5.nabble.com/Proposal-Make-Semigroup-as-a-superclass... Sent from the Haskell - Libraries mailing list archive at Nabble.com. _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

---

Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Cough - I meant semigroups introduces a NonEmpty list type. On 29 April 2015 at 14:51, Stephen Tetley wrote:

Empty lists are problematic if you want a mconcat like operation.

Edward Kmett's semigroups package introduces an EmptyList type to avoid this (the downside being it introduces an EmptyList type).

If you don't want an mconcat like operation then Semigroup only has one useful operation (<>).

On 29 April 2015 at 14:13, David Feuer wrote:

...

What's problematic about empty lists for semigroups?

why do you need an mconcat-like operation?

Well, the more operations the better, especially derived ones rather than ones baked into the class. For me a class with only one operation wouldn't really meet the Fairburn threshold. In this case, I'd abstain from voting against as the consensus is high but I would like to see a proper proposal for what adding Semigroup includes (and what it leaves out) rather than a straw in the wind notion to just add it. On 29 April 2015 at 14:57, David Feuer wrote:

Kmett's NonEmpty type (or similar) is the solution to this, but really, why do you need an mconcat-like operation?

On Wed, Apr 29, 2015 at 9:51 AM, Stephen Tetley wrote:

...

Empty lists are problematic if you want a mconcat like operation.

Edward Kmett's semigroups package introduces an EmptyList type to avoid this (the downside being it introduces an EmptyList type).

If you don't want an mconcat like operation then Semigroup only has one useful operation (<>).

On 29 April 2015 at 14:13, David Feuer wrote:

...

What's problematic about empty lists for semigroups?

On Wed, Apr 29, 2015 at 8:51 AM, Stephen Tetley wrote:

...

The consensus seems largely to favour the high level proposal to add a Semigroup class, but there hasn't been much discussion of the implementation details i.e. what to do about mappend or a Semigroup-like candidate (problematic for empty lists, of course).

On 29 April 2015 at 12:24, Jeremy wrote:

...

So what's the conclusion on this? We seem to have a strong consensus on going ahead with the proposal, and a weaker consensus for doing so via the long path.

-- View this message in context:

http://haskell.1045720.n5.nabble.com/Proposal-Make-Semigroup-as-a-superclass... Sent from the Haskell - Libraries mailing list archive at Nabble.com. _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

---

Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Well, it seems the consensus is high enough that we'll try to go ahead with this. As it affects the Prelude, we may put out another poll / wider broadcast just to avoid any appearance of ambushing folks with another change to the Prelude without announcement, but I think at this point my intent is to pick a path to make this happen. -Edward On Wed, Apr 29, 2015 at 8:51 AM, Stephen Tetley wrote:

The consensus seems largely to favour the high level proposal to add a Semigroup class, but there hasn't been much discussion of the implementation details i.e. what to do about mappend or a Semigroup-like candidate (problematic for empty lists, of course).

On 29 April 2015 at 12:24, Jeremy wrote:

...

So what's the conclusion on this? We seem to have a strong consensus on going ahead with the proposal, and a weaker consensus for doing so via the long path.

-- View this message in context: http://haskell.1045720.n5.nabble.com/Proposal-Make-Semigroup-as-a-superclass... Sent from the Haskell - Libraries mailing list archive at Nabble.com. _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

---

Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

On Wed, Apr 29, 2015 at 2:28 PM, Malcolm Wallace wrote:

Whilst the change itself might have merit, I have to say I'm getting really fed up of all these tiny and piecemeal change proposals for the Prelude. I'd be much more in favour of something radical, like removing 80% of the Prelude altogether, and forcing people to import list operations from Data.List, monad stuff from Control.Monad, number hierarchies from Data.Numeric, etc. Then we would not have to suffer all of these long-drawn-out and painful yet minor breakages in future. With a minimal Prelude, all of the recent proposed changes, from Applicative/Monad, to Foldable/Traversable, to Semigroup/Monoid, could have been achieved purely via libraries, and if someone doesn't like a change, they can just pick a different library.

... and if they are exiled all the way into separate libraries then nobodies code works together, because nobody wants to incur a dependency they don't need at the moment. For example, stuff in the containers package implement the classes in base, but I'd wager pretty heavily that I'd have a hard time convincing Johan or Milan to pick up _any_ dependency they absolutely didn't have to have to make that library go. As messy and organic as it is having a shared base to build on it gives us a common names and instances for things we all have in common. It may have been better to start with the culture you suggest. It would have reduced this particular pain point, but the knock-on consequences of such a design are pretty terrible. So we're left with the choice of nickel and diming you with small changes that you can work around with nice warning periods as you get hit by them or making bigger changes that require harder actions. =/ -Edward

On 29-04-2015 13:24, Jeremy wrote:

So what's the conclusion on this? We seem to have a strong consensus on going ahead with the proposal, and a weaker consensus for doing so via the long path.

Maybe you should work out the details wrt. the concerns/things raised in the thread and do a wiki page detailing all of this? Ideally with some code to review, perhaps? In particular, if you could do a survey of Hackage to find out how many (and which) packages would be affected by this, you would earn a lot of bonus points for due dilligence! :) (I'm definitely +1 on the concept, but it's hard to judge how practical it is without estimates of breakage, etc.) Regards,

Wouldn't your concerns about NonEmpty be addressed by keeping its type abstract? Then something like Liquid Haskell could be used to define it better. On May 4, 2015 10:19 AM, "Reid Barton" wrote:

On Sun, Mar 29, 2015 at 8:20 AM, Jeremy wrote:

...

The proposal to make Semigroup a superclass of Monoid was discussed a while ago [1], and the conclusion was to "put this off until the dust has settled from the AMP and FT changes".

Now that 7.10 is out, I would like to re-propose. The proposed plan is similar to AMP, but less invasive, as (in my subjective experience) user-defined Monoids are much less common than user-defined Monads.

1. GHC 7.12 will include Semigroup and NonEmpty in base. All Monoid instances, and anything else which forms a Semigroup, will have a Semigroup instance. GHC will issue a warning when it encounters an instance of Monoid which is not an instance of Semigroup.

Strongly opposed to adding a NonEmpty type to base. It's a step in the wrong direction: the problem it clumsily tries to address is solved much better by refinement types à la LiquidHaskell, which handles this and other whole classes of problems at once.

Now, we don't have LiquidHaskell in GHC yet; but let's not settle for adding a NonEmpty type that we know is an inferior approach to base now, when it will likely be very hard to remove it in the future.

I know there are some who use NonEmpty types currently, but I think their needs are just as well (if not better) met by putting the type in a small package outside of base with few dependencies.

...

2. GHC >7.12 will define Monoid as a subclass of Semigroup.

While it frustrates me to repeatedly see so much time spent by both GHC developers and Haskell library and application programmers on changes like this with fairly small upside, I don't have any fundamental objection to ending up in a state with Semigroup as a superclass of Monoid.

Regards, Reid Barton

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

The issue with a LiquidHaskell solution in this space, aside from the fact that it is an experiment that isn't part of the compiler or the language that we have, and uses assumptions about the way numbers work that don't hold for the ones we have, is that it is terribly invasive. In order to use it everything that ever wants to work with your shiny new non-empty list type needs to be written in LiquidHaskell to prove the non-empty invariant still holds. Refinement types are notoriously hard to use. On the other-hand a type like NonEmpty satisfies that invariant trivially: There is no empty constructor. The price of this is that it is a different data type, with different operations. I love LiquidHaskell, but I'd be very hesitant to do anything or rather to not do anything predicated on its existence. -Edward On Mon, May 4, 2015 at 2:37 PM, Reid Barton wrote:

On Mon, May 4, 2015 at 12:58 PM, David Feuer wrote:

...

Wouldn't your concerns about NonEmpty be addressed by keeping its type abstract? Then something like Liquid Haskell could be used to define it better.

There are (at least) two possible designs for a "non-empty list type".

1. A refinement type (as in LiquidHaskell) of [t] whose values include only the non-empty lists. Call it NonEmptyLiquid t. You can pass a NonEmptyLiquid t to a function that expects a [t], and you can pass a [t] to a function that expects a NonEmptyLiquid [t] if the compiler can prove that your [t] is nonempty. If it can't then you can add a runtime test for emptiness and in the non-empty case, the compiler will know the list is non-empty.

2. A new type NonEmptySolid t that is totally unrelated to [t] like you can define in Haskell today. The advantage is that NonEmptySolid is a full-fledged type constructor that can have instances, be passed to other type constructors and so on. The disadvantage is that you need to explicitly convert in your program (and possibly do a runtime conversion also) in either direction between [t] and NonEmptySolid t.

I think most people who want a "non-empty list type" want 1, not 2. Option 2 is bad for API design because it forces the users of your library to care exactly as much as you do about non-emptiness. If you imagine adding other sorts of lists like infinite lists, fixed-length or bounded-length lists, lists of even length etc. then it quickly becomes clear that having such an array of incompatible list types is not the way to go. We just want lists to be lists, but we also want the compiler to make sure we don't try to take the head of an empty list.

Those who use a NonEmpty type prefer option 2 over option 0 "type NonEmptyGas t = [t] -- and just hope"; but that doesn't mean they prefer option 2 over option 1. Those who really want option 2 can also define it as a newtype wrapper on option 1, as you noted.

So, to answer your question, no, it wouldn't really make a difference if the NonEmpty type was abstract. That would just smooth the transition to a design that I think people don't really want.

Finally, let me reiterate that there seem to be no advantages to moving a NonEmpty type into base rather than into its own small package. We don't need base to swallow up every small popular package.

Regards, Reid Barton

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

On Mon, 4 May 2015, Edward Kmett wrote:

The issue with a LiquidHaskell solution in this space, aside from the fact that it is an experiment that isn't part of the compiler or the language that we have, and uses assumptions about the way numbers work that don't hold for the ones we have, is that it is terribly invasive. In order to use it everything that ever wants to work with your shiny new non-empty list type needs to be written in LiquidHaskell to prove the non-empty invariant still holds. Refinement types are notoriously hard to use. On the other-hand a type like NonEmpty satisfies that invariant trivially: There is no empty constructor.

The price of this is that it is a different data type, with different operations.

In my experience with my non-empty package I found that I can lift that restriction by using type classes like Functor, Traversable etc.

I love LiquidHaskell, but I'd be very hesitant to do anything or rather to not do anything predicated on its existence.

Although LiquidHaskell is cool, I also prefer to solve simple problems with simple tools. Non-empty lists do not need a sophisticated prover framework, it can be solved with simple Haskell 98.

On Tue, 5 May 2015, Greg Weber wrote:

The issue you have not raised that I am more concerned with is that NonEmpty only works for lists. Michael and I figured out how to extend the concept to any (Mono)Foldable structure and also to be able to demand lengths of > 1.

It's possible with the structure provided by "non-empty". It is also possible to construct types for lists of fixed length or lists with an arbitrary set of allowed lengths.