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 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 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe