I use discriminatory union to define an algebraic expression, and then implement a simplification function that performs basic algebraic simplification using the Match-Case recursive algorithm. I came across a trial block involving nested addition / subtraction / multiplication.
The problem is that the case of matching for adding / subtracting / etc of two or more nested Expression objects will not simplify all the way to one constant when necessary. 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 an object containing Const(6)
The following code will do what happens very clearly, for brevity, I have included only cases to add, since the structure (and 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 problem is that with the way it is currently structured, an input that matches // PROBLEM_2 will not be fully recursively simplified to the case // PROBLEM_1 , even if expr1 and expr2 contain only Const values. As mentioned above, it will eventually return an Expression containing -> Add(Const(n2), Const(n2)) , instead of actually adding these last two values together, as in -> Const(n1+n2)
What can I change about how this is structured, so Add(expr1, expr2) will return one Const if all auxiliary expressions contain and are reduced to Const values, that is: that do not contain variables or irreducible expressions?