使用 Discriminating Union 实现基本的代数化简 F#

Question

我正在使用判别联合定义代数表达式，然后实现一个简化函数，该函数使用递归 Match-Case 算法执行基本代数简化。我运行进入一个涉及嵌套 addition/subtraction/multiplication.

的障碍

问题是 adding/subtracting/etc 两个或多个嵌套 Expression 对象的匹配案例不会在应该时一直简化为单个常量。即：

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

Returns 一个 Expression 对象包含 Add(Const(3), Const(3)) 而它应该 return 一个包含 Const(6)

下面的代码将使正在发生的事情变得非常清楚，为简洁起见，我只包含了加法的情况，因为减法和乘法的结构（和问题）是相同的：

// 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 的输入不会完全递归地简化为 // PROBLEM_1 情况，即使 expr1 和 expr2 仅包含 Const 个值。如上所述，它最终将 return 包含 -> Add(Const(n2), Const(n2)) 的 Expression 而不是像 -> Const(n1+n2)

那样实际将这两个最终值相加

如果所有子表达式都包含并可简化为 Const 个值，即：不包含变量或不可约表达式？

Answer 1

我认为最后一行改为

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

是唯一需要更改的地方吗？

使用 Discriminating Union 实现基本的代数化简 F#

Using Discriminating Union to implement basic Algebraic Simplification F#

f#

pattern-matching

discriminated-union