(* MODIFIED FROM BEN GOLDBERG'S LECTURE NOTES *)
(* USERDEFINED TYPES *)
type mytype = bool list ; (* makes "mytype" a synonym for "bool list" *)
type mytype = bool list
fun one (x:mytype) = hd x;
val one = fn : mytype > bool
(* To define a brand new type, we use the "datatype" construct *)
datatype stoplight = red  green  yellow ;
datatype stoplight = green  red  yellow
(* The order doesn't matter, so the interpreter alphabetizes.)
val x = red;
val x = red : stoplight
(* These literals, "green", "read", and "yellow" can be used as patterns *)
fun drive red = "stop"
 drive green = "go"
 drive yellow = "go faster" ;
val drive = fn : stoplight > string
drive yellow;
val it = "go faster" : string
(* Recursive datatypes *)
datatype tree = leaf of int  node of tree * tree ;
val t = node(node(leaf 2, leaf 3), leaf 5);
val t = node (node (leaf #,leaf #),leaf 5) : tree
(* t is the tree node > node > leaf 2
 
 > leaf 3

> leaf 5
*)
(* The # mark is just an indicator that the structure continues past the
maximum default depth for the printer *)
(* Note: "leaf" and "node" are both little functions.
leaf N is a function of type fn : int > tree that returns
the structure (leaf N)
node (E1,E2) is a function of type expr * expr > expr that returns
the structure (node E1 E2).
*)
(* Here's a function that returns the "frontier" of a tree, namely
the list of integers at the leaves of a tree *)
fun frontier (leaf x) = [x]
 frontier (node (l,r)) = frontier l @ frontier r ;
val frontier = fn : tree > int list
frontier t;
val it = [2,3,5] : int list
(* Can also define polymorphic datatypes *)
datatype 'a tree = leaf of 'a  node of 'a tree * 'a tree ;
datatype 'a tree = leaf of 'a  node of 'a tree * 'a tree
leaf 3;
val it = leaf 3 : int tree
leaf true;
val it = leaf true : bool tree
node(leaf "hello", leaf "goodbye") ;
val it = node (leaf "hello",leaf "goodbye") : string tree
(* The following is illegal, since in a given data structure
all instances of 'a must be the same type *)
node(leaf 2, leaf false);
stdIn:7.389.26 Error: operator and operand don't agree [literal]
operator domain: int tree * int tree
operand: int tree * bool tree
in expression:
node (leaf 2,leaf false)
fun frontier (leaf x) = [x]
 frontier (node (l,r)) = frontier l @ frontier r ;
val frontier = fn : 'a tree > 'a list
 frontier (node(leaf "hello", leaf "goodbye"));
val it = ["hello","goodbye"] : string list
frontier(leaf 5);
val it = [5] : int list
(* Expression tree *)
datatype expr = Numeral of int  Plus of expr * expr  Times of expr * expr;
fun eval (Numeral n) = n
 eval (Plus (e1, e2)) = (eval e1) + (eval e2)
 eval (Times (e1, e2)) = (eval e1) * (eval e2);
val t = Times (Plus (Numeral 3, Numeral 5), Numeral 7);
val t = Times (Plus (Numeral #,Numeral #),Numeral 7) : expr
eval t;
val it = 56 : int;
(* Tree with any number of children *)
datatype 'a otree = oleaf of 'a  onode of 'a otree list;
val t = onode [oleaf 3, oleaf 4, onode [oleaf 2]];
(* The leaves of a tree may themselves be trees *)
val t = node(leaf(node(leaf 3,leaf 4)),leaf(leaf(5)));
val t = node (leaf (node (#,#)),leaf (leaf 5)) : int tree tree
(* Corresponds to the structure
_____________________
 Node > Leaf 3 
Node > Leaf   
  > Leaf 4 
 ____________________

 ____________________
> Leaf  Leaf 5 
__________________
*)