Eliminate/move class Alternative

Martijn van Steenbergen martijn at van.steenbergen.nl
Mon May 4 17:15:03 EDT 2009

Ben Franksen wrote:
> 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).

The trick is to not constrain the result type: pFail should be 
polymorphic in its result type. Suppose you use the list of successes 

> type Parser s a = [s] -> [(a, [s])]

Then pFail may be defined as:

> pFail :: Parser s a
> pFail = const []

i.e. polymorphic in output (and input too), because [] :: [a] is 
polymorphic in its element type.

I'm pretty sure most if not all modern parse libraries contain such a 



More information about the Libraries mailing list