Fwd: Proposal: Add Data.Semigroup to base, as a superclass of Monoid

newer
Why is there no Foldable instance...

older
Re: Proposal: Add Data.Semigroup...

Gabriel Gonzalez

12 Jun 2013 12 Jun '13

5:31 p.m.

Forgot to copy `libraries` on my answer to your question: On Wed, Jun 12, 2013 at 3:28 AM, Herbert Valerio Riedel wrote:

...

On 2013-06-12 at 00:04:04 +0200, Gabriel Gonzalez wrote:

...
I think types that lack an empty element are a misfeature.

...so having a data-type for representing non-empty lists (on which operation such as head/last/minimum/maximum et. al can be proper statically guaranteed total functions as opposed to resorting to 'Maybe'-wrapped results which need to be checked dynamically at runtime) is a misfeature?

I phrased that poorly. Non-empty data types are useful, but having a combining operation on those types of type: A -> A -> A ... is not. The very example you gave (non-empty lists) shows why. If you combine two non-empty lists you can actually prove a stronger result, that the combined list has at least two elements. However, you lose that information if you use the `mappend` operation. I'm not saying that non-empty lists shouldn't have a combining operation, but rather that `mappend` is not the appropriate operation for the task.

...

They usually end up contaminating everything they touch, which is why

...
semigroups forms an entire parallel ecosystem of its own.

Can you provide a concrete example showing the kind of problematic "contamination" that is caused by semigroup-forming types?

The non-empty list example shows what I meant. The moment you start including extra information like non-emptiness you have to re-engineer all downstream operations to preserve that information as faithfully as possible. Again, there's nothing wrong with that, but it's not deserving of its own type class or a special place in the Prelude.

...

cheers, hvr

Attachments:

attachment.html (text/html — 2.6 KB)

Show replies by date

Ben

12 Jun 12 Jun

8:35 p.m.

New subject: Proposal: Add Data.Semigroup to base, as a superclass of Monoid

i'm not voting for semigroups, but it seems like there are useful examples of combining datatypes without a unit. for example, Int under min or max. you might imagine wanting to express finding the smallest or largest element of a collection as a fold that combines Int over min and max. to be fair, one can always add unit element to a semigroup, in this case +/- infinity, but it seems unnecessary to require it when it is not needed for your computation. best, b On Jun 12, 2013, at 2:31 PM, Gabriel Gonzalez wrote:

...

Forgot to copy `libraries` on my answer to your question:

On Wed, Jun 12, 2013 at 3:28 AM, Herbert Valerio Riedel wrote: On 2013-06-12 at 00:04:04 +0200, Gabriel Gonzalez wrote:

...
I think types that lack an empty element are a misfeature.

...so having a data-type for representing non-empty lists (on which operation such as head/last/minimum/maximum et. al can be proper statically guaranteed total functions as opposed to resorting to 'Maybe'-wrapped results which need to be checked dynamically at runtime) is a misfeature?

I phrased that poorly. Non-empty data types are useful, but having a combining operation on those types of type:

A -> A -> A

... is not.

The very example you gave (non-empty lists) shows why. If you combine two non-empty lists you can actually prove a stronger result, that the combined list has at least two elements. However, you lose that information if you use the `mappend` operation. I'm not saying that non-empty lists shouldn't have a combining operation, but rather that `mappend` is not the appropriate operation for the task.

...
They usually end up contaminating everything they touch, which is why semigroups forms an entire parallel ecosystem of its own.

Can you provide a concrete example showing the kind of problematic "contamination" that is caused by semigroup-forming types?

The non-empty list example shows what I meant. The moment you start including extra information like non-emptiness you have to re-engineer all downstream operations to preserve that information as faithfully as possible. Again, there's nothing wrong with that, but it's not deserving of its own type class or a special place in the Prelude.

cheers, hvr

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Conrad Parker

9:03 p.m.

New subject: Proposal: Add Data.Semigroup to base, as a superclass of Monoid

On 13 June 2013 05:31, Gabriel Gonzalez wrote:

...

Forgot to copy `libraries` on my answer to your question:

On Wed, Jun 12, 2013 at 3:28 AM, Herbert Valerio Riedel wrote:

...
On 2013-06-12 at 00:04:04 +0200, Gabriel Gonzalez wrote:

...
I think types that lack an empty element are a misfeature.

...so having a data-type for representing non-empty lists (on which operation such as head/last/minimum/maximum et. al can be proper statically guaranteed total functions as opposed to resorting to 'Maybe'-wrapped results which need to be checked dynamically at runtime) is a misfeature?

I phrased that poorly. Non-empty data types are useful, but having a combining operation on those types of type:

A -> A -> A

... is not.

The very example you gave (non-empty lists) shows why. If you combine two non-empty lists you can actually prove a stronger result, that the combined list has at least two elements. However, you lose that information if you use the `mappend` operation. I'm not saying that non-empty lists shouldn't have a combining operation, but rather that `mappend` is not the appropriate operation for the task.

