[Haskell-beginners] parser for expressions

Stephen Tetley stephen.tetley at gmail.com
Sun Dec 27 14:11:24 EST 2009

Hi John

Are you working from the "Monadic Parser Combinators" paper by Graham
Hutton and Erik Meijer?

That was written for Gofer a predecessor to Haskell which is similar
Haskell but has some slight differences - particularly in Haskell you
would really want to make the Parser a newtype then use can make a
Monad instance.

Here are some of the bits from that paper with the newtype for Parser
- unfortunately it adds some clutter. I think there should be a full
version converted to Haskell if you do a web search. You will
certainly need the sat and char parsers from the paper - I can post
them later if you can't find them through a web search:

newtype Parser s a = Parser { getParser :: [s] -> [(a,[s])] }

result :: a -> Parser s a
result v = Parser $ \inp -> [(v,inp)]

bind :: Parser s a -> (a -> Parser s b) -> Parser s b
p `bind` f = Parser $ \inp ->
  concat [ (getParser . f) v inp' | (v,inp') <- (getParser p) inp]

instance Monad (Parser s) where
  return a = result a
  mf >>= k  = mf `bind` k

pFail :: Parser s a
pFail = Parser $ \cs -> []

pSymbol :: Eq s => s -> Parser s s
pSymbol a = Parser $ \inp -> case inp of
                               (b:bs) | a == b -> [(b,bs)]
                               _               -> []

(+++) :: Parser s a -> Parser s a -> Parser s a
t +++ w  = Parser $ \inp -> case (getParser t) inp of
     []  -> (getParser w) inp
     [(v,out)] -> [(v,out)]

More information about the Beginners mailing list