使用判别联盟实现基本的代数简化F#

Question

我正在使用判别联盟来定义代数表达式,然后实现一个简化函数,该函数使用递归的匹配 - 案例算法执行基本的代数简化.我遇到了涉及嵌套加法/减法/乘法的障碍.

问题是,添加/减去/ etc两个或多个嵌套Expression对象的匹配大小写一直都不会简化为单个常量.IE:

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

返回一个Expression对象,该对象包含Add(Const(3), Const(3))何时返回包含的对象Const(6)

下面的代码将使发生的事情变得非常清楚,为简洁起见,我只包括了Addition的情况,因为Subtraction和Multiplication的结构(和问题)是相同的:

// 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值.如上所述,它最终将返回一个Expression包含-> Add(Const(n2), Const(n2))而不是实际将最后两个值一起添加到其中-> Const(n1+n2)

我可以改变这种结构的方式,以便在所有子表达式包含并且可以简化为值的情况下Add(expr1, expr2)返回单个,即:不包含变量或不可Const简化的Const表达式？

Answer 1

我认为最后一行改为

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

是唯一需要改变的？