Proposal: Add a Semigroup-equivalent superclass of Alternative

[Roman Cheplyaka]

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

On 05/04/15 18:05, 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 at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>