Eliminate/move class Alternative

[Ben Franksen]

Ross Paterson wrote:
> On Sun, Mar 15, 2009 at 11:50:15PM +0100, Ben Franksen wrote:
>> I propose to remove class Alternative and functions depending on it
>> (optional, some, and many) from Control.Applicative. They can be moved
>> into a separate module Control.Alternative if people desire such a class,
>> but I doubt that it has many useful applications, at least in its present
>> form.
> 
> In my opinion, the "killer app" for Alternative is "Parsing Permutation
> Phrases", by Arthur Baars, Andres Loeh and S. Doaitse Swierstra, Haskell
> Workshop 2001.  I've just uploaded a package action-permutations based
> on this.

Taking a quick look at the paper, I can't seem to find the definition of
pFail. Hmm, have to read it more carefully; look at your code, too.

>> Rationale:
>> 
>> Although the idea behind Alternative, i.e. generalize some of the
>> functions commonly found in parser combinator libs, is a nice one, it
>> doesn't work too well in practice, /even/ for the case that has inspired
>> it (namely parsers).
>> 
>> This is mostly due to the class method 'empty'.
>> [...]
>> Second, and more important, is that some parser libs would like to, but
>> cannot offer a sensible implementation for it. For instance, any
>> error-correcting library of parser combinators (like those invented by
>> Swierstra & Duponcheel) need to construct a valid result even in case of
>> a failed parse.
> 
> That's odd: I thought all of Doaitse's parsers had pFail :: p a.

I was refering to the 1996 paper titled "Deterministic, Error-Correcting
Combinator Parsers", where the 'fail' parser needs extra arguments. Maybe I
am dense, but I can't see how to avoid the arguments w/o constraining the
type of the result (which would mean the parsers can't even be instances of
Applicative).

What about the lack of stated laws for Alternative, i.e. how do the monoid
laws interact with the Applicative laws?

Cheers
Ben