(**** LECTURE 7: Datatypes and Trees ****) (* \$Id: datatypes.ML,v 1.1 1997/10/14 13:34:47 lcp Exp lcp \$ *) (** An enumeration type **) datatype vehicle = Bike | Motorbike | Car | Lorry; fun wheels Bike = 2 | wheels Motorbike = 2 | wheels Car = 4 | wheels Lorry = 18; (*A non-recursive datatype*) datatype vehicle = Bike | Motorbike of int (*engine size in CCs*) | Car of bool (*true if a Reliant Robin*) | Lorry of int; (*number of wheels*) (*A finer wheel computation*) fun wheels Bike = 2 | wheels (Motorbike _) = 2 | wheels (Car robin) = if robin then 3 else 4 | wheels (Lorry w) = w; (*actually used in lecture 9, queues*) fun wheels v = case v of Bike => 2 | Motorbike _ => 2 | Car robin => if robin then 3 else 4 | Lorry w => w; (*Nested Pattern-Matching*) fun greener (Bike, Motorbike _) = true | greener (Bike, Car _) = true | greener (Bike, Lorry _) = true | greener (Motorbike _, Car _) = true | greener (Motorbike _, Lorry _) = true | greener (Car _, Lorry _) = true | greener _ = false; fun greener (_, Bike) = false | greener (Bike, _) = true | greener (_, Motorbike _) = false | greener (Motorbike _, _) = true | greener (_, Car _) = false | greener (Car _, _) = true | greener (_, Lorry _) = false; exception Change; fun change (till, 0) = [] | change ([], amt) = raise Change | change (c::till, amt) = if amt<0 then raise Change else c :: change(c::till, amt-c) handle Change => change(till, amt); datatype 'a tree = Lf | Br of 'a * 'a tree * 'a tree; fun count Lf = 0 | count (Br(v,t1,t2)) = 1 + count t1 + count t2; fun leaves Lf = 1 | leaves (Br(v,t1,t2)) = leaves t1 + leaves t2; fun max (i,j): int = if i>j then i else j; fun depth Lf = 0 | depth (Br(v,t1,t2)) = 1 + max(depth t1, depth t2); (*Construct a full binary tree labelled breadth-first*) fun fulltree (k,n) = if n=0 then Lf else Br(k, fulltree(2*k, n-1), fulltree(2*k+1, n-1)); val t = fulltree (1,5); count t; leaves t; depth t; (** Tree traversal **) fun preorder Lf = [] | preorder (Br(v,t1,t2)) = [v] @ preorder t1 @ preorder t2; fun inorder Lf = [] | inorder (Br(v,t1,t2)) = inorder t1 @ [v] @ inorder t2; fun postorder Lf = [] | postorder (Br(v,t1,t2)) = postorder t1 @ postorder t2 @ [v]; (** Efficient versions **) fun preord (Lf, vs) = vs | preord (Br(v,t1,t2), vs) = v :: preord (t1, preord (t2, vs)); fun inord (Lf, vs) = vs | inord (Br(v,t1,t2), vs) = inord (t1, v::inord (t2, vs)); fun postord (Lf, vs) = vs | postord (Br(v,t1,t2), vs) = postord (t1, postord (t2, v::vs)); (** For lecture 11, functionals **) fun maptree f Lf = Lf | maptree f (Br(v,t1,t2)) = Br(f v, maptree f t1, maptree f t2); fun fold f e Lf = e | fold f e (Br(v,t1,t2)) = f (v, fold f e t1, fold f e t2); maptree (fn n => 2*n) t; fold (fn (x,y,z) => x+y+z) 0 t; fun infold f (Lf, e) = e | infold f (Br(v,t1,t2), e) = infold f (t1, f (v, infold f (t2, e))); infold op+ (t,0);