How can I simplify the below expressions using primitive recursion?
Possible duplicate:
Symbolic simplification in Haskell (using recursion?)
I have simplifications:
0*e = e*0 = 0
1*e = e*1 = 0+e = e+0 = e-0 = e
and simplification of constant subexpressions eg. Plus (Const 1) (Const 2)
will become Const 3
. I would not expect variables (or variables and constants) to be combined: Var "st"
is a great variable from Var "s"
.
for example simplify(Plus (Var "x") (Const 0))= Var "x"
source to share
Well, can't you apply pattern matching for individual cases?
simplify (Plus (Const 0) (Expr x)) = simplify (Expr x)
simplify (Plus (Expr x) (Const 0)) = simplify (Expr x)
simplify (Mult (Const 0) _) = Const 0
simplify (Mult _ (Const 0)) = Const 0
โ โฆ and so on
EDIT: Yes, of course ... recursion added.
source to share
I don't know much about haskell, but essentially you want to do an expression tree traversal.
EXP tree: (statement) (EXP) (EXP) EXP: (const) EXP: (var)
then your simplification becomes heres psuedo code
simplify(Exp e)
if (e is const) return e
else if (e is var) return e
else
{//encode simplification rules
Exp left = simplify(e.left)
Exp right = simplify(e.right)
if(operator is PLUS)
{
if(left == 0) return right;
if(right == 0) return left;
}
else if(operator is MULT)
{
if(left == 1) return right;
if(right == 1) return left;
if(left == 0) return 0;
if(right == 0) return 0;
}
//and so on for other operators
}
It's kind of java esque, but I think the idea is there, in fact you will have to do tree traversal.
source to share