[Haskell-cafe] Alternative instance for non-backtracking parsers

[Olaf Klinke]

Thanks to Doaitse for the example. I yet have to wrap my head around it (since I don't know how pChainr is related to <|>) but playing with q parsing the empty string is a good start. 
When you said

> One might expect <|> to be associative, but even that is in no way guaranteed.

I suppose you meant that type class laws can not be enforced, because the documentation of Alternative states that <|> should be associative. It would be quite horrible if the Alternative instances of parsers weren't. 

@Paul: I think that parser combinator libraries are one of the most wonderful things functional programming has given us. How else would you parse your input data? Anything cobbled together manually with the help of some Read instances is bound to be unmaintainable and does not yield good error messages. What would you suggest as a replacement? How would you write composable parsers for a complicated file type? 

Today I added a 'try' method to my MonadParse type class. This lets me write (try p <|> q) generically. An instance for Attoparsec would declare try=id, since it always backtracks. We'll see how this goes. 

What I learned form this thread is:
* arrange your usages of <|> so that both sides can never share a common prefix, then no backtracking will be necessary
* for that reason, some parsers like Megaparsec define their Alternative instances the way they do, without backtracking. 

Please allow one more question:
Is the backtracking performance penalty linear in the amount of backtracking? That is, suppose that 
p = char '-' >> someHugeParser
q = char '-' >> anotherHugeParser
Could (try p <|> q) decide after seeing two characters that p fails and commit to the second branch, freeing memory? 

Thanks,
Olaf