Using Discriminating Union to implement basic Algebraic Simplification F#

Question

I'm using a Discriminating Union to define an algebraic expression, and then implementing a simplification function that performs basic Algebraic Simplification with a recursive Match-Case algorithm. I ran into a roadblock involving nested addition/subtraction/multiplication.

The issue is that the match-case for adding/subtracting/etc two or more nested Expression objects wont simplify all the way down to a single constant when it should. IE:

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

Returns an Expression object containing Add(Const(3), Const(3)) when it should return one containing Const(6)

The following code will make what's happening very clear, for brevity I only included the cases for Addition, since the structure (and the problem) is identical for Subtraction and 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

The issue is that with the way it's currently structured, an input that matches // PROBLEM_2 won't fully recursively simplify to a // PROBLEM_1 case, even if expr1 and expr2 contain only Const values. As mentioned above, it eventually will return an Expression containing -> Add(Const(n2), Const(n2)) instead of actually adding those final two values together as in -> Const(n1+n2)

What can I change about the way this is structured so that Add(expr1, expr2) will return a single Const in the event that that all sub expressions contain and are reducible to Const values, ie: that contain no variables or irreducible expressions?

Answer 1

I think the last line changed to

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

is the only change needed?