Proposal: Add a Semigroup-equivalent superclass of Alternative

[Mario Blažević]

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.