Proposal: Add a Semigroup-equivalent superclass of Alternative

Sun Apr 5 16:15:13 UTC 2015

Rather, the Alt in semigroups is an indexed version with a Functor
constraint: a sort of middle ground.

There is also a possibly quite useful indexed version without a Functor
constraint that can be polykinded. That one is useful for working with
things like Conor McBride's Kleisli Arrows of Outrageous Fortune, when it
comes time to talk about indexed writer monads and indexed update monads.

-Edward

On Sun, Apr 5, 2015 at 12:13 PM, Edward Kmett <ekmett at gmail.com> wrote:

> 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/4457a950/attachment.html>