(* Expression Trees: Typed, Functional Programming Style *)

open System

type Expr =
  | Val of int
  | Plus of Expr*Expr
  | Times of Expr*Expr
  | Neg of Expr           // unary -

let rec eval expr =
  match expr with
    | Val(x) -> x
    | Plus(a,b) -> (eval a) + (eval b)
    | Times(a,b) -> (eval a) * (eval b)
    | Neg(a) -> -1 * (eval a)

let rec tostring expr =
  match expr with
    | Val(x) -> string(x)
    | Times(a,b) -> sprintf "(%s * %s)" (tostring a) (tostring b)
    | Plus(a,Neg(b)) -> sprintf "(%s - %s)" (tostring a) (tostring b)    
    | Plus(a,b) -> sprintf "(%s + %s)" (tostring a) (tostring b)
    | Neg(Neg(a)) -> tostring a
    | Neg(a) -> sprintf "-%s" (tostring a)

let e1 = Plus(Times(Val(2),Val(3)), Plus(Val(1),Val(4)))

printfn "%s evals to %d" (tostring e1) (eval e1)

(* The functional programming version fixes the type Expr.  We cannot
   arbitrarily extend Expr with a new kind of expression.  This appears
   restrictive but it allows for static typing.  Types are no longer 
   required at runtime.  This style of programming contrasts with with
   OOP approach in that it becomes easier to add new kinds of operations
   in addition to eval and tostring.  However, with the OOP version it is
   easier to add new kinds of expressions.
*)