Haskell problem
Tom Pledger
Tom.Pledger@peace.com
Thu, 21 Feb 2002 14:16:43 +1300
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