[Haskell-cafe] Newbie: a parser for a list of objects?

[Daniel Fischer]

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