(* task 2 *) datatype Expr = Val of int | Plus of Expr * Expr | Times of Expr * Expr | Neg of Expr; fun eval (Val v) = v | eval (Plus (e1, e2)) = (eval e1) + (eval e2) | eval (Times (e1, e2)) = (eval e1) * (eval e2) | eval (Neg e) = ~(eval e); (* Task 5 *) (* Binary Trees *) datatype 'a Tree = Lf | Br of 'a * 'a Tree * 'a Tree exception Missing val natrange = let fun nr l a b i = if b < a then l else nr (b :: l) a (b-i) i in nr [] end; datatype Ord = EQ | LT | GT fun lookup b x Lf = raise Missing | lookup b x (Br ((x',y),t1,t2)) = case b x x' of EQ => y | LT => lookup b x t1 | GT => lookup b x t2; fun update b ((x, y), Lf) = Br ((x,y), Lf, Lf) | update b ((x, y), (Br ((x',y'), t1, t2))) = case b x x' of EQ => Br ((x',y), t1, t2) | LT => Br ((x',y'), (update b ((x, y), t1)), t2)| GT => Br ((x',y'), t1 , (update b ((x, y), t2))); exception Collision of int; fun insert (x,y) Lf = Br ((x,y),Lf,Lf) | insert (x,y) (Br ((x',y'), t1, t2)) = if x < x' then Br ((x',y'), insert (x,y) t1, t2) else if x > x' then Br ((x',y'), t1, insert (x,y) t2) else raise Collision y' fun deleteLeftmost (Br (kv,Lf,tr)) = (kv, tr) | deleteLeftmost (Br (kv,tl,tr)) = let val (kv', t) = deleteLeftmost tl in (kv',Br (kv, t, tr)) end; fun delete b x Lf = Lf | delete b x (Br ((x',y'),tl,tr)) = case b x x' of EQ => (case tr of Lf => tl | Br (_,Lf,_) => tr | Br (_,tl',_) => let val (kv, t) = deleteLeftmost tl' in Br (kv,tl,t) end) | LT => Br ((x',y'), delete b x tl, tr) | GT => Br ((x',y'), tl, delete b x tr); (* test the binary tree *) fun list2tree b l = foldr (update b) Lf l; fun intb x y = if x < y then LT else if x > y then GT else EQ; fun flatten Lf = [] | flatten (Br (a,t1,t2)) = (flatten t1) @ [a] @ (flatten t2); fun increasing b [] = true | increasing b [x] = true | increasing b (x::y::l) = if b (x, y) then increasing b (y::l) else false; local val a = 16807.0 and m = 2147489.0 in fun nextrandom seed = let val t = a*seed in t - m * real(floor(t/m)) end and truncto k r = 1 + floor((r / m) * (real k)) end; fun randlist (n,seed,seeds) = if n=0 then (seed,seeds) else randlist(n-1, (nextrandom seed), seed::seeds); val (seed,rs) = randlist(10000, 1.0, []); val testList = map (fn x => let val y = trunc x in (y,y) end) rs; val testTree = list2tree intb testList; fun snd (_,y) = y; fun fst (x,_) = x; fun foldr' f b al = foldr (fn (x,y) => f x y) b al; val testTreeDel = foldr' (delete intb) testTree (map fst (List.take(testList,2000))); val testTreeDelList = flatten testTreeDel; val test1 = increasing Int.< (map fst testTreeDelList);