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 <kmill31...@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 <ckkash...@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@haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >> >> >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe