F# Simple Tree evaluation

Question

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

Answer 1

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

• prydain: 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#?
• Mark Seemann: 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.
• prydain: 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.
• Mark Seemann: @prydain Well, yes... It depends... :$