import Test.QuickCheck
import Data.List
import Data.Maybe



-- Data type for arithmetic expressions
data Expr
    = Num Integer
    | Add Expr Expr
    | Mul Expr Expr
    | Var Name
  deriving (Eq)

type Name = String

-- x+1
ex1 = Add (Var "x") (Num 1)



eval :: [(Name,Integer)] -> Expr -> Integer
eval env (Num n)   = n
eval env (Add a b) = eval env a + eval env b
eval env (Mul a b) = eval env a * eval env b
eval env (Var v)   = fromJust (lookup v env)



-- `showExpr e` shows the expression `e` as a string
showExpr :: Expr -> String
showExpr (Num n)   = show n
showExpr (Add a b) = showExpr a ++ "+" ++ showExpr b
showExpr (Mul a b) = showFactor a ++ "*" ++ showFactor b
showExpr (Var v)   = v

showFactor :: Expr -> String
showFactor e@(Add _ _) = "(" ++ showExpr e ++ ")"
showFactor e           = showExpr e

instance Show Expr
  where
    show = showExpr



genExpr :: Int -> Gen Expr
genExpr s = frequency
    [ (1,  do n <- arbitrary
              return (Num n)
      )
    , (1,  do v <- elements ["x","y","z"]
              return (Var v)
      )
    , (s,  do a <- genExpr (s `div` 2)
              b <- genExpr (s `div` 2)
              return (Add a b)
      )
    , (s,  do a <- genExpr (s `div` 2)
              b <- genExpr (s `div` 2)
              return (Mul a b)
      )
    ]

instance Arbitrary Expr
  where
    arbitrary = sized genExpr

-- `vars e` lists the distinct variables used in the expression `e`
vars :: Expr -> [Name]
vars (Num _)   = []
vars (Var v)   = [v]
vars (Add a b) = vars a `union` vars b
vars (Mul a b) = vars a `union` vars b
  -- union



-- `diff e x` differentiates expression `e` with respect to variable `x`
diff :: Expr -> Name -> Expr
diff (Num _) v             = Num 0
diff (Var w) v | w==v      = Num 1
               | otherwise = Num 0

diff (Add a b) x = Add (diff a x) (diff b x)
diff (Mul a b) x =
    Add (Mul a (diff b x)) (Mul b (diff a x))



  -- diff (Mul (Num 2) (Var "x")) "x"
  -- smart constructors
    -- Add (Num 2) (Num 5)
    -- add (Num 2) (Num 5)



-- `simplify e` simplifies `e` without changing its value
simplify :: Expr -> Expr
simplify = undefined
  -- Handle closed expressions; other cases in exercise



-- prop_simplifyCorrect
  -- Generate environment



-- prop_simplifyNoJunk
  -- To be extended in exercise