import Data.Char import Data.Maybe ------------------------------------------------------------------------- {- This file demonstrates how to improve the definition of parsers by using functions from the Monad class. This, in turn, allows us to use do-notation for parsers. Many parsing libraries for Haskell are based on monads. -} ------------------------------------------------------------------------- -- the expression datatype data Expr = Num Int | Add Expr Expr | Mul Expr Expr deriving ( Eq, Show ) ------------------------------------------------------------------------- -- parsing numbers type Parser a = String -> Maybe (a,String) number :: Parser Int number (c:s) | isDigit c = Just (digits 0 (c:s)) number ('-':s) = fmap negate' (number s) number _ = Nothing negate' :: (Int,String) -> (Int,String) negate' (n,s) = (-n,s) digits :: Int -> String -> (Int,String) digits n (c:s) | isDigit c = digits (10*n + digitToInt c) s digits n s = (n,s) -- This one is ugly, because it has to handle failure and pass around the string num :: Parser Expr num s = case number s of Just (n,s') -> Just (Num n, s') Nothing -> Nothing ------------------------------------------------------------------------- -- combining Maybes (>>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b Nothing >>>= _ = Nothing Just a >>>= k = k a -- Slight improvement (no need to handle failure) num2 :: Parser Expr num2 s = number s >>>= \(n,s') -> Just (Num n, s') {- -- `Maybe` is a monad instance Monad Maybe where return = Just (>>=) = (>>>=) -} -- Then we can just write `(>>=)` instead of `(>>>=)`, and `return` instead of `Just`: num3 :: Parser Expr num3 s = number s >>= \(n,s') -> return (Num n, s') -- Since Maybe is a monad, we are allowed to use do notation. The compiler will -- automatically translate `num4` to `num3`. num4 :: Parser Expr num4 s = do (n,s') <- number s return (Num n, s') ------------------------------------------------------------------------- -- combining Parsers -- This combinator for parsers handles failure and hides the threading of the string: (>>>>=) :: Parser a -> (a -> Parser b) -> Parser b p >>>>= k = \s -> case p s of Nothing -> Nothing Just (a,s') -> k a s' -- alternative: p >>>>= k = \s -> p s >>>= \(a,s') -> k a s' retParser :: a -> Parser a retParser a = \s -> Just (a,s) num5 :: Parser Expr num5 = number >>>>= \n -> retParser (Num n) -- `Parser` can not be an instance of `Monad`, so we define a new type: data P a = P (Parser a) -- The same as `(>>>>=)` but with wrapping of the `P` constructor (>>>>>=) :: P a -> (a -> P b) -> P b P p >>>>>= k = P (p >>>>= \a -> let P p2 = k a in p2) retP :: a -> P a retP = P . retParser -- `P` is a monad: instance Monad P where (>>=) = (>>>>>=) return = retP -- Then we can just write `(>>=)` instead of `(>>>>>=)`, and `return` instead of `retP`: num6 :: P Expr num6 = P number >>= \n -> return (Num n) -- Finally, we can use do-notation. The compiler will automatically translate -- `num7` to `num6`. num7 :: P Expr num7 = do n <- P number return (Num n) ------------------------------------------------------------------------- test = fromJust (num7' "345+567") where P num7' = num7