<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
> behaviours are surprising, it's because there is a lack of
understanding of the tool, and not an issue with the tool itself.<br>
Hello, Issac. Yes, it will be the most correct statement :)<br>
<blockquote type="cite"
cite="mid:CADNFHyN7h=R7_+1OWRYBejOwmaGpHRsEGDJ8a_BymYdo=gSH=A@mail.gmail.com">
<div dir="ltr">
<div><br>
</div>
<div>Also, trifecta has the same backtracking semantics as
megaparsec.</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr">On Fri, Aug 24, 2018 at 8:10 PM Paul <<a
href="mailto:aquagnu@gmail.com" moz-do-not-send="true">aquagnu@gmail.com</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">may be
because I always hit similar problems and needs different
tricks <br>
with them, so I an not sure that parser combinators are good
solution. <br>
Btw, usually I use standard parser combinator which is related
to GHC <br>
itself (in the 'base' package), so I'm not sure how all those
P.C. <br>
libraries are similar (may be MegaParsec has different
behavior). But <br>
it's my IMHO: I'm not sure that P.C. libraries are good for
serious <br>
parsing tasks: you should be concentrated on the task and not
to spend <br>
time in solving of such surprises like that.<br>
<br>
Btw, some time ago I found this list of libs <br>
<a
href="https://www.reddit.com/r/haskell/comments/46u45o/what_is_the_current_state_of_parser_libraries_in/"
rel="noreferrer" target="_blank" moz-do-not-send="true">https://www.reddit.com/r/haskell/comments/46u45o/what_is_the_current_state_of_parser_libraries_in/</a>
<br>
and Trifecta looks interesting but I did not try it<br>
<br>
<br>
24.08.2018 12:44, Doaitse Swierstra wrote:<br>
><br>
>> Op 24 aug. 2018, om 7:33 heeft Paul <<a
href="mailto:aquagnu@gmail.com" target="_blank"
moz-do-not-send="true">aquagnu@gmail.com</a>> het
volgende geschreven:<br>
>><br>
>>> Of course the example above can be mitigated by
moving the char '-' outside the alternative.<br>
>> Right, this works fine:<br>
>><br>
>> pq :: Parsec Void String Bool<br>
>> pq = do<br>
>> char '-'<br>
>> (q <|> p)<br>
>><br>
>> which for me, means that Haskell has not real
backtracking.<br>
> You are confusing the language “Haskell” with the library
“Parsec”. Parsec is just one of the many parser combinator
libraries.<br>
><br>
>> Btw, `Alternative` is not backtracking (as well as
List permutations).<br>
> The class “Alternative” does in no way specify how
parsers should behave; it defines an interface. One might
expect <|> to be associative, but even that is in no way
guaranteed.<br>
><br>
>> 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.<br>
> - Some libraries do not need “try” constructs to set
backtrack points, but may be a bit slower; other libraries are
more greedy and a bit faster.<br>
> - Some parsers keep track of where you are in the input
at some cost, others just parse as fast as possible without
having to update line and position counters (handy when you
know the input is correct since it was machine-generated).<br>
> - Some libraries provide nice error messages about what
was expected at some cost, other libraries just report that
they did not find a parse.<br>
> - Some libraries try to “repair” the input and continue
parsing when they cannot proceed otherwise, some others just
stop when they get stuck.<br>
> - Some libraries hang on to the input so they may
backtrack to a point far back, some libraries work in an
online way and pursue all parses “in parallel”, i.e. they
perform a breadth first search for a successful parse.<br>
> - Some libraries analyse the grammar before parsing
starts and warn for non-sensical parsers, others just do not.<br>
> - Some libraries already return part of the computed
result during the parsing process -and thus exhibit online
behaviour-, other libraries (usually the monadic ones)
construct a huge closure describing the result, which only
becomes available when a succesful parse was found.<br>
> - Some libraries analyse a grammar for left-recursion
and transform them into an equivalent non-left-recusrive one
at some costs.<br>
> - Some libraries memoise the parsing, and may be
faster, but in return cannot handle real monadic constructs.<br>
> - Etc., Etc.<br>
><br>
> My impression is that with respect to parser combinators
you just jump a bit too fast to a conclusion.<br>
><br>
> Doaitse<br>
><br>
><br>
>><br>
>> 23.08.2018 22:41, Olaf Klinke wrote:<br>
>>> Dear Cafe,<br>
>>><br>
>>> 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?<br>
>>> 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].<br>
>>><br>
>>> Minimal code example and context below.<br>
>>><br>
>>> Thanks,<br>
>>> Olaf<br>
>>><br>
>>> [1] <a
href="http://hackage.haskell.org/package/parser-combinators-1.0.0/docs/Control-Applicative-Combinators.html"
rel="noreferrer" target="_blank" moz-do-not-send="true">http://hackage.haskell.org/package/parser-combinators-1.0.0/docs/Control-Applicative-Combinators.html</a><br>
>>><br>
>>> import Text.Megaparsec<br>
>>> import Text.Megaparsec.Char<br>
>>> import Data.Void<br>
>>><br>
>>> p :: Parsec Void String Bool<br>
>>> p = do<br>
>>> char '-'<br>
>>> string "True"<br>
>>> return True<br>
>>> q :: Parsec Void String Bool<br>
>>> q = do<br>
>>> char '-'<br>
>>> string "False"<br>
>>> return False<br>
>>><br>
>>>>>> parseTest (p <|> q) "-True"<br>
>>> True<br>
>>>>>> parseTest (p <|> q) "-False"<br>
>>> 1:2:<br>
>>> unexpected "Fals"<br>
>>> expecting "True"<br>
>>> -- Since q can parse "-False", I would expect (p
<|> q) to parse "-False", too.<br>
>>><br>
>>> Context:<br>
>>> 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.<br>
>>> _______________________________________________<br>
>>> Haskell-Cafe mailing list<br>
>>> To (un)subscribe, modify options or view archives
go to:<br>
>>> <a
href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe"
rel="noreferrer" target="_blank" moz-do-not-send="true">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
>>> Only members subscribed via the mailman list are
allowed to post.<br>
>> _______________________________________________<br>
>> Haskell-Cafe mailing list<br>
>> To (un)subscribe, modify options or view archives go
to:<br>
>> <a
href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe"
rel="noreferrer" target="_blank" moz-do-not-send="true">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
>> Only members subscribed via the mailman list are
allowed to post.<br>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a
href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe"
rel="noreferrer" target="_blank" moz-do-not-send="true">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to
post.</blockquote>
</div>
</blockquote>
<br>
</body>
</html>