title: Math Expression Simplification f#
body: <p>I'm working on a mathematical expression simplifier (rather basic, no exponents, logs, roots, fractions etc) and I have it mostly working. Of the 19 tests I've used 14 of them pass. For the 5 remaining, I have written multiple other statements in my simplify function but it doesn't seem to change a thing. </p>
  
  <p>Below is code (copy and paste into an interpreter and it works just fine)</p>
  
  <pre><code>    //expression types 
  type Expression =
      | X
      | Y
      | Const of float
      | Neg of Expression
      | Add of Expression * Expression
      | Sub of Expression * Expression
      | Mul of Expression * Expression
  
  // formats string 
  let exprToString expr =
      let rec recExprStr parens expr =
          let lParen = if parens then "(" else ""
          let rParen = if parens then ")" else ""
          match expr with
          | X -&gt; "x"
          | Y -&gt; "y"
          | Const n -&gt; n.ToString()
          | Neg e -&gt; lParen + "-" + recExprStr true e + rParen
          | Add (e1, e2) -&gt; lParen + recExprStr true e1 + "+" + recExprStr true e2 + rParen
          | Sub (e1, e2) -&gt; lParen + recExprStr true e1 + "-" + recExprStr true e2 + rParen
          | Mul (e1, e2) -&gt; lParen + recExprStr true e1 + "*" + recExprStr true e2 + rParen
      recExprStr false expr
  
  //simplification function 
  let rec simplify expr =
      match expr with
      //addition 
      | Add(Const(ex1), Const(ex2)) -&gt; Const(ex1 + ex2)
      | Add(ex1, Const(0.)) -&gt; ex1 |&gt; simplify
      | Add(Const(0.), ex1) -&gt; ex1 |&gt; simplify
      | Add(Const(num), ex1) -&gt; Add(ex1, Const(num)) |&gt; simplify
      | Add(ex1, Neg(ex2)) -&gt; Sub(ex1, ex2) |&gt; simplify
      | Add(Neg(ex1), ex2) -&gt; Sub(ex2, ex1) |&gt; simplify
      //subtraction 
      | Sub(Const(num1), Const(num2)) -&gt; Const(num1 - num2)
      | Sub(ex1, Const(0.)) -&gt; ex1 |&gt; simplify
      | Sub(Const(0.), ex1) -&gt; Neg(ex1) |&gt; simplify
      //multiplication 
      | Mul(Const(num1), Const(num2)) -&gt; Const(num1 * num2)
      | Mul(ex1, Const(1.)) -&gt; ex1 |&gt; simplify
      | Mul(Const(1.), ex1) -&gt; ex1 |&gt; simplify
      | Mul(ex1, Const(0.)) -&gt; Const(0.)
      | Mul(Const(0.), ex1) -&gt; Const(0.)
      | Mul(ex1, Const(num1)) -&gt; Mul(Const(num1), ex1) |&gt; simplify
      | Mul(Neg(ex1), ex2) -&gt; Neg(Mul(ex1, ex2)) |&gt; simplify
      | Mul(ex1, Neg(ex2)) -&gt; Neg(Mul(ex1, ex2)) |&gt; simplify
      //negation involving a number
      | Neg(Const(0.)) -&gt; Const(0.)
      | Neg(Neg(ex1)) -&gt; ex1 |&gt; simplify
      | _ -&gt; expr
  
  //Tests
  printfn "---Provided Tests---"
  let t1 = Add (Const 5.0, Const 3.0)
  let t2 = Sub (Const 5.0, Const 3.0)
  let t3 = Mul (Const 5.0, Const 3.0)
  let t4 = Neg (Const 4.0)
  let t5 = Neg (Const -9.0)
  let t6 = Add (X, Const 0.0)
  let t7 = Add (Const 0.0, Y)
  let t8 = Sub (X, Const 0.0)
  let t9 = Sub (Const 0.0, Y)
  let t10 = Sub (Y, Y)
  let t11 = Mul (X, Const 0.0)
  let t12 = Mul (Const 0.0, Y)
  let t13 = Mul (X, Const 1.0)
  let t14 = Mul (Const 1.0, Y)
  let t15 = Neg (Neg X)
  let t16 = Sub (Mul (Const 1.0, X), Add (X, Const 0.0))
  let t17 = Add (Mul (Const 4.0, Const 3.0), Sub (Const 11.0, Const 5.0))
  let t18 = Sub (Sub (Add (X, Const 1.0), Add (X, Const 1.0)), Add (Y, X))
  let t19 = Sub (Const 0.0, Neg (Mul (Const 1.0, X)))
  
  //Output goes here! 
  //5 + 3 = 0
  printfn "t1  Correct: 8\t\tActual: %s" (exprToString (simplify t1))
  //5-3 = 2
  printfn "t2  Correct: 2\t\tActual: %s" (exprToString (simplify t2))
  //5 * 3 = 15
  printfn "t3  Correct: 15\t\tActual: %s" (exprToString (simplify t3))
  //-(4) = -4
  printfn "t4  Correct: -4\t\tActual: %s" (exprToString (simplify t4))
  //-(-9) = 9
  printfn "t5  Correct: 9\t\tActual: %s" (exprToString (simplify t5))
  //x + 0 = x
  printfn "t6  Correct: x\t\tActual: %s" (exprToString (simplify t6))
  //0 + y = y
  printfn "t7  Correct: y\t\tActual: %s" (exprToString (simplify t7))
  //x - 0 = x
  printfn "t8  Correct: x\t\tActual: %s" (exprToString (simplify t8))
  //0 - y = -y
  printfn "t9  Correct: -y\t\tActual: %s" (exprToString (simplify t9))
  //y - y = 0
  printfn "t10  Correct: 0\t\tActual: %s" (exprToString (simplify t10))
  //x * 0 = 0
  printfn "t11  Correct: 0\t\tActual: %s" (exprToString (simplify t11))
  //0 * y = 0
  printfn "t12  Correct: 0\t\tActual: %s" (exprToString (simplify t12))
  //x * 1 = x
  printfn "t13  Correct: x\t\tActual: %s" (exprToString (simplify t13))
  //1 * y = y
  printfn "t14  Correct: y\t\tActual: %s" (exprToString (simplify t14))
  //-(-x) = x
  printfn "t15  Correct: x\t\tActual: %s" (exprToString (simplify t15))
  // (1 * x) - (x + 0) = 0
  printfn "t16  Correct: 0\t\tActual: %s" (exprToString (simplify t16))
  //(4 * 3) + (11 - 5) = 18
  printfn "t17  Correct: 18\t\tActual: %s" (exprToString (simplify t17))
  // ((x + 1) - (x + 1)) - (y+x) = -y -x
  printfn "t18  Correct: -y -x\t\tActual: %s" (exprToString (simplify t18))
  // 0 - (-(1 * x)) = x
  printfn "t19  Correct: x\t\tActual: %s" (exprToString (simplify t19))
  // (x + 1) *  (-2y + x) 
  </code></pre>
  
  <p>The output of the program is as follows, I have marked the 6 tests that fail (correct is the proper answer, actual is what i'm returning) </p>
  
  <pre><code>t1  Correct: 8          Actual: 8
  t2  Correct: 2          Actual: 2
  t3  Correct: 15         Actual: 15
  t4  Correct: -4         Actual: -4
  t5  Correct: 9          Actual: --9 //FAILS 
  t6  Correct: x          Actual: x
  t7  Correct: y          Actual: y
  t8  Correct: x          Actual: x
  t9  Correct: -y         Actual: -y
  t10  Correct: 0         Actual: y-y //FAILS
  t11  Correct: 0         Actual: 0
  t12  Correct: 0         Actual: 0
  t13  Correct: x         Actual: x
  t14  Correct: y         Actual: y
  t15  Correct: x         Actual: x
  t16  Correct: 0         Actual: (1*x)-(x+0)          //FAILS
  t17  Correct: 18                Actual: (4*3)+(11-5) //FAILS
  t18  Correct: -(y + x)             Actual: ((x+1)-(x+1))-(y+x) //FAILS 
  t19  Correct: x         Actual: x
  </code></pre>
  
  <p>I'm a bit perplexed as to how I might solve the final 4 (16,17,18) but It seems to me like what I have for #5 and #10 should work. </p>
  
  <p>For test 5, I included <code>| Neg(Neg(ex1)) -&gt; ex1 |&gt; simplify</code> which I thought would catch my double negative but doesn't.</p>
  
  <p>For test 10, I figured something like <code>| Sub(ex1, ex2) -&gt; (ex1 - ex2)</code> would work, but it turns out that's not even valid syntax.</p>
  
  <p>I've looked through a half dozen or so resources on simplification, and even copying and pasting some of their work my tests still fail. It know I must just be missing a case or two, but I'm pulling my hair trying to figure what I might have left out! I greatly appreciate any input!     </p>
  
  <p>(Original post had a test 20, I have since removed it for answer simplification purposes. Given my current code, I realized I couldn't possibly simplify it)</p>