Haskell problem

[Tom Pledger]

Mark Wotton writes:
 | Hi,
 | 
 | 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
 | pThen3 combine p1 p2 p3 toks =
 |         [(combine v1 v2 v3, toks3) | (v1, toks1) <- p1 toks,
 |                                      (v2, toks2) <- p2 toks1,
 |                                      (v3, toks3) <- p3 toks2]
 | 
 | 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,
 | but there seems to be no way to capture this in Haskell's type system, as
 | the combine function has a different signature for each pThenX. (This is
 | actually the first time the Haskell type system has got in my way rather
 | than helping.) Is there a way around this problem?

If you can build the list of tokens into the state of your Parser
monad - which would include making  Parser a  a distinct type instead
of an alias for  [Token] -> [(a, Token)]  - you could condense pThen3
down to this:

    pThen3 combine p1 p2 p3 toks
        = do v1 <- p1
             v2 <- p2
             v3 <- p3
             return (combine v1 v2 v3)

which is equivalent to the liftM3 function from the Monad library.
You'd still be stuck with a family of lifting functions, but at least
they're predefined.  I don't see any way of getting by with a fixed
number of lifting functions, unless you're willing to clutter the call
sites:

    infixl 0 `ap`
    ap :: Parser (a -> b) -> Parser a -> Parser b
    ap = Monad.ap
    ...
    ... Monad.liftM f p1 `ap` p2 `ap` p3 `ap` p4

Regards,
Tom