Discussion: remove the Applicative superclass from Alternative

[David Feuer]

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/ad99de4f/attachment-0001.html>