[Haskell-cafe] Parsec question

[Kyle Miller]

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/20130724/6ae2f437/attachment.htm>