Thanks Daniel!<br>Things are getting more in shape, yet I still can not fully comprehend the expression:<br><br>((p >*> pList p) `build` (uncurry (:)))<br><br>where<br><br> (>*>) :: Parse a b -> Parse a c -> Parse a (b, c)
<br> (>*>) p1 p2 inp = [((x,y), rem2) |(x, rem1) <- p1 inp, (y, rem2) <- p2 rem1]<br><br> build :: Parse a b -> (b -> c) -> Parse a c<br> build p f inp = [ (f x, rem) | (x, rem) <- p inp]<br><br>So in fact recursive application:
<br><br>p >*> pList p<br><br>should unfold in something like:<br><br>((p >*> p) >*> p) >*> p ...<br><br>and *all* iterations of <br><br>p >*> pList p<br><br>will be done *before* 'build' will be applied?
<br><br>Correct?<br><br>Thanks,<br>Dima<br><br><div><span class="gmail_quote">On 3/26/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;">> -----Ursprüngliche Nachricht-----<br>> Von: "Dmitri O.Kondratiev" <
<a href="mailto:dokondr@gmail.com">dokondr@gmail.com</a>><br>> Gesendet: 26.03.07 16:44:12<br>> An: <a href="mailto:haskell-cafe@haskell.org">haskell-cafe@haskell.org</a><br>> Betreff: [Haskell-cafe] Newbie: a parser for a list of objects?
<br><br>> Please see my questions inside comments {-- --} :<br>> Thanks!<br>><br>> ---<br>> module Parser where<br>><br>> import Data.Char<br>><br>> type Parse a b = [a] -> [(b, [a])]<br>>
<br>> {--<br>> Newbie: a parser for a list of objects?<br>><br>> I am working with the section 17.5 "Case study: parsing expressions" of the book "Haskell The Craft of Functional Programming", where a parser for a list of objects is defined.
<br>> I called this function pList in order to avoid confusion with 'list' as a term for data structure.<br>><br>> Please help me to understand how pList works (please, see the rest of the code at the end of this message):
<br>> --}<br>><br>> pList :: Parse a b -> Parse a [b]<br>> pList p = (succeed []) `alt`<br>> ((p >*> pList p) `build` (uncurry (:)))<br>><br>><br>> {--<br>> First of all, I don't quite understand why there must be a choice ('alt') between the function ('succeed') that always returns an empty list and the other part? This results in adding [] to the front, why?
<br>><br><br>Well, if the parser p doesn't succeed, we don't want the whole thing to fail. And p will (almost certainly) fail when the end of input is reached.<br>So without the alternative 'succeed []', we'd get
<br><br>pL1 dig "12" = [(('1':y),rem) | (y,rem) <- pL1 dig "2"]<br> = [(('1':y),rem) | (y,rem) <- [(('2':z),rem2) | (z,rem2) <- pL1 dig ""]]
<br> = [(('1':y),rem) | (y,rem) <- [(('2':z),rem2) | (z,rem2) <- []]<br> = [(('1':y),rem) | (y,rem) <- []]<br> = []<br><br>because dig "" = []
<br><br>> I thought that 'simplified' version of pList should still work fine. Trying to prove this I wrote :<br>> --}<br>><br>> pL1 :: Parse a b -> Parse a [b]<br>> pL1 p = (p >*> pL1 p) `build` (uncurry (:))
<br>><br>> {--<br>> Which, as expected, does not work correctly - just gives an empty list [] - but I don't understand why:<br><br>because the parser eventually fails when the end of input is reached.<br>>
<br>> *Parser> t1 "12345"<br>> []<br>> *Parser><br>><br>> Also, I don't understand why the textbook version of pList gives this result:<br>><br>> *Parser> test "12345"
<br>> [("","12345"),("1","2345"),("12","345"),("123","45"),("1234","5"),("12345","")]<br><br>That's because of the order of alt's arguments:
<br><br>(succeed [] `alt` p) inp = [([],inp)] ++ (p inp)<br><br>with pList p = ((p >*> pList p) `build` (uncurry (:))) `alt` succeed []<br>the resulting list woulde be reversed.<br><br>><br>> *Parser><br>>
<br>> In particular, I don't understand where the first element ("","12345") of the resulting list comes from?<br>><br>> I am trying to figure out how pList recursively unfolds. To my mind operators in the expression:
<br>><br>><br>> (succeed []) `alt`((p >*> pList p) `build` (uncurry (:)))<br>><br>> has the following execution order:<br>> 1) >*><br>> 2) 'build'<br>> 3) 'alt'<br>>
<br>No, the first argument of alt gets evaluated first, because (p1 `alt` p2) inp = (p1 inp) ++ (p2 inp), thus we need p1 inp first.<br>Then we see we haven't hit bottom, so we need the second argument of (++) (resp. alt).
<br>So next we need to evaluate p, then pList p, combine the results of those with the second argument of build, uncurry (:).<br><br>> It seems that operation >*> should be done as many times as many elements the input list has. Right?
<br>><br><br>Unfortunately not. Let's stay with pList dig. Say your input starts with n digits.<br>From the example above you can conjecture that length (pList dig inp) == (n+1).<br>Now in the outermost (dig >*> pList dig) branch, you apply (pList dig) to an input beginning with (n-1) digits, returning a list of length n,
<br>to each element of this list you adjoin the first digit, resulting in n + (n-1) + ... + 1 = n*(n+1)/2 applications of (>*>).<br>(Lesson: you need an exclusive choice, using the second parser only if the first one fails and a maximal munch combinator in your library, too)
<br><br>><br>> Signature:<br>><br>> (>*>) :: Parse a b -> Parse a c -> Parse a (b, c)<br>><br>> implies that second argument of the expression:<br>><br>> p >*> pList p<br>><br>
> should be of type 'Parse a c' but in this application it is of type 'Parse a b -> Parse a [b]'<br>><br>c is [b], so p >*> pList p has type Parse a (b,[b]), then<br>(p >*> pList p) `build` (uncurry (:)) has type Parse a [b]
<br><br>> How can that be?<br>> How recursion termination conditinon is expressed in pList?<br><br>recursion terminates when p fails.<br><br>HTH,<br>Daniel<br><br>> --}<br>><br>> none :: Parse a b<br>> none inp = []
<br>><br>> succeed :: b -> Parse a b<br>> succeed val inp = [(val, inp)]<br>><br>> suc:: b -> [a] -> [(b, [a])]<br>><br>> suc val inp = [(val, inp)]<br>><br>> spot :: (a -> Bool) -> Parse a a
<br>> spot p [] = []<br>> spot p (x:xs)<br>> | p x = [(x, xs)]<br>> | otherwise = []<br>><br>> alt :: Parse a b -> Parse a b -> Parse a b<br>> alt p1 p2 inp = p1 inp ++ p2 inp<br>><br>
> bracket = spot (=='(')<br>> dash = spot (== '-')<br>> dig = spot isDigit<br>> alpha = spot isAlpha<br>><br>> infixr 5 >*><br>><br>> (>*>) :: Parse a b -> Parse a c -> Parse a (b, c)
<br>><br>> (>*>) p1 p2 inp = [((x,y), rem2) |(x, rem1) <- p1 inp, (y, rem2) <- p2 rem1]<br>><br>> build :: Parse a b -> (b -> c) -> Parse a c<br>> build p f inp = [ (f x, rem) | (x, rem) <- p inp]
<br>><br>> test = pList dig<br>> t1 = pL1 dig<br>><br>><br>> -----------------------------------------------------------------<br><br><br></blockquote></div><br>