HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

F# Simple Tree evaluation

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
simpleevaluationtree

Problem

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

Solution

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

Code Snippets

type Expression =
| IntExpr of int
| AddExpr of Expression * Expression
| SubtractExpr of Expression * Expression
| NegationExpr of Expression
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)
> 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

Context

StackExchange Code Review Q#139356, answer score: 4

Revisions (0)

No revisions yet.