This is a "perfect world" argument: that there is no point in doing small step X because in a perfect world, Haskell would be a different language with generalized feature Y which subsumes X. Here, X is "have semigroup" and Y is "having dependent types". I think this style of reasoning is counterproductive for the libraries list. There are good reasons for being conservative about libraries changes, but appeal to a perfect world is not a good reason. Conrad.

Gabriel Gonzalez

9:24 p.m.

New subject: Proposal: Add Data.Semigroup to base, as a superclass of Monoid

On Jun 12, 2013 6:03 PM, "Conrad Parker" wrote:

...

On 13 June 2013 05:31, Gabriel Gonzalez wrote:

...
Forgot to copy `libraries` on my answer to your question:

On Wed, Jun 12, 2013 at 3:28 AM, Herbert Valerio Riedel

wrote:

...

...
...
On 2013-06-12 at 00:04:04 +0200, Gabriel Gonzalez wrote:

...
I think types that lack an empty element are a misfeature.

...so having a data-type for representing non-empty lists (on which operation such as head/last/minimum/maximum et. al can be proper statically guaranteed total functions as opposed to resorting to 'Maybe'-wrapped results which need to be checked dynamically at

runtime)

...
is a misfeature?

I phrased that poorly. Non-empty data types are useful, but having a combining operation on those types of type:

A -> A -> A

... is not.

The very example you gave (non-empty lists) shows why. If you combine two non-empty lists you can actually prove a stronger result, that the combined list has at least two elements. However, you lose that information if you use the `mappend` operation. I'm not saying that non-empty lists shouldn't have a combining operation, but rather that `mappend` is not the appropriate operation for the task.

This is a "perfect world" argument: that there is no point in doing small step X because in a perfect world, Haskell would be a different language with generalized feature Y which subsumes X.

Here, X is "have semigroup" and Y is "having dependent types".

No. I'm saying that even if we had dependent types this would still be a bad idea because the type of the result will differ from the input types.

...

I think this style of reasoning is counterproductive for the libraries list. There are good reasons for being conservative about libraries changes, but appeal to a perfect world is not a good reason.

Anybody who has used the "Edward platform" knows exactly what I am talking about where the moment you add Semigroup you also have to add Semigroupoid, Apply, Bind, all just to preserve this entirely parallel ecosystem of things that are not empty. It infects everything downstream of it. Besides, I'm not saying that you can't define an operator that concatenates two Nonempty lists and produces a Nonempty list. You can, but don't put it in base. Just because there is a mathematical name for it doesn't mean it is worth adding to our collective cognitive overhead, otherwise we'd also have Magmas and Actions, too.

John Lato

10:32 p.m.

New subject: Proposal: Add Data.Semigroup to base, as a superclass of Monoid

On Thu, Jun 13, 2013 at 9:24 AM, Gabriel Gonzalez wrote:

...

On Jun 12, 2013 6:03 PM, "Conrad Parker" wrote:

...
On 13 June 2013 05:31, Gabriel Gonzalez wrote:

...
Forgot to copy `libraries` on my answer to your question:

On Wed, Jun 12, 2013 at 3:28 AM, Herbert Valerio Riedel

wrote:

...
...
...
On 2013-06-12 at 00:04:04 +0200, Gabriel Gonzalez wrote:

...
I think types that lack an empty element are a misfeature.

...so having a data-type for representing non-empty lists (on which operation such as head/last/minimum/maximum et. al can be proper statically guaranteed total functions as opposed to resorting to 'Maybe'-wrapped results which need to be checked dynamically at

runtime)

...
is a misfeature?

I phrased that poorly. Non-empty data types are useful, but having a combining operation on those types of type:

A -> A -> A

... is not.

The very example you gave (non-empty lists) shows why. If you combine two non-empty lists you can actually prove a stronger result, that the combined list has at least two elements. However, you lose that information if you use the `mappend` operation. I'm not saying that non-empty lists shouldn't have a combining operation, but rather that `mappend` is not the appropriate operation for the task.

This is a "perfect world" argument: that there is no point in doing small step X because in a perfect world, Haskell would be a different language with generalized feature Y which subsumes X.

Here, X is "have semigroup" and Y is "having dependent types".

No. I'm saying that even if we had dependent types this would still be a bad idea because the type of the result will differ from the input types.

This seems an arbitrary line, you could similarly say that we should remove (:), because by using cons you can prove a stronger result (the resulting list has 1 more element than the input), but that information is lost when using lists.

...

...
I think this style of reasoning is counterproductive for the libraries list. There are good reasons for being conservative about libraries changes, but appeal to a perfect world is not a good reason.

Anybody who has used the "Edward platform" knows exactly what I am talking about where the moment you add Semigroup you also have to add Semigroupoid, Apply, Bind, all just to preserve this entirely parallel ecosystem of things that are not empty. It infects everything downstream of it.

Besides, I'm not saying that you can't define an operator that concatenates two Nonempty lists and produces a Nonempty list. You can, but don't put it in base. Just because there is a mathematical name for it doesn't mean it is worth adding to our collective cognitive overhead, otherwise we'd also have Magmas and Actions, too.

