Daniel,<br>
New combinator (&lt;:&gt;) that you introduced helps a lot to
understand the whole thing. I think that your explanation should be
included in the next edition of&nbsp; the &quot;Haskell. The Craft of Functional
Programming&quot;, 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 &quot;123&quot;<br>
<br>
unfolds into:<br>
<br>
succeed [] <br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &lt;+&gt; (dig &lt;:&gt; succeed []) <br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &lt;+&gt; (dig &lt;:&gt; (dig &lt;:&gt; succeed []))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &lt;+&gt; (dig &lt;:&gt; (dig &lt;:&gt; (dig &lt;:&gt; succeed [])))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &lt;+&gt; (dig &lt;:&gt; (dig &lt;:&gt; (dig &lt;:&gt; (dig &lt;:&gt; pList dig)))) <br>
<br>
where:<br>
succeed [] ~~&gt; [(&quot;&quot;, &quot;123&quot;)]<br>
(dig &lt;:&gt; succeed [])&nbsp; ~~&gt; [(&quot;1&quot;, &quot;23&quot;)]<br>
(dig &lt;:&gt; (dig &lt;:&gt; succeed [])) ~~&gt; [(&quot;12&quot;, &quot;3&quot;)]<br>
(dig &lt;:&gt; (dig &lt;:&gt; (dig &lt;:&gt; succeed []))) ~~&gt; [(&quot;123&quot;, &quot;&quot;)]<br>
(dig &lt;:&gt; (dig &lt;:&gt; (dig &lt;:&gt; (dig &lt;:&gt; pList dig)))) ~~&gt; []<br>
<br>
the last one returns [] because:<br>
(dig &gt;*&gt; dig &gt;*&gt; dig &gt;*&gt; dig) &quot;123&quot; ~~&gt; []<br>
<br>
As a result we get:<br>
<br>
[(&quot;&quot;, &quot;123&quot;)] ++ [(&quot;1&quot;, &quot;23&quot;)] ++ [(&quot;12&quot;, &quot;3&quot;)] ++ [(&quot;123&quot;, &quot;&quot;)] ++ [] <br>
<br>
&nbsp; &nbsp; &nbsp; ~~&gt;&nbsp; [(&quot;&quot;, &quot;123&quot;), (&quot;1&quot;, &quot;23&quot;), (&quot;12&quot;, &quot;3&quot;), (&quot;123&quot;, &quot;&quot;)]<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> &lt;<a href="mailto:daniel.is.fischer@web.de">daniel.is.fischer@web.de</a>&gt; 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>&gt; Daniel,<br>&gt; I am still trying to figure out the order of function applications in the<br>&gt; parser returning list of objects (I attached again the code to the end of
<br>&gt; this message for convenience).<br>&gt;<br>&gt; You wrote:<br>&gt; (&gt;*&gt;) associates to the right, hence<br>&gt; p &gt;*&gt; (p &gt;*&gt; (p &gt;*&gt; (... &gt;*&gt; (p &gt;*&gt; succeed [])...)))<br>&gt;<br>
&gt; I don&#39;t understand where (p &gt;*&gt; succeed []) comes from?<br><br>The final &#39;succeed []&#39; comes from a) the definition of pList p as<br>pList p = succeed [] `alt` ((p &gt;*&gt; pList p) `build` (uncurry (:)))
<br>plus b) the assumption that p should be a parser which doesn&#39;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 &quot;12ab&quot;
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=== succeed [] &quot;12ab&quot; ++ (((dig &gt;*&gt; pList dig) `build` (uncurry (:))) &quot;12ab&quot;)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=== [([],&quot;12ab&quot;)] ++ [(&#39;1&#39; : ds,rem) | (ds,rem) &lt;- pList dig &quot;2ab&quot;]
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-- since dig &quot;12ab&quot; = [(&#39;1&#39;,&quot;2ab&quot;)]<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=== [([],&quot;12ab&quot;)] ++ [(&#39;1&#39; : ds,rem) | (ds,rem) &lt;- (succed [] `alt`<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(((dig &gt;*&gt; pList dig) `build` (uncurry (:))))) &quot;2ab&quot;]
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=== [([],&quot;12ab&quot;)] ++ [(&#39;1&#39; : ds,rem) | (ds,rem) &lt;- ([([],&quot;2ab&quot;)] ++<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[(&#39;2&#39; : ds2,rem2) | (ds2,rem2) &lt;- pList dig &quot;ab&quot;])]<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=== [([],&quot;12ab&quot;),(&quot;1&quot;,&quot;2ab&quot;)] ++<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[(&#39;1&#39; : &#39;2&#39; : ds2,rem2) | (ds2,rem2) &lt;- (succeed [] `alt`<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(((dig &gt;*&gt; pList dig) `build` (uncurry (:))))) &quot;ab&quot;]
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=== [([],&quot;12ab&quot;),(&quot;1&quot;,&quot;2ab&quot;)] ++<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[(&#39;1&#39; : &#39;2&#39; : ds2,rem2) | (ds2,rem2) &lt;- ([([],&quot;ab&quot;)] ++<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(((dig &gt;*&gt; pList dig) `build` (uncurry (:))) &quot;ab&quot;))]
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-- now &#39;dig&#39; and hence &#39;dig &gt;*&gt; pList dig&#39; fail on the input &quot;ab&quot;, thus<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=== [([],&quot;12ab&quot;),(&quot;1&quot;,&quot;2ab&quot;),(&quot;12&quot;,&quot;ab&quot;)]
<br><br>Hum, I find that a bit hard to read myself, so let&#39;s introduce an alias for<br>&#39;alt&#39;, call it (&lt;+&gt;) and a new combinator which joins (&gt;*&gt;) and<br>&#39;build (uncurry (:))&#39; :<br>(&lt;:&gt;) :: Parser a b -&gt; Parser a [b] -&gt; Parser a [b]
<br>p1 &lt;:&gt; p2 = \inp -&gt; [(x:ys,rem2)&nbsp;&nbsp;| (x,rem1) &lt;- p1 inp, (ys,rem2) &lt;- p2 rem1]<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-- or p1 &lt;:&gt; p2 = build (p1 &gt;*&gt; p2) (uncurry (:))<br><br>Then we have (because p1 &lt;:&gt; (p2 &lt;+&gt; p3) === (p1 &lt;:&gt; p2) &lt;+&gt; (p1 &lt;:&gt; p3))
<br>pList p<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=== succeed [] &lt;+&gt; (p &lt;:&gt; pList p)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=== succeed [] &lt;+&gt; (p &lt;:&gt; (succeed [] &lt;+&gt; (p &lt;:&gt; pList p)))<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=== succeed [] &lt;+&gt; (p &lt;:&gt; succeed []) &lt;+&gt; (p &lt;:&gt; (p &lt;:&gt; pList p))
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=== succeed [] &lt;+&gt; (p &lt;:&gt; succeed []) &lt;+&gt; (p &lt;:&gt; (p &lt;:&gt; (succeed [] &lt;+&gt;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(p &lt;:&gt; pList p))))<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=== succeed []<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&lt;+&gt; (p &lt;:&gt; succeed [])
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&lt;+&gt; (p &lt;:&gt; (p &lt;:&gt; succeed []))<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&lt;+&gt; (p &lt;:&gt; (p &lt;:&gt; (p &lt;:&gt; succeed [])))<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&lt;+&gt; (p &lt;:&gt; (p &lt;:&gt; (p &lt;:&gt; (p &lt;:&gt; pList p))))<br>
and so on.<br>And when we request more p&#39;s than the input provides, pList p isn&#39;t reached<br>anymore and recursion stops (e.g. with p = dig and input &quot;123&quot; or &quot;123a45&quot;,<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 &quot;123&quot;, 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&#39;s ended by a<br>&#39;succeed []&#39;.<br><br>So the order of evaluation of<br>pList p input = (succeed [] &lt;+&gt; (p &lt;:&gt; pList p)) input<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;= succeed [] input ++ (p &lt;:&gt; 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 &lt;:&gt; 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&#39;s empty,<br>we&#39;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&#39;),([obj2,obj3],rem&#39;&#39;)...]<br>2.3. return the list of (obj:objlist,rem2) pairs<br><br>&gt;<br>&gt; Yet, if the order is as you describe, everything goes well, for example:
<br>&gt;<br>&gt; comp1 = dig &gt;*&gt; dig&nbsp;&nbsp; has type&nbsp;&nbsp;- Parser char (char, char)<br>&gt; comp2 = dig &gt;*&gt; (succeed [])&nbsp;&nbsp;has type&nbsp;&nbsp;- Parser char (char, [a])<br>&gt; pl1 = comp2 `build` (uncurry (:)) has type - Parser char (char, [char])
<br><br>pl1 has type Parser Char [Char] because &#39;uncurry (:)&#39; has type (a,[a]) -&gt; [a]<br><br>&gt;<br>&gt; At first run<br>&gt; (succeed []) `alt` ((p &gt;*&gt; pList p) `build` (uncurry (:)))<br>&gt;<br>&gt; should be:
<br>&gt; [] ++&nbsp;&nbsp;((p &gt;*&gt; pList p) `build` (uncurry (:)))<br><br>(succeed [] `alt` ((p &gt;*&gt; pList p) `build` (uncurry (:)))) input<br>gives<br>[([],input)] ++ ((p &gt;*&gt; pList p) `build` (uncurry (:))) input<br>
&gt;<br>&gt; so how we get:<br>&gt; (p &gt;*&gt; succeed []) ?<br>&gt;<br>&gt; Thanks,<br>&gt; Dima<br>&gt;<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>