(* ML or "meta language" is a research-oriented language with which many
   advanced programming language features, such as garbage collection,
   algebric types, and (especially) polymorphic typing, were first conceived
   and developed.  Many of these features are finally finding their way
   into more popular languages such as C# and Java.  But there is also much
   more in store.  Microsoft Research is working on a .NET-compatible version
   of ML called F#.
*)

(* Algebric linked lists.
   Furthermore, these lists are polymorphic: 'a is a type variable
 *)

datatype 'a mylist = nil | cons of ('a*'a mylist);

(* ML is capable of inferring that the type of the following length function
   is polymorphic.
*)

fun length(nil) = 0
  | length(cons(head,tail)) = 1+length(tail);

(* ML prints val length = fn : 'a mylist -> int)    *)


(* datatype for expression trees *)

datatype expr = leaf of int | timesnode of (expr*expr) | plusnode of (expr*expr);

fun eval(leaf(x)) = x
  | eval(timesnode(l,r)) = eval(l) * eval(r)
  | eval(plusnode(l,r)) = eval(l) + eval(r);

(*
    ML is a purely algebraic language.  What does this mean? Well, for
    one thing, it is not possible to have a malformed expr.  One cannot
    create a leaf node that points back to the root, for example.
*)


(*
   We write a ML equivalent of the fooditem program.  The visitor
   pattern was actually created to allow this form of "algebraic" programming.

   All food items have a calories property.  vegetables also have a 
   color property, and meat has a type property (0=white, 1=red)

   Each food item also has a component that links it with more food items,
   terminating in a 'nofood' item.
*)

datatype food = 
   fruit of (int*food) | veg of (int*string*food) | 
   meat of (int*int*food) | nofood;

(* sample linked lists *)
val myfood = fruit(50,meat(100,1,veg(80,"green",nofood)));
val myfood2 = fruit(50,veg(150,"green",veg(170,"white",meat(280,1,nofood))));

(* function to add up calories *)

fun cals(fruit(x,next)) = x + cals(next)
  | cals(veg(x,color,next)) = x + cals(next)
  | cals(meat(x,t,next)) = x + cals(next)
  | cals(nofood) = 0;

(* function find fooditem with highest calories, tail-recursive, ax0=0 *)

fun max(ax,fruit(x,next)) = if x>ax then max(x,next) else max(ax,next)
  | max(ax,veg(x,c,next)) = if x>ax then max(x,next) else max(ax,next)
  | max(ax,meat(x,t,next)) = if x>ax then max(x,next) else max(ax,next)
  | max(ax,_) = ax;    (* underscore means don't care *)


(* function to check if list is ordered, with all fruits before vegs and
   all vegs before meats, tail recursive with a state parameter. 
   The initial value passed to state should be "fruit"
*)

fun ordered(state,nofood) = true
  
  | ordered(state,fruit(x,next)) =
       not(state="veg" orelse state="meat") andalso ordered("fruit",next)

  | ordered(state,veg(x,c,next)) = 
       not(state="meat") andalso ordered("veg",next)

  | ordered(state,meat(x,t,next)) = ordered("meat",next);


(* An improvement on the Visitor Pattern:  The visitor pattern recovers some
   of the capability of algebraic types for java-like programming languages.
   However, object-oriented programming only dispatches on ONE object.  The
   one behind the dot.  Consider writing a function that takes TWO food items
   as parameters, and returns true iff both are of the same type (both fruits,
   both vegetables or both meats).  One would have to use "is" (or 
   "instanceof") tests and several if-else statements in C#/Java.  One cannot
   use the visitor pattern, because we can only dispatch on ONE of the two
   food objects.  Extending the dynamic dispatch paradigm to multiple objects
   also would not work.  If there are 4 different subclasses and we wish to
   write a function with three object parameters, we would need to write
   4*4*4 = 64 different versions of the function!  But with ML-style algebraic
   types and pattern-matching, we can write it as follows:
*)

fun sametype(fruit(_,_), fruit(_,_)) = true
  | sametype(veg(_,_,_), veg(_,_,_)) = true
  | sametype(meat(_,_,_), meat(_,_,_)) = true
  | sametype(_,_) = false;


(* The default pattern matches all other cases, so there is no need to
   write 9 separate cases. *)