-- Lecture week 5B part 2
-- Symbolic expressions
-- dave@chalmers.se 
-- 2017-09-28
import Test.QuickCheck
import Data.Maybe(fromJust)

xx = undefined

------------------------------------------------------

showExpr (Num n) = show n
showExpr (Var s) = s
showExpr (Add e e') = 
  showExpr e ++ " + " ++ showExpr e'
showExpr (Mul e e') = 
  showFactor e ++ " * " ++ showFactor e'
  where 
    showFactor e | isAddition e = "(" ++ showExpr e ++ ")"
                 | otherwise    = showExpr e
                where isAddition (Add _ _) = True
                      isAddition _         = False

instance Show Expr
   where show = showExpr

vars :: Expr -> [VarName]
vars (Num n)     = []
vars (Var x)     = [x]
vars (Add e1 e2) = vars e1 ++ vars e2 -- union Data.List
vars (Mul e1 e2) = vars e1 ++ vars e2


eval :: Table -> Expr -> Integer
eval t (Num n) = n
eval t (Var x) = fromJust (lookup x t)
eval t (Mul e1 e2) = eval t e1 * eval t e2
eval t (Add e1 e2) = eval t e1 + eval t e2

type Table = [(VarName,Integer)]

extable  = [("x",2)]
extable' = [("x",2),("y",3),("z",4)]
 
------------------------------------------------------
-- generators for expressions

rExp :: Int -> Gen Expr
rExp s = frequency [(1,rNum), (1,rVar),(s,rBin s)]

rNum = do
       n <- arbitrary
       return $ Num n
       
rVar = elements $ map Var ["x","y","z"]

rBin s = do
       op <- elements [Add,Mul]
       e1 <- rExp s'
       e2 <- rExp s'
       return $ op e1 e2
           where s' = s `div` 2
         
instance Arbitrary Expr where
  arbitrary = sized rExp

-----------------------------------------------------------------------
data Expr
  = Num Integer
  | Var VarName
  | Add Expr Expr
  | Mul Expr Expr
 deriving Eq

type VarName = String

ex1 = Mul (Add (Var "y") (Num 2)) (Var "x") 
ex2 = Add (Var "x") (Mul (Num 2) (Var "y"))
ex3 = Num (-5) `Add` (Num 2 `Mul` Num 4)

derive :: VarName -> Expr -> Expr
derive x (Num _)             = Num 0
derive x (Var y) | x == y    = Num 1
                 | otherwise = Num 0
derive x (Add e1 e2)         = add (derive x e1) (derive x e2)
derive x (Mul e1 e2)         = add (mul (derive x e1) e2)
                                   (mul (derive x e2) e1)

add (Num 0)  e      = e
add e       (Num 0) = e
add (Num m) (Num n) = Num (n+m)
add e1      e2      = Add e1 e2

mul (Num 0)  e      = Num 0
mul e       (Num 0) = Num 0
mul (Num 1)  e      = e
mul e       (Num 1) = e
mul (Num m) (Num n) = Num (n*m)
mul e1      e2      = Mul e1 e2


-- derive x e 
-- the derivative of e with respect to x (d/dx)