Proposal: Add a Semigroup-equivalent superclass of Alternative

[Edward Kmett]

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ć <blamario at ciktel.net> 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 at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20150405/ffa14e21/attachment-0001.html>