[Haskell-cafe] Parsec question

[C K Kashyap]

Thanks Kyle,

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.

Regards,
Kashyap




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 [1] 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.
>
> Kyle
>
> [1] 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[1] parsec in go using the "Monadic Parser
>> Combinators" paper [2] . I've been able to implement "plus" "bind" and
>> "many"
>> 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?
>>
>>
>> Regards,
>> Kashyap
>>
>> [1] https://github.com/ckkashyap/parsec/blob/master/parsec.go
>> [2] Monadic Parser Combinators: Graham Hutton, Erik Meijer
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130725/efa4909b/attachment.htm>