(* The SML Blitz Review: see The Little MLer for details *)
(* ***************************************************** *)

(* Simple Functions *)
(* ---------------- *)

fun f(x) = x             (* the identity function *)

fun g(x) = 5*x + 1       (* a simple polynomial *)


(* Binary Functions *)
(* ---------------- *)

fun h(x,y) = 3*x + 4*y   (* a simple binary function *) 
        
fun i(x,y) = (x,y)       (* the identity function on pairs f != i *)
			 (*   ==> pairs are values in their own right *)
			 (*   ==> pattern matching notation! *)

fun b(a) = h(i(a))       (* pairs are values in their own right! : 
			    returned and passed on to next function *)

(* Types *)
(* ----- *)
    
    ;
    f : int -> int
    ; 
    g : int -> int
    ;
    h : (int * int) -> int
    ;
    b : (int * int) -> int
    ;
    i : (int * int) -> (int * int)
    ;
    
type binary_int = (int * int) -> int
    ;	
    h : binary_int
    ;
    b : binary_int
    ;


(* Polymorphism *)
(* ------------ *)
    
    f : bool -> bool                (* f has many types *)
    ;
    f : string -> string            (* ... and another one ... *)
    ;
    f : 'a -> 'a                    (* f is polymorphic : 
				       when it inputs an int, it returns one;
				       when it inputs an bool, it returns one;
				       etc *)
    ;
    i : ('a * 'b) -> ('a * 'b)      (* i is polymorphic, too, but on pairs *)
    ;
    
type 'a unary = 'a -> 'a            (* a polymorphic type definition *) 
    ;
    f : int unary
    ;
    f : 'a unary                   
    ;
   
type ('a,'b) binary = ('a * 'b) -> ('a * 'b)
                                    (* a binary polymorphic type definition *)
    ;
    f : (bool,int) binary           (* f has many many pair types, too *)
    ;
    i : (int,bool) binary           
    ;
    f : ('a,'b) binary
    ;
    i : ('a,'b) binary
    ;

(* ML's types are ranked.
   If t1 can be obtained by replacing type variables in t2 with type expressions, 
   then t2 is more general than t1. 
       Example: 
       t1 = ('a,'b) -> ('a,'b)
       is the result of replacing 'a in 
       t2 = 'a -> 'a 
       with ('a,'b) 
       Ergo: t2 is more general than t1. *)


(* Recursive Types or Datatype *)
(* --------------------------- *) 

datatype int_lst = Empty | Cons of int * int_lst 
                                    (* the usual example, but see below *)

    ;
    Empty : int_lst                 (* Empty __is__ an int_lst *)
    ;
    Cons : int * int_lst -> int_lst (* Cons is __not__ an int_lst *)
    ;
    Cons(1,Empty) : int_lst         (* Now here is a int_lst *)
    ;
    Cons(2,Cons(1,Empty)) : int_lst (* ... and another one *)
    ;

fun add_em_up(Empty) = 0            (* ... and the usual function on lists ... *)
  | add_em_up(Cons(n,l)) = n + add_em_up(l)

    ;
    add_em_up : int_lst -> int
    ;
    
datatype boo_lst = Empty_b | Cons_b of bool * boo_lst
    ;
    Empty_b : boo_lst
    ;
    Cons_b : bool * boo_lst -> boo_lst 
    ;
    Cons_b(true,Empty_b) : boo_lst
    ;
                                    (* okay we get the point: let's abstract *)
datatype 'a lst = Empty | Cons of 'a * 'a lst 
    ;
    Empty : int lst 
    ;
    Empty : bool lst
    ;
    Empty : 'a lst 
    ;
    Cons(1,Empty) : int lst 
    ;
    Cons(true,Empty) : bool lst
    ;

                      (* Cons(true,Cons(1,Empty)) : NO, ML is __NOT__ Scheme *)


datatype 'a tree = Leaf of 'a | Node of ('a tree) lst
                                    (* here is to mututal recursion of data *)
    ;            
    Leaf(5) : int tree
    ;
    Node(Empty) : int tree
    ;
    Node(Cons(Leaf(5),Empty)) : int tree
    ;