Proposal: Add a Semigroup-equivalent superclass of Alternative

[Mario Blažević]

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:
>> 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
>>
>