如何使用原始遞歸來簡化以下表達式？

Question

可能重複：
Symbolic simplification in Haskell (using recursion?)

的簡化我的想法是

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

和簡化不斷子表達式，如Plus (Const 1) (Const 2)將變成Const 3。我不希望將變量（或變量和常量）連接在一起：Var "st"是與Var "s"不同的變量。

例如simplify(Plus (Var "x") (Const 0))= Var "x"

Answer 1

嗯，你能不能適用模式匹配的個案？

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 

編輯：是的，當然...遞歸添加。

Answer 2

我不太瞭解haskell，但基本上你會想要做表達式樹遍歷。

樹是 EXP：（操作員）（EXP）（EXP） EXP：（常量） 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，但我認爲這個想法就在那裏，基本上你必須做一個樹遍歷。