Как упростить приведенные ниже выражения с использованием примитивной рекурсии?

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 

EDIT: Да, конечно ... рекурсия добавлена.

Answer 2

Я мало знаю о haskell, но по существу вы захотите сделать обход дерева выражений.

дерево EXP: (оператор) (EXP) (EXP) EXP: (Const) EXP: (вар)

тогда ваш Simplify становится Heres код псевдо

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, но я думаю, что идея там, по сути, вам придется делать обход дерева.