<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>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>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>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>*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>*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>(succeed []) `alt`((p >*> pList p) `build` (uncurry (:)))<br><br>has the following execution order:<br>1) >*><br>2) 'build'<br>3) 'alt'<br><br>It seems that operation >*> should be done as many times as many elements the input list has. Right?
<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>How can that be?<br>How recursion termination conditinon is expressed in pList?<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>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>(>*>) 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>