Haskell problem

Daan Leijen daan@cs.uu.nl
Fri, 22 Feb 2002 11:44:16 +0100


Hi all,

There exist a really neat solution to this. I think that it is pioneered
by Doaitse Swierstra and Luc Duponcheel in their parser combinators:

http://www.cs.uu.nl/~doaitse/Papers/1996/LL1.pdf

> > > I'm trying out some combinatorial parsers, and I ran into a slightly
> > > inelegant construction. To parse a sequence of things, we have a function
> > > like
> > >
> > > pThen3 :: (a->b->c->d) -> Parser a -> Parser b -> Parser c -> Parser d
> > >
> > > The problem with this is that this structure has to be duplicated for
> > > pThen2, pThen4, and so on. These other forms are very similar to pThen3,
> >
> > Yes there is a way around this problem. You can use multi parameter type
> > classes to create (and give a type to) a function such as pThenX.
>
> Or, in Standard Haskell you can do something like this:
>
>   infixr `then2`
>   infixr `thenn`
>
>   then2:: Parser b -> Parser c -> ((b,c)->d) -> Parser d
>   thenn:: Parser a b -> ((t->d) -> Parser a d) -> ((b,t)->d) -> Parser a d
>
> and use like this
>
> (p1 `thenn` p2 `thenn` p3 `then2` p4) (\(a,(b,(c,d))) -> whatever)
>
> I'm not sure if you can get rid of the `then2`, but is seems
> quite servicable even so.

The last solution is almost right, what we can do is to define two
(arrow style) combinators, one for sequential composition and
one for lifting values into the Parser type:

  (<*>) :: Parser (a -> b) -> Parser a -> Parser b
  succeed :: a -> Parser a

Now, if we assign a left-associative priority to the (<*>) operator:  infixl 4 <*>,
we can combine it as follows:

  succeed (\x y z -> (x,y,z)) <*> p1 <*> p2 <*> p3

Note that the parens are as follows:

  (((succeed (\x y z -> (x,y,z)) <*> p1) <*> p2) <*> p3)

And indeed, the first component has type: Parser (a -> b -> c -> (a,b,c))
and combines through (<*>) with (p1 :: Parser a) into (Parser (b -> c -> (a,b,c)))
which combines through (<*>) and (p2 :: Parser b) into (Parser (c -> (a,b,c))) etc.

Now, it helps off course to define another combinator:

infix 5  <$>
f <$> p  = succeed f <*> p

And you can write:

  f <$> p1 <*> p2 <*> p3
 where
    f x y z  = (x,y,z)

With a little more cunning, you can also define combinators like (*>) and (<*)
that leave out parser results: parens p  = char '(' *> p <* char ')'

The UU_parsing library embodies the epitome of this technique:
http://www.cs.uu.nl/groups/ST/Software/UU_Parsing/

All the best,
    Daan.

> --
> Jón Fairbairn                                 Jon.Fairbairn@cl.cam.ac.uk
> 31 Chalmers Road                                         jf@cl.cam.ac.uk
> Cambridge CB1 3SZ            +44 1223 570179 (after 14:00 only, please!)
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>