<div dir="ltr">Thanks Kyle,<div><br></div><div>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 :)</div>
<div><br></div><div>I will now explore using go-routines to implement laziness.</div><div><br></div><div>Thank you so much for your input.</div><div><br></div><div>Regards,</div><div>Kashyap</div><div><div><br></div><div>
<br></div></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Thu, Jul 25, 2013 at 1:44 AM, Kyle Miller <span dir="ltr"><<a href="mailto:kmill31415@gmail.com" target="_blank">kmill31415@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">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.<div>
<br></div><div>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'.<br>
<div><br></div><div>Assuming you're wanting a full backtracking parser, here's a counterexample for the "take 1":</div><div><br></div><div>needsList = do</div><div> v <- many (char 'a')</div>
<div> a <- return v -- just to make sure the "take 1" bind happens at least once before the next step</div><div> guard $ length a == 3</div><div> return a</div><div><br></div><div>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.</div>
</div><div><br></div><div>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.</div>
<div><br></div><div>Kyle</div><div><br></div><div>[1] <a href="https://github.com/kmill/metaview/blob/master/src/mparserlib/parser.py" target="_blank">https://github.com/kmill/metaview/blob/master/src/mparserlib/parser.py</a></div>
</div>
<div class="gmail_extra"><br><br><div class="gmail_quote"><div><div class="h5">On Wed, Jul 24, 2013 at 10:26 AM, C K Kashyap <span dir="ltr"><<a href="mailto:ckkashyap@gmail.com" target="_blank">ckkashyap@gmail.com</a>></span> wrote:<br>
</div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div class="h5"><div dir="ltr">Dear Cafe,<div><br></div><div>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"</div>
<div>While doing the implementation - I looked at bind closely</div><div><br></div><div><div>bind :: Parser a -> (a -> Parser b) -> Parser b</div><div>p `bind` f = \inp -> concat [f v inp' | (v,inp') <- p inp]</div>
<div><br></div><div>I wondered if the result needs the complete list - wouldn't just the first successful value suffice?</div><div>Perhaps -</div><div>p `bind` f = \inp -> take 1 $ concat [f v inp' | (v,inp') <- p inp]<br>
</div><div><br></div><div>Will this miss out matches?</div><div><br></div><div><br></div><div>Regards,</div><div>Kashyap</div></div><div><br></div><div>[1] <a href="https://github.com/ckkashyap/parsec/blob/master/parsec.go" target="_blank">https://github.com/ckkashyap/parsec/blob/master/parsec.go</a></div>
<div>[2] Monadic Parser Combinators: Graham Hutton, Erik Meijer</div></div>
<br></div></div><div class="im">_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></div></blockquote></div><br></div>
</blockquote></div><br></div>