Discussion: remove the Applicative superclass from Alternative

Fri Nov 7 07:37:14 UTC 2014

The problem is <*> is able to do better than (>>=) here.

In a monad you are forced to inspect the left hand side to get an 'a' to
proceed with the right hand side under (>>=) at all. When you add the
identity laws you are left with no non-trivial monads that can avoid using
the right hand side of (>>=) by the left identity law.

So either the monad is trivial, in which case the law holds, or it isn't in
which case you have to inspect the term on the left of the (>>=) in order
to determine how to proceed, in which case since mzero 'can't have any 'a's
in it you can't extract any information from the right hand term.

The mzero >>= f = mzero law is a description of a consequence, but it is a
consequence of a thing we don't have in the Applicative world.

Applicatives have no such limitation, (<*>) is more or less symmetric in
the information you get about each argument. You can just as easily work
'right to left' or do something else.

-Edward

On Fri, Nov 7, 2014 at 12:18 AM, David Feuer <david.feuer at gmail.com> wrote:

> Taking the MonadPlus stuff to Alternative, their zero law (which you've
> said doesn't even work for everything) becomes
> empty <*> a = empty
>
> Distribution (on the side they describe, anyway):
> (a <|> b) <*> c = (a <*> c) <|> (b <*> c)
>
> Catch:
> pure x <|> xs = pure x
>
> On Thu, Nov 6, 2014 at 10:32 PM, Edward Kmett <ekmett at gmail.com> wrote:
>
>> This isn't just a matter of not wanting to rip off a bandaid.
>>
>> There isn't even full consensus on even what those classes would be.
>>
>> The MonadPlus reform proposal is just an article written up on the wiki
>> that has languished for a bunch of years and isn't terribly seriously put
>> forth. Also both of the classes in there have a law that no monad
>> transformer currently implements, so do we go to 4 classes? Also how do the
>> laws generalize to Applicative?
>>
>> The actual pain from having two (four?) classes masquerading as one is
>> actually quite little, despite appearances.
>>
>> You'd think if someone actually cared someone would have implemented a
>> fixed MonadOr and the like in a library -- and folks would be using it.
>> There are a couple of implementations that basically cut and paste from the
>> proposal, but there isn't any code actually using them.
>>
>> Splitting MonadPlus into its constituent ideas requires defining at least
>> a pair of classes where you have to be scared you might reach for the wrong
>> version of orElse or <|> for a given monad is a rather ridiculously large
>> change that potentially rather dramatically increases the penchant for user
>> error. You have to pick new names for the operations entirely so there is
>> no upgrade path, because otherwise its just silently wrong for many users.
>>
>> Also almost all of the existing code in the entire haskell ecosystem
>> would be broken. Not just a little bit, but a lot. MonadPlus has been with
>> us since 1996 or so. Ripping it to pieces is not a 'hey lets discuss this
>> over dinner' scale proposal.
>>
>> It isn't clear even how some code in transformers/mtl even refactors in
>> the presence of a split MonadOr/MonadPlus.
>>
>> What you have right now is users implicitly understand if the context
>> they are working in is one where <|> means 'do this if you fail' or <|>
>> means 'do both'.
>>
>> Moreover, there is also lot of code that actually fundamentally relies
>> upon both of these being the same operation. The way folks overload
>> Wadler's 1985 "list of successes" parser to let it work with either [] or
>> Maybe to get all or one parse fundamentally relies on the punning between
>> these different semantics within one class.
>>
>> We don't even have a viable implementation of the MonadPlus reform
>> proposal, let alone some Applicative generalization, the idea is nowhere
>> near baked enough to just upend the entire ecosystem and replace all of the
>> code within it.
>>
>> Contrary to appearances rewriting all of the Haskell code ever written
>> would be quite a bit of work.
>>
>> It is worth exploring what those classes should be, but such a proposal
>> has a very very high bar to clear.
>>
>> The new state has to be sufficiently better from the status quo that it
>> is worth the pain of literally breaking almost every package ever made in
>> anything recognizable as Haskell since Haskell 1.3 and there is no real
>> viable upgrade path. Big breaking changes require a lot of groundwork to
>> ensure they are worth the breakage, and a clear upgrade path for users, one
>> that is teachable.
>>
>> This idea currently fails both of these tests.
>>
>> Don't get me wrong. I'd love to have a nicer story here, but I have also
>> been looking at this very problem for years and have given up on one
>> existing.
>>
>> -Edward
>>
>> On Thu, Nov 6, 2014 at 9:49 PM, David Feuer <david.feuer at gmail.com>
>> wrote:
>>
>>> Fine, then. If there are two classes to be had, why don't we add them
>>> and get it over with? Then the type signatures in the parsing library will
>>> make some kind of sense, and people will stop complaining about it, and the
>>> kittens will all have lots of yarn.
>>>
>>> On Thu, Nov 6, 2014 at 9:43 PM, Edward Kmett <ekmett at gmail.com> wrote:
>>>
>>>> The operations from MonadPlus are the same as you'd get from Monad +
>>>> Alternative.
>>>>
>>>> That said, we don't actually have an extant proof that if you satisfy
>>>> the Alternative laws and the Monad laws you satisfy the MonadPlus laws!
>>>> Part of the problem is of course there are two sets of competing MonadPlus
>>>> laws, so the question itself of whether such a proof can exist is rather
>>>> ill-posed.
>>>>
>>>> The AMP does not cover 'removing' dead-weight methods like mzero,
>>>> mplus, return, etc. to get a more minimal subset, it just puts Applicative
>>>> and Alternative in the class hierarchy where they belong so you don't
>>>> constantly get stuck invoking liftM when working with transformers and the
>>>> like.
>>>>
>>>> -Edward
>>>>
>>>> On Thu, Nov 6, 2014 at 8:49 PM, Ivan Lazar Miljenovic <
>>>> ivan.miljenovic at gmail.com> wrote:
>>>>
>>>>> On 7 November 2014 12:36, David Feuer <david.feuer at gmail.com> wrote:
>>>>> > Currently, Applicative is a superclass of Alternative.
>>>>> Unfortunately, the
>>>>> > *only* laws for Alternative are the monoid laws. Sensible sets of
>>>>> laws have
>>>>> > been proposed in the past, but unfortunately *none* of them cover
>>>>> all the
>>>>> > current important instances. Thus we have a rather awkward situation
>>>>> where
>>>>> > Alternative is a subclass of Applicative, but there's no real way to
>>>>> take
>>>>> > advantage of that fact. There are essentially no useful functions
>>>>> that would
>>>>> > end up with signatures that look like
>>>>> >
>>>>> > p :: (Applicative f, Alternative f) => ...
>>>>> >
>>>>> > I'm wondering, therefore, what people think of the idea of making
>>>>> > Alternative entirely independent—just a version of Monoid with a
>>>>> different
>>>>> > kind.
>>>>> >
>>>>> > class Alternative f where
>>>>> >   empty :: f a
>>>>> >   (<|>) :: f a -> f a -> f a
>>>>> >
>>>>> > A second option would be to go with a Functor superclass for
>>>>> Alternative;
>>>>> > that might save some typing over the independent Alternative, and it
>>>>> comes
>>>>> > with the free theorem
>>>>> >
>>>>> > fmap f empty = empty
>>>>>
>>>>> Control.Applicative.optional requires (Functor f, Alternative f),
>>>>> though that's the only function using Alternative that isn't a method
>>>>> of the typeclass that's in there.
>>>>>
>>>>> With AMP, what happens with MonadPlus?  Isn't it equivalent to
>>>>> Monad+Alternative?
>>>>>
>>>>> --
>>>>> Ivan Lazar Miljenovic
>>>>> Ivan.Miljenovic at gmail.com
>>>>> http://IvanMiljenovic.wordpress.com
>>>>> _______________________________________________
>>>>> Libraries mailing list
>>>>> Libraries at haskell.org
>>>>> http://www.haskell.org/mailman/listinfo/libraries
>>>>>
>>>>
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20141107/75d4453c/attachment.html>