Following Code contains solutions in part to the excercises (traverse) and the exam from the Summersemester 2022 (print). It is meant to serve as a small guide to SML syntax and data types.
(* Helper function to recursively concatenate a list*)
fun concat list1 list2 = foldr (fn (head, tail) => head::tail) list1 list2;
(* Define the tree datatype *)
datatype 'a tree = empty | node of 'a * 'a tree * 'a tree;
(* Declare a tree for demonstration purporses *)
val t = node(1,node(2,node(3,empty,node(4,empty,empty)),empty),node(5,empty,empty));
(* Recursively count nodes of a tree *)
fun nodes (empty) = 0
| nodes (node (_, t1, t2)) = 1 + nodes t1 + nodes t2;
(* Recursively traverse a tree, appending values to the list *)
fun traverse (empty) = []
| traverse (node (v, t1, t2)) = concat (concat (traverse t2) (traverse t1)) [v];
(* Recurse the tree, printing nodes in a human-readable form *)
fun print (empty) = "_"
| print (node (v, t1, t2)) = "(" ^ (print t1) ^ ", " ^ (Int.toString v) ^ ", " ^ (print t2) ^ ")";
traverse t;
print t;
The outputs of traverse t; and print t; respectively yield
[1, 2, 3, 4, 5]: int list;
and
"(((_, 3, (_, 4, _)), 2, _), 1, (_, 5, _))": string;