haskell - How do I simplify the below expressions using primitive recursion?

Question

Possible Duplicate:
Symbolic simplification in Haskell (using recursion?)

The simplifications I have in mind are

0*e = e*0 = 0
1*e = e*1 = 0+e = e+0 = e-0 = e

and simplifying constant subexpressions, e.g. Plus (Const 1) (Const 2) would become Const 3. I would not expect variables (or variables and constants) to be concatenated: Var "st" is a distinct variable from Var "s".

For example simplify(Plus (Var "x") (Const 0))= Var "x"

Answer 1

Well, can't you apply pattern matching to the 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.

Answer 2

我对haskell知之甚少，但基本上你会想做一个表达式树遍历。

树是 EXP: (operator) (EXP) (EXP) EXP: (const) EXP: (var)

那么你的简化就变成了伪代码

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
} 

这有点像java esque，但我认为这个想法就在那里，基本上你将不得不进行树遍历。