(* Exercise 1 *)
datatype 'a tsil = LIN | SNOC of 'a tsil * 'a;
(* Exercise 1 part a *)
fun list2tsil (lists)
= let fun visit nil
= LIN
| visit (list :: lists)
= SNOC ((visit lists), list)
in visit lists
end;
fun tsil2list (lists)
= let fun visit LIN
= nil
| visit (SNOC (lists,list))
= list :: (visit lists)
in visit lists
end;
(* Exercise 1 part b *)
structure Our_Tsil
= struct
(* Exercise 1 part b LENGTH *)
fun length LIN
= 0
| length (SNOC (xs,x))
= 1 + (length xs)
(* Exercise 1 part b REVERSE *)
fun reverse (tsils)
= let fun visit (LIN,a)
= a
| visit (SNOC (tsil,elm),a)
= visit (tsil,SNOC(a,elm))
in visit (tsils,LIN)
end;
(* Exercise 1 part b CONCAT *)
fun concat (tsil1,tsil2)
= let fun visit (t1,LIN)
= t1
| visit (t1,SNOC(t2,elm))
= visit (SNOC(t1,elm),t2)
in visit (tsil1,tsil2)
end;
(* Exercise 1 part b MAP *)
fun map (inductive,tsil)
= let fun visit (LIN)
= LIN
| visit(SNOC(ts,elm))
= SNOC ((visit ts),(inductive elm))
in visit (tsil)
end;
(* Exercise 1 part b MAP_APPEND *)
fun map_append (f,tsils)
= let fun visit LIN
= LIN
| visit(SNOC(ts,elm))
= concat((visit ts), (f elm))
in visit (tsils)
end;
end;
(* Exercise 1 part c TESTS *)
Our_Tsil.length(list2tsil [1,2,3,4]);
tsil2list (Our_Tsil.reverse(list2tsil [1,2,3,4,5]));
tsil2list (Our_Tsil.concat(list2tsil [1], list2tsil [4]));
tsil2list (Our_Tsil.reverse (list2tsil [1,2,3]));
tsil2list (Our_Tsil.map(fn x => x*x, list2tsil [1,2,3] ));
tsil2list (Our_Tsil.map_append((fn x => list2tsil [1,2+x]),list2tsil [1,2,3] ));
(* Exercise 2 *)
datatype 'a tree = LEAF | NODE of 'a tree * 'a * 'a tree;
(* Exercise 2 part a *)
fun max_elm (tree)
= let fun visit (LEAF)
= 0 (* INSERT Int.minInt here *)
| visit (NODE(left,elm,right))
= Int.max(Int.max(visit(left), elm), visit(right))
in visit(tree)
end;
(* Exercise 2 part b *)
fun depth (tree)
= let fun visit (LEAF)
= 0
| visit (NODE(left,elm,right))
= 1 + Int.max(visit(left),visit(right))
in visit(tree)
end;
(* Exercise 2 part c *)
fun weight (tree)
= let fun visit (LEAF)
= 0
| visit (NODE(left,elm,right))
= visit(left) + elm + visit(right)
in visit(tree)
end;
(* Exercise 2 part d *)
fun balanced (tree)
= let fun visit(LEAF)
= true
| visit(NODE(left,elm,right))
= if weight(left) = weight(right)
then if visit(left)
then visit(right)
else false
else false
in visit (tree)
end;
(* Exercise 2 part e *)
fun swaptree (tree)
= let fun visit(LEAF)
= LEAF
| visit(NODE(left,elm,right))
= NODE(visit(right),elm,visit(left))
in visit (tree)
end;
(* Exercise 2 part f *)
fun fold (lea, nod, t)
= let fun visit (LEAF)
= lea LEAF
| visit(NODE(left,elm,right))
= let val r_l = visit left
val r_r = visit right
in nod (r_l, elm, r_r)
end
in visit t
end;
(* Exercise 2 part g-a *)
fun max_elm' (tree)
= fold (fn x => 0 (* intMin, again *),
fn (l,e,r) => Int.max(Int.max(l,e),r), tree);
(* Exercise 2 part g-b *)
fun depth' (tree)
= fold (fn x => 0,
fn (l,e,r) => 1 + Int.max(l,r), tree);
(* Exercise 2 part g-c *)
fun weight' (tree)
= fold (fn x => 0,
fn (l,e,r) => e + l + r, tree);
(* Exercise 2 part g-d *)
(* Nontrivial. The ``int option'' type is used, so that ``NONE'' at any point means
* ``unbalanced'' and a SOME(w) is a weight of a balanced subtree.
* The base case here is the weightless leaf ``subtree'', which is balanced.
* The inductive case is least true of the balance-determining booleans. *)
fun balanced' (tree)
= case fold (fn x => SOME(0),
fn (NONE, x, NONE) => NONE
| (NONE, x, SOME w_r) => NONE
| (SOME w_l, x, NONE) => NONE
| (SOME w_l, x, SOME w_r) => if w_l = w_r then SOME(w_l+x+w_r) else NONE
, tree)
(* correlate to real boolean values: *)
of NONE => false
| (SOME _) => true;
(* Exercise 2 part g-e *)
fun swaptree' (tree)
= fold (fn x => x,
fn (l,e,r) => NODE(r,e,l), tree);
(* Exercise 2 part h *)
(* Choosing in-order, here *)
fun flatten (tree)
= fold (fn x => [],
fn (l_l, x, l_r) => l_l @ [x] @ l_r
,tree);
(* Exercise 2 part i *)
fun make_adders (tree)
= fold (fn x => LEAF,
fn (t_l, x, t_r) => NODE(t_l, fn t => t + x, t_r)
,tree);
(* Exercise 2 part j *)
(* Note that this only applies to (int -> int) tree's. *)
fun map_adders (tree,addend : int)
= fold (fn x => LEAF,
fn (t_l, x, t_r) => NODE(t_l, (x : int -> int ) addend , t_r)
,tree);
(* Tests *)
val t1 = NODE ( NODE( LEAF,7,LEAF),8, NODE(LEAF,9,LEAF));
val t2 = NODE ( NODE( LEAF,7,LEAF ),8,NODE(LEAF,7,LEAF));
val t3 = NODE ( NODE( NODE( LEAF,7,LEAF ),7,LEAF ),8,NODE(LEAF,10,LEAF));
val max_conv_t2 = max_elm t2;
val depth_conv_t2 = depth t2;
val depth_conv_t3 = depth t3;
val weight_conv_t3 = weight t3;
val balanced_conv_t2 = balanced t2;
val balanced_conv_t3 = balanced t3;
val swaptree_conv_t1 = swaptree t1;
val swaptree_conv_t2 = swaptree t2;
val swaptree_conv_t3 = swaptree t3;
val max_para_t2 = max_elm' t2;
val depth_para_t2 = depth' t2;
val depth_para_t3 = depth' t3;
val weight_para_t3 = weight' t3;
val balanced_para_t2 = balanced' t2;
val balanced_para_t3 = balanced' t3;
val swaptree_para_t1 = swaptree' t1;
val swaptree_para_t2 = swaptree' t2;
val swaptree_para_t3 = swaptree' t3;
val flatten_t1 = flatten t1;
val flatten_t2 = flatten t2;
val flatten_t3 = flatten t3;
val make_adders_t3 = make_adders t3;
val map_adders_t3_2 = map_adders(make_adders t3, 2);
val map_adders_t3_102 = map_adders(make_adders t3, 102);
(* vim:syntax:syntax=sml:
*)