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

[Paul]

 >  Of course the example above can be mitigated by moving the char '-' 
outside the alternative.

Right, this works fine:

   pq :: Parsec Void String Bool
   pq = do
     char '-'
     (q <|> p)

which for me, means that Haskell has not real backtracking. Btw, 
`Alternative` is not backtracking (as well as List permutations). After 
"do" should happen context saving. I think it's possible to be 
implemented manually... As workaround, may be to pick char '-', but 
don't consume it (and to fail if it is not expecting '-') ? Or to switch 
to another parser libs: arrow based, happy, bindings to good known 
libs... For me, parsers combinators absolutely ever are big problem: a 
lot of tricks, low performance, may be it's typical for any "elegant" 
approach.


23.08.2018 22:41, Olaf Klinke wrote:
> 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.
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.