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'

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