//    F# algebraic expression trees

open System;

type expr = Num of int | Plus of expr*expr | Mult of expr*expr | Neg of expr;;

// recursive function to evaluate expression, note "match"
let rec eval e= 
  match e with
    | Num(x) -> x
    | Plus(x,y) -> eval(x) + eval(y)
    | Mult(x,y) -> eval(x) * eval(y);
    | Neg(x) -> -1 * eval(x);

// print form in prefix notation:
let rec tostring = function  //equivalent to: rec tostring s = match s with ...
  | Num(x) -> string(x)
  | Plus(x,y) -> "(+ " + tostring(x) + " " + tostring(y) + ")"
  | Mult(x,y) -> "(* " + tostring(x) + " " + tostring(y) + ")";
  | Neg(Neg(x)) -> tostring(x)  // two negatives cancel out
  | Neg(x) -> "-" + tostring(x);

(* How does this compare to dynamic dispatch?  Each line in the eval and
   tostring functions corresponds roughly to a "visit" method in the visitor 
   pattern.  But more than that is happening.  If we defined Num, Plus,
   Mult and Neg as subclasses of an expr interface, then dynamic dispatch
   will allow us to automatically choose one of 4 cases.  But how could
   dynamic dispatch distinguish between the Neg(Neg(x)) case from the
   Neg(x) case?  The pattern matching mechanism of F#/ML is more powerful
   than dynamic dispatch.  In order to implement it, much more than a
   simple "tag" is needed in each object.  The entire STRUCTURE of the
   data object must be exposed.

   More importantly, however, no type casting is needed, and the code is
   STATICALLY TYPE SAFE.
*)

// more interesting version of tostring, convert to infix, with parentheses
// only where necessary.  Three levels of precedence: unary -, * and +. 2 1 0
// When calling to_infix, pass in level of outer expression, initially 0

let to_infix_str exp = 
  let rec to_infix exp level = 
   match exp with 
    | Num(x) -> string(x)
    | Neg(Neg(x)) -> to_infix x level
    | Neg(x) -> "-" + (to_infix x 2)
    | Mult(x,y) -> 
        let (a,b) = ((to_infix x 1), (to_infix y 1))
        if level>1 then sprintf "(%s*%s)" a b
        else sprintf "%s*%s" a b
    | Plus(x,Neg(y)) -> 
        let (a,b) = ((to_infix x 0),(to_infix y 2))
        if level>0 then sprintf "(%s-%s)" a b
        else sprintf "%s-%s" a b
    | Plus(x,y) -> 
        let (a,b) = ((to_infix x 0),(to_infix y 0))
        if level>0 then sprintf "(%s+%s)" a b
        else sprintf "%s+%s" a b
  to_infix exp 0;;

// sample tree
let t = Neg(Neg(Mult(Plus(Num(2),Neg(Num(3))),Plus(Num(4),Num(5)))));
let t2 = Neg(Plus(Mult(Num(2),Num(3)), Num(4)));
Console.WriteLine(eval(t));
Console.WriteLine(tostring(t));;
printfn "%s" (to_infix_str t);;
printfn "%s" (to_infix_str t2);;