a simple parser monad

ParserMonad.hs

{-# OPTIONS -Wall -fwarn-tabs -fno-warn-type-defaults  #-}
 
-- The basic definition of the parsing monad.
 
module Parser (Parser,                  
                   get,
                   choose,
                   (<|>),
                   satisfy,
                   doParse,  
                   ) where
 
newtype Parser a b = P ([a] -> [(b, [a])])
 
doParse :: Parser a b -> [a] -> [(b, [a])] 
doParse (P p) s = p s
 
-- | Return the next character
get :: Parser a a
get = P (\cs -> case cs of 
                (x:xs) -> [ (x,xs) ]
                []     -> [])
 
-- | Return the next character if it satisfies the given predicate
satisfy :: (a -> Bool) -> Parser a a
satisfy p = do c <- get
               if (p c) then return c else fail "End of input"
 
instance Monad (Parser a) where
  -- (>>=) :: Parser a -> (a -> Parser b) -> Parser b
  p1 >>= fp2 = P (\cs -> do (a,cs') <- doParse p1 cs 
                            doParse (fp2 a) cs') 
  -- return :: a -> Parser a
  return x   = P (\cs -> [ (x, cs) ])
   
  -- fail :: String -> Parser a
  fail _     = P (\_ ->  [ ] )
 
instance Functor (Parser a) where
  -- fmap = liftM
  fmap f p = do x <- p
                return (f x)
 
-- | Combine two parsers together in parallel, producing all 
-- possible results from either parser.                 
choose :: Parser a b -> Parser a b -> Parser a b
p1 `choose` p2 = P (\cs -> doParse p1 cs ++ doParse p2 cs)
 
-- | Combine two parsers together in parallel, but only use the 
-- first result. This means that the second parser is used only 
-- if the first parser completely fails. 
(<|>) :: Parser a b -> Parser a b -> Parser a b
p1 <|> p2 = P $ \cs -> case doParse (p1 `choose` p2) cs of
                          []   -> []
                          x:_ -> [x]