Daniel, I am still trying to figure out the order of function applications in the parser returning list of objects (I attached again the code to the end of this message for convenience). You wrote: (>*>) associates to the right, hence p >*> (p >*> (p >*> (... >*> (p >*> succeed [])...))) I don't understand where (p >*> succeed []) comes from? Yet, if the order is as you describe, everything goes well, for example: comp1 = dig >*> dig has type - Parser char (char, char) comp2 = dig >*> (succeed []) has type - Parser char (char, [a]) pl1 = comp2 `build` (uncurry (:)) has type - Parser char (char, [char]) At first run (succeed []) `alt` ((p >*> pList p) `build` (uncurry (:))) should be: [] ++ ((p >*> pList p) `build` (uncurry (:))) so how we get: (p >*> succeed []) ? Thanks, Dima --- module MyParser where import Data.Char type Parse a b = [a] -> [(b, [a])] none :: Parse a b none = \inp -> [] succeed :: b -> Parse a b succeed val = \inp -> [(val, inp)] spot :: (a -> Bool) -> Parse a a spot p = \inp -> case inp of [] -> [] (x:xs) -> if (p x) then [(x, xs)] else [] alt :: Parse a b -> Parse a b -> Parse a b alt p1 p2 = \inp -> p1 inp ++ p2 inp bracket = spot (=='(') dash = spot (== '-') dig = spot isDigit alpha = spot isAlpha infixr 5 >*> (>*>) :: Parse a b -> Parse a c -> Parse a (b, c) (>*>) p1 p2 = \inp -> [((x,y), rem2) |(x, rem1) <- p1 inp, (y, rem2) <- p2 rem1] build :: Parse a b -> (b -> c) -> Parse a c build p f = \inp -> [ (f x, rem) | (x, rem) <- p inp] pList :: Parse a b -> Parse a [b] pList p = (succeed []) `alt` ((p >*> pList p) `build` (uncurry (:))) comp1 = dig >*> dig comp2 = dig >*> (succeed []) pl1 = comp2 `build` (uncurry (:)) test = pList dig On 3/28/07, Daniel Fischer <daniel.is.fischer@web.de> wrote:
Am Dienstag, 27. März 2007 12:15 schrieb Dmitri O.Kondratiev:
Thanks Daniel! Things are getting more in shape, yet I still can not fully comprehend the expression:
((p >*> pList p) `build` (uncurry (:)))
where
(>*>) :: Parse a b -> Parse a c -> Parse a (b, c) (>*>) p1 p2 inp = [((x,y), rem2) |(x, rem1) <- p1 inp, (y, rem2) <- p2 rem1]
build :: Parse a b -> (b -> c) -> Parse a c build p f inp = [ (f x, rem) | (x, rem) <- p inp]
So in fact recursive application:
p >*> pList p
should unfold in something like:
((p >*> p) >*> p) >*> p ...
(>*>) associates to the right, hence p >*> (p >*> (p >*> (... >*> (p >*> succeed [])...)))
and *all* iterations of
p >*> pList p
will be done *before* 'build' will be applied?
Correct?
Think so. Though it might be conceivable that 'build' would be partially applied before. After p has parsed the first item x1, leaving the remainder rem of the input, we can see that the result will be [(x1:lst,rem2) | (lst,rem2) <- pList p rem] and we know that pList p never fails, due to 'succeed []', so that would be more efficient than constructing and destroying a lot of pairs. I've no idea whether a compiler would do that transformation, though I'd be interested to know.
Thanks, Dima
Cheers, Daniel