# F# Simple Tree evaluation

I'm currently trying to learn the idiomatic way to write F# code. The code simulates a basic calculator with only binary plus, minus and unary minus.

I'd like to know if there is a better way to group union cases than the way I did it. Should the Add/Sub/MinusExpression be cases in the Expression union? Is there a better way to write the eval function?

type Expression =
| BinExpression of BinExpression
| UnExpression  of UnExpression
| IntExpression of int

and BinExpression =
| AddExpression of Expression * Expression
| SubExpression of Expression * Expression

and UnExpression =
| MinusExpression of Expression

let rec eval tree =
let evalBin tree =
match tree with
| AddExpression(e1, e2) -> (eval e1) + (eval e2)
| SubExpression(e1, e2) -> (eval e1) - (eval e2)

let evalUn tree =
match tree with
| MinusExpression(v) -> -(eval v)

match tree with
| BinExpression(e) -> evalBin e
| UnExpression(e)  -> evalUn e
| IntExpression(v) -> v


## 1 Answer

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 -> i
| AddExpr (x, y) -> eval x + eval y
| SubtractExpr (x, y) -> eval x - eval y
| NegationExpr x -> -(eval x)


Here are some FSI examples:

> let x1 = IntExpr 42 |> eval;;
val x1 : int = 42

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

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

• Is that still viable if I get more cases like Mul/Div/Mod/And/Or/etc? And coming from C# the urge to group these in more specific unions is still there, I'm mostly wondering if this is just me trying to apply C# to F# or if this is the "right" way to do it in F#? Aug 22 '16 at 17:07
• That 'etc' hides the answer to that question. How much more do you need to add? What does the complex structure afford? In general, I often find the Zen of Python helpful - in this case, Flat is better than nested. My inclination would be to keep it flat until I can clearly see the benefit of introducing a more nested model. Aug 22 '16 at 17:39
• I was thinking about the scale of a parse tree for a programming language but the only thing a more complex structure would gain in that case is the ability to fine grain the match statements on the other hand that would make it more readable. What I take away from this is a if you can give an good argument for it may be a good idea. Aug 22 '16 at 19:50
• @prydain Well, yes... It depends... :\$ Aug 22 '16 at 20:04