F# Simple Tree evaluation
For a simple domain like that, wouldn't it be simpler to define the data like this?

type Expression =
| IntExpr of int
| AddExpr of Expression * Expression
| SubtractExpr of Expression * Expression
| NegationExpr of Expression


This would mean that you can implement the eval function like this:

let rec eval = function
| IntExpr i -&gt; i
| AddExpr (x, y) -&gt; eval x + eval y
| SubtractExpr (x, y) -&gt; eval x - eval y
| NegationExpr x -&gt; -(eval x)


Here are some FSI examples:

&gt; let x1 = IntExpr 42 |&gt; eval;;    
val x1 : int = 42

&gt; let x2 = AddExpr (IntExpr 1, IntExpr 32) |&gt; eval;;    
val x2 : int = 33

&gt; let x3 = NegationExpr (SubtractExpr (NegationExpr (IntExpr 3), (AddExpr (IntExpr 4, IntExpr 7)))) |&gt; eval;;    
val x3 : int = 14