[Haskell-cafe] Parsec question
C K Kashyap
ckkashyap at gmail.com
Thu Jul 25 06:56:36 CEST 2013
My initial implementation was evaluating the whole list - the current one
though just returns the first successful result. Anyway, I think I need the
backtracking - I would want the "aaa" as the result :)
I will now explore using go-routines to implement laziness.
Thank you so much for your input.
On Thu, Jul 25, 2013 at 1:44 AM, Kyle Miller <kmill31415 at gmail.com> wrote:
> Because of laziness, you do in a sense only take the first successful
> value. When I've made parser combinators for Python before, I've used
> either generators or exceptions to get lazy evaluation, since computing the
> whole list of possibilities for each bind would ruin the running time of
> the algorithm (or make it never terminate). From your go code, it looks
> like you're evaluating the entire list.
> The bind you give looks like it's for a backtracking parser. For
> non-backtracking, though, I believe it would be possible to use Maybe.
> Parsec has a different bind operator which only lets backtracking happen
> when you explicitly allow it with 'try'.
> Assuming you're wanting a full backtracking parser, here's a
> counterexample for the "take 1":
> needsList = do
> v <- many (char 'a')
> a <- return v -- just to make sure the "take 1" bind happens at least
> once before the next step
> guard $ length a == 3
> return a
> If my input string is "aaaa", then many (char 'a') will produce matches of
> '', 'a', 'aa', 'aaa', and 'aaaa', but the bind will probably force the
> incorrect one of these before it reaches the guard.
> I can't guarantee this is any good, and I haven't looked at it in a while,
> but at  I have an example of using exceptions to get a parsec-like
> backtracking-when-explicitly-allowed parser. I was planning on writing an
> article about how to do this technique, but I never got around to it.
>  https://github.com/kmill/metaview/blob/master/src/mparserlib/parser.py
> On Wed, Jul 24, 2013 at 10:26 AM, C K Kashyap <ckkashyap at gmail.com> wrote:
>> Dear Cafe,
>> I am trying to implement parsec in go using the "Monadic Parser
>> Combinators" paper  . I've been able to implement "plus" "bind" and
>> While doing the implementation - I looked at bind closely
>> bind :: Parser a -> (a -> Parser b) -> Parser b
>> p `bind` f = \inp -> concat [f v inp' | (v,inp') <- p inp]
>> I wondered if the result needs the complete list - wouldn't just the
>> first successful value suffice?
>> Perhaps -
>> p `bind` f = \inp -> take 1 $ concat [f v inp' | (v,inp') <- p inp]
>> Will this miss out matches?
>>  https://github.com/ckkashyap/parsec/blob/master/parsec.go
>>  Monadic Parser Combinators: Graham Hutton, Erik Meijer
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe