// 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. *) // sample tree for --((2+ -3) * 4): let t = Neg(Neg(Mult(Plus(Num(2),Neg(Num(3))),Num(4)))); Console.WriteLine(eval(t)); Console.WriteLine(tostring(t));;