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

[Olaf Klinke]

Dear Cafe,

can anyone explain the use of an Alternative instance for a parser monad where the parser (p <|> q) does not backtrack automatically when p fails? 
Consider megaparsec for example. When p is a parser that does not backtrack automatically, then (p <|> q) never succeeds with q. While I do understand that fine-grained control of backtracking is desirable for performance reasons in general, it escapes me why such an Alternative instance could be useful. See also "A note on backtracking" in the parser-combinators package documentation [1].

Minimal code example and context below.

Thanks,
Olaf

[1] http://hackage.haskell.org/package/parser-combinators-1.0.0/docs/Control-Applicative-Combinators.html

import Text.Megaparsec
import Text.Megaparsec.Char
import Data.Void

p :: Parsec Void String Bool
p = do
  char '-'
  string "True"
  return True
q :: Parsec Void String Bool
q = do
  char '-'
  string "False"
  return False

>>> parseTest (p <|> q) "-True"
True
>>>  parseTest (p <|> q) "-False"
1:2:
unexpected "Fals"
expecting "True"
-- Since q can parse "-False", I would expect (p <|> q) to parse "-False", too. 

Context:
Of course the example above can be mitigated by moving the char '-' outside the alternative. But we might not have control over whether the two parsers share a common prefix. I am trying to write some code generic in the parser monad and I am having difficulties making my code work for both backtracking and non-backtracking parsers. If possible, I'd like to keep my parser type class devoid of a 'try' combinator, which would be the identity function for parser monads that always backtrack.