The only reason it infects everything downstream is because it's broken in base. If Monoid depended on Semigroup (which is strictly more general), then working around it in libraries would be much easier. You can see this with other classes too. If Functor/Monad were generalized to work with indexed types, we wouldn't need to use NoImplicitPrelude and custom classes to make Set a Monad. If Functor were generalized to work with arbitrary categories, then you could use the standard Functor instead of building up a parallel ecosystem around CFunctor. et cetera. Of course we need to draw a line somewhere. Personally I've found semigroups to be useful, and with 72 direct dependencies (including yesod-platform) others have too. There are probably many other cases where people have made classes for semigroups for various reasons. I'd be in favor of making Semigroup a Monoid superclass if it doing so were relatively unintrusive. Since that's not currently the case (as Edward pointed out), I don't think we should proceed at this time. But that's purely for engineering reasons, not because semigroups are not useful

Edward Kmett

13 Jun 13 Jun

8:33 a.m.

New subject: Proposal: Add Data.Semigroup to base, as a superclass of Monoid

Honestly the main reason that 'semigroupoids' exist is that DataKinds are pretty much broken at this point in GHC due to the addition of Any and lack of eta reduction rules. While I can define a product semigroupoid a product category is still beyond GHC and I needed them for something I was working on at the time, so I just ran with it and defined the rest of the relevant hierarchy to explore what was possible. ;) I also realize you were going for hyperbole but Actions would require an MPTC+FD or type family, both are unlikely for anything under consideration for inclusion in base. ;) In a 'perfect language' we might have classes for affine, relevant and/or linear traversals, and similarly restricted folds, but Haskell is not that language. I'm not going to sit down and define up to 4 restricted variants of 'traverse' for every data type I define with no real code-reuse between them. My experience with the Apply and Bind (semi-applicative and semi-monad) classes is that they are very rarely worth their weight. I use them in the linear package so we can have diagonals of sparse matrices use the 'semi-monad' join for IntMap, etc. but that is pretty much the limit of their utility, unless you want to introduce non-empty traversals in the lens sense. Even if Semigroup was talked into base -- which is sounding rather unlikely at least in the short term -- I'd still be against bringing Apply/Semiapplicative and Bind/Semimonad into the mix. They'd require a much bigger change to user code, including requiring lots of CPP noise for little benefit. Interestingly each of the "major" current changes under discussion won't require CPP for almost all users who want to continue to support older versions. I'm generally willing to put them all over my own code, but tastes vary. Haskell's typeclass system is actually remarkably bad at dealing with overly fine grained class distinctions, because you get very little OOP-style code reuse as you move down the hierarchy. This tends to cause me to err on the side of the pragmatists for core library design while still trying to rectify the situation in my own libraries. -Edward On Wed, Jun 12, 2013 at 9:24 PM, Gabriel Gonzalez wrote:

...

On Jun 12, 2013 6:03 PM, "Conrad Parker" wrote:

...
On 13 June 2013 05:31, Gabriel Gonzalez wrote:

...
Forgot to copy `libraries` on my answer to your question:

On Wed, Jun 12, 2013 at 3:28 AM, Herbert Valerio Riedel

wrote:

...
...
...
On 2013-06-12 at 00:04:04 +0200, Gabriel Gonzalez wrote:

...
I think types that lack an empty element are a misfeature.

...so having a data-type for representing non-empty lists (on which operation such as head/last/minimum/maximum et. al can be proper statically guaranteed total functions as opposed to resorting to 'Maybe'-wrapped results which need to be checked dynamically at

runtime)

...
is a misfeature?

I phrased that poorly. Non-empty data types are useful, but having a combining operation on those types of type:

A -> A -> A

... is not.

The very example you gave (non-empty lists) shows why. If you combine two non-empty lists you can actually prove a stronger result, that the combined list has at least two elements. However, you lose that information if you use the `mappend` operation. I'm not saying that non-empty lists shouldn't have a combining operation, but rather that `mappend` is not the appropriate operation for the task.

This is a "perfect world" argument: that there is no point in doing small step X because in a perfect world, Haskell would be a different language with generalized feature Y which subsumes X.

Here, X is "have semigroup" and Y is "having dependent types".

No. I'm saying that even if we had dependent types this would still be a bad idea because the type of the result will differ from the input types.

...
I think this style of reasoning is counterproductive for the libraries list. There are good reasons for being conservative about libraries changes, but appeal to a perfect world is not a good reason.

Anybody who has used the "Edward platform" knows exactly what I am talking about where the moment you add Semigroup you also have to add Semigroupoid, Apply, Bind, all just to preserve this entirely parallel ecosystem of things that are not empty. It infects everything downstream of it.

Besides, I'm not saying that you can't define an operator that concatenates two Nonempty lists and produces a Nonempty list. You can, but don't put it in base. Just because there is a mathematical name for it doesn't mean it is worth adding to our collective cognitive overhead, otherwise we'd also have Magmas and Actions, too.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

4360

Age (days ago)

4361

Last active (days ago)

List overview

Download

5 comments

5 participants

participants (5)

Ben
Conrad Parker
Edward Kmett
Gabriel Gonzalez
John Lato