Daniel,<br>
New combinator (<:>) that you introduced helps a lot to
understand the whole thing. I think that your explanation should be
included in the next edition of the "Haskell. The Craft of Functional
Programming", I really mean it.<br>
<br>
To summarize how I now understand the parser:<br>
<br>
Using your combinators, for example:<br>
<br>
pList dig "123"<br>
<br>
unfolds into:<br>
<br>
succeed [] <br>
<+> (dig <:> succeed []) <br>
<+> (dig <:> (dig <:> succeed []))<br>
<+> (dig <:> (dig <:> (dig <:> succeed [])))<br>
<+> (dig <:> (dig <:> (dig <:> (dig <:> pList dig)))) <br>
<br>
where:<br>
succeed [] ~~> [("", "123")]<br>
(dig <:> succeed []) ~~> [("1", "23")]<br>
(dig <:> (dig <:> succeed [])) ~~> [("12", "3")]<br>
(dig <:> (dig <:> (dig <:> succeed []))) ~~> [("123", "")]<br>
(dig <:> (dig <:> (dig <:> (dig <:> pList dig)))) ~~> []<br>
<br>
the last one returns [] because:<br>
(dig >*> dig >*> dig >*> dig) "123" ~~> []<br>
<br>
As a result we get:<br>
<br>
[("", "123")] ++ [("1", "23")] ++ [("12", "3")] ++ [("123", "")] ++ [] <br>
<br>
~~> [("", "123"), ("1", "23"), ("12", "3"), ("123", "")]<br>
<br>
Thanks again Daniel for your great help!<br>
Dima<br><br><div><span class="gmail_quote">On 3/28/07, <b class="gmail_sendername">Daniel Fischer</b> <<a href="mailto:daniel.is.fischer@web.de">daniel.is.fischer@web.de</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Am Mittwoch, 28. März 2007 11:57 schrieb Dmitri O.Kondratiev:<br>> Daniel,<br>> I am still trying to figure out the order of function applications in the<br>> parser returning list of objects (I attached again the code to the end of
<br>> this message for convenience).<br>><br>> You wrote:<br>> (>*>) associates to the right, hence<br>> p >*> (p >*> (p >*> (... >*> (p >*> succeed [])...)))<br>><br>
> I don't understand where (p >*> succeed []) comes from?<br><br>The final 'succeed []' comes from a) the definition of pList p as<br>pList p = succeed [] `alt` ((p >*> pList p) `build` (uncurry (:)))
<br>plus b) the assumption that p should be a parser which doesn't succed on an<br>empty input and that the input is finite (though the second point is not<br>necessary).<br><br>Let us unfold a little:<br><br>pList dig "12ab"
<br> === succeed [] "12ab" ++ (((dig >*> pList dig) `build` (uncurry (:))) "12ab")<br> === [([],"12ab")] ++ [('1' : ds,rem) | (ds,rem) <- pList dig "2ab"]
<br> -- since dig "12ab" = [('1',"2ab")]<br> === [([],"12ab")] ++ [('1' : ds,rem) | (ds,rem) <- (succed [] `alt`<br> (((dig >*> pList dig) `build` (uncurry (:))))) "2ab"]
<br> === [([],"12ab")] ++ [('1' : ds,rem) | (ds,rem) <- ([([],"2ab")] ++<br> [('2' : ds2,rem2) | (ds2,rem2) <- pList dig "ab"])]<br>
=== [([],"12ab"),("1","2ab")] ++<br> [('1' : '2' : ds2,rem2) | (ds2,rem2) <- (succeed [] `alt`<br> (((dig >*> pList dig) `build` (uncurry (:))))) "ab"]
<br> === [([],"12ab"),("1","2ab")] ++<br> [('1' : '2' : ds2,rem2) | (ds2,rem2) <- ([([],"ab")] ++<br> (((dig >*> pList dig) `build` (uncurry (:))) "ab"))]
<br> -- now 'dig' and hence 'dig >*> pList dig' fail on the input "ab", thus<br> === [([],"12ab"),("1","2ab"),("12","ab")]
<br><br>Hum, I find that a bit hard to read myself, so let's introduce an alias for<br>'alt', call it (<+>) and a new combinator which joins (>*>) and<br>'build (uncurry (:))' :<br>(<:>) :: Parser a b -> Parser a [b] -> Parser a [b]
<br>p1 <:> p2 = \inp -> [(x:ys,rem2) | (x,rem1) <- p1 inp, (ys,rem2) <- p2 rem1]<br> -- or p1 <:> p2 = build (p1 >*> p2) (uncurry (:))<br><br>Then we have (because p1 <:> (p2 <+> p3) === (p1 <:> p2) <+> (p1 <:> p3))
<br>pList p<br> === succeed [] <+> (p <:> pList p)<br> === succeed [] <+> (p <:> (succeed [] <+> (p <:> pList p)))<br> === succeed [] <+> (p <:> succeed []) <+> (p <:> (p <:> pList p))
<br> === succeed [] <+> (p <:> succeed []) <+> (p <:> (p <:> (succeed [] <+><br> (p <:> pList p))))<br> === succeed []<br> <+> (p <:> succeed [])
<br> <+> (p <:> (p <:> succeed []))<br> <+> (p <:> (p <:> (p <:> succeed [])))<br> <+> (p <:> (p <:> (p <:> (p <:> pList p))))<br>
and so on.<br>And when we request more p's than the input provides, pList p isn't reached<br>anymore and recursion stops (e.g. with p = dig and input "123" or "123a45",<br>the last line will fail because it demands four digits from the beginning of
<br>the input, but there are only three).<br>If p would succeed on an empty input, e.g. p = succeed 1 or the input is an<br>infinite list of successes for p, e.g. p = dig and input = cycle "123", the<br>unfolding would never stop, producing an infinite list of results, but each
<br>of these results wolud come from a finite chain of p's ended by a<br>'succeed []'.<br><br>So the order of evaluation of<br>pList p input = (succeed [] <+> (p <:> pList p)) input<br> = succeed [] input ++ (p <:> pList p) input
<br>is<br>1. evaluate the first argument of (++), succeed [] input == [([],input)]<br>Since this is not _|_, we need also the second argument of (++), so<br>2. evaluate (p <:> pList p) input (to whnf first, more if required)
<br>3. evaluate (++) as far as needed<br><br>2. is further split,<br>2.1. evaluate p input, giving a list of (obj,rem) pairs -- if that's empty,<br>we're done, also if that produces _|_<br>2.2. (partially) evaluate pList p rem (goto 1.) giving a list of
<br>(objlist,rem2); [([],rem),([obj2],rem'),([obj2,obj3],rem'')...]<br>2.3. return the list of (obj:objlist,rem2) pairs<br><br>><br>> Yet, if the order is as you describe, everything goes well, for example:
<br>><br>> comp1 = dig >*> dig has type - Parser char (char, char)<br>> comp2 = dig >*> (succeed []) has type - Parser char (char, [a])<br>> pl1 = comp2 `build` (uncurry (:)) has type - Parser char (char, [char])
<br><br>pl1 has type Parser Char [Char] because 'uncurry (:)' has type (a,[a]) -> [a]<br><br>><br>> At first run<br>> (succeed []) `alt` ((p >*> pList p) `build` (uncurry (:)))<br>><br>> should be:
<br>> [] ++ ((p >*> pList p) `build` (uncurry (:)))<br><br>(succeed [] `alt` ((p >*> pList p) `build` (uncurry (:)))) input<br>gives<br>[([],input)] ++ ((p >*> pList p) `build` (uncurry (:))) input<br>
><br>> so how we get:<br>> (p >*> succeed []) ?<br>><br>> Thanks,<br>> Dima<br>><br>Anytime,<br>Daniel<br><br></blockquote></div><br><br clear="all"><br>-- <br>Dmitri O Kondratiev<br><a href="mailto:dokondr@gmail.com">
dokondr@gmail.com</a><br><a href="http://www.geocities.com/dkondr">http://www.geocities.com/dkondr</a>