import Control.SetFunctions

-- Simplification of arithmetic expressions

-- Representing arithmetic expressions:
data Exp = Lit Int
         | Var String
         | Add Exp Exp
         | Mul Exp Exp
 deriving (Eq,Show)

-- 1*x+0
exp1 = Add (Mul (Lit 1) (Var "x")) (Lit 0)

type Pos = [Int]

-- replace e p s === e[s]_p
replace :: Exp -> Pos -> Exp -> Exp
replace _         []    s = s
replace (Add l r) (1:p) s = Add (replace l p s) r
replace (Add l r) (2:p) s = Add l (replace r p s)
replace (Mul l r) (1:p) s = Mul (replace l p s) r
replace (Mul l r) (2:p) s = Mul l (replace r p s)

-- inverse of the simplification rules:
evalTo :: Exp -> Exp
evalTo e = Add (Lit 0) e
         ? Add e (Lit 0)
         ? Mul (Lit 1) e
         ? Mul e (Lit 1)

simplify :: Exp -> Exp
simplify (replace c p (evalTo x)) = replace c p x
--simplify (replace c p (Add (Lit 0) x)) = replace c p x
--simplify (replace c p (Add x (Lit 0))) = replace c p x
--simplify (replace c p (Mul (Lit 1) x)) = replace c p x

-- Find some variable occurring in an expression:
varInExp :: Exp -> String
varInExp (replace _ _ (Var v)) = v

-- Find all variables occurring in an expression:
varsInExp :: Exp -> [String]
varsInExp e = sortValues ((set1 varInExp) e)