差別化連合を使って基本的な代数的簡素化を実装するF＃

Question

私は、差別化連合を使って代数式を定義し、再帰的マッチケースアルゴリズムで基本的代数単純化を実行する単純化関数を実装しています。私はネストされた加算/減算/乗算を含むロードブロッキングに遭遇しました。

2つ以上のネストされた/ etc/etcをネストするマッチケースは、必要なときに単一の定数に完全に簡素化されないという問題があります。 IE：それは次のコードがあるため、簡潔にするために、私は唯一の追加のためのケースを含め、非常に明確に何が起こっているかでしょうConst(6)

を含むものを返すべきとき

simplify Add(Add(Const(1), Const(2)), Add(Const(1), Const(2)))

がAdd(Const(3), Const(3))を含むExpressionオブジェクトを返します。構造（と問題）は、減算と乗算では同じです。

// Expression type 
type Expression = 
    | X 
    | Y 
    | Const of float 
    | Neg of Expression 
    | Add of Expression * Expression 
    | Sub of Expression * Expression 
    | Mul of Expression * Expression 

let rec simplify expr = 
    match expr with 
    | X -> expr 
    | Y -> expr 
    | Const(n) -> Const(n) 
    | Add(X, Const(0.0)) -> X 
    | Add(Const(0.0), X) -> X 
    | Add(Const(0.0), Y) -> Y 
    | Add(Y, Const(0.0)) -> Y 
    | Add(Const(n1), Const(n2)) -> Const(n1+n2)     // PROBLEM_1 
    | Add(expr1, expr2) -> Add(simplify(expr1), simplify(expr2)) // PROBLEM_2 

問題はその通りです現在構成されている// PROBLEM_2に一致する入力は、expr1とexpr2にはConstの値しか含まれていなくても、// PROBLEM_1の場合に完全に再帰的に単純化されません。前述したように、それは最終的にExpressionが-> Add(Const(n2), Const(n2))を含む代わりに、実際に私はAdd(expr1, expr2)がイベントで単一Constを返すように、これは構造化されている方法については変更することができますどのような-> Const(n1+n2)

のように一緒にこれらの最後の2つの値を加算し返すようすべての下位式にはConstの値が含まれています。つまり、変数または既約式が含まれていませんか？

Answer 1

私は必要なだけの変更である最後の行が

| Add(expr1, expr2) -> simplify(Add(simplify(expr1), simplify(expr2))) 
//      ^^^^^^^^^         ^

に変更と思いますか？