type 'a tree = Leaf of 'a | Fork of 'a * 'a tree * 'a tree let t1 = Leaf 5 let t2 = Fork (3, Leaf 3, Fork (2, t1, t1)) let t3 = Fork ("Hello", Leaf "World", Leaf "!") let rec t_size t = match t with | Leaf _ -> 1 | Fork (_, ta, tb) -> 1 + t_size ta + t_size tb let rec t_sum = function | Leaf v -> v | Fork (v, t1, t2) -> v + t_sum t1 + t_sum t2 let rec t_charcount = function | Leaf s -> String.length s | Fork (v, t1, t2) -> String.length v + t_charcount t1 + t_charcount t2 let rec t_concat = function | Leaf s -> s | Fork (v, t1, t2) -> v ^ t_concat t1 ^ t_concat t2 (* t_opt versions. *) (* After writing the first 4 functions they are to write 4 more, but with different names: t_opt_size, t_opt_sum, etc. Provide a few sample trees for this type as well. t_opt_size should count the number of values in the tree - that is, those under a "Some" constructor. I didn't make this clear. So we need something like the following: *) let rec t_opt_size (t: 'a option tree) : int = match t with | Leaf None -> 0 | Leaf (Some _) -> 1 | Fork (None, t1, t2) -> t_opt_size t1 + t_opt_size t2 | Fork (Some _, t1, t2) -> 1 + t_opt_size t1 + t_opt_size t2 let rec t_opt_sum (t: 'a option tree) : int = match t with | Leaf None -> 0 | Leaf (Some x) -> x | Fork (None, t1, t2) -> t_opt_sum t1 + t_opt_sum t2 | Fork (Some x, t1, t2) -> x + t_opt_sum t1 + t_opt_sum t2 let rec t_opt_charcount (t: string option tree) : int = match t with | Leaf None -> 0 | Leaf (Some s) -> String.length s | Fork (None, t1, t2) -> t_opt_charcount t1 + t_opt_charcount t2 | Fork (Some s, t1, t2) -> String.length s + t_opt_charcount t1 + t_opt_charcount t2 let rec t_opt_concat (t: string option tree) : string = match t with | Leaf None -> "" | Leaf (Some s) -> s | Fork (None, t1, t2) -> t_opt_concat t1 ^ t_opt_concat t2 | Fork (Some s, t1, t2) -> s ^ t_opt_concat t1 ^ t_opt_concat t2 (* t_fold versions. *) let rec tfold (l:'a -> 'b) (f:'a -> 'b -> 'b -> 'b) (t:'a tree) : 'b = match t with | Leaf v -> l v | Fork (v, t1, t2) -> f v (tfold l f t1) (tfold l f t2) let tf_size t = tfold (fun x -> 1) (fun a b c -> 1+b+c) t let tf_sum t = tfold (fun x -> x) (fun a b c -> a+b+c) t let tf_char_count t = tfold (fun x -> String.length x) (fun a b c -> String.length a + b + c) t let tf_concat t = tfold (fun x -> x) (fun a b c -> a ^ b ^ c) t let tf_opt_size t = let f o = match o with | None -> 0 | Some _ -> 1 in tfold f (fun a b c -> f a + b + c) t (* something similar for the other 3 tf_opt_.... functions *) let tf_opt_sum t = let f o = match o with | None -> 0 | Some x -> x in tfold f (fun a b c -> f a + b + c) t let tf_opt_char_count t = let f o = match o with | None -> 0 | Some x -> String.length x in tfold f (fun a b c -> f a + b + c) t let tf_opt_concat t = let f o = match o with | None -> "" | Some x -> x in tfold f (fun a b c -> f a ^ b ^ c) t (* Implementations. *) (* The type of tree that we have above is actually not so useful as it doesn't allow for an empty tree. So let's create a more useful tree. Note that we'll put the data on a Node in between the two sub-trees to indicate that they are sorted in that order. *) type 'a btree = Empty | Node of 'a btree * 'a * 'a btree let rec bt_insert_by (cmp: 'a -> 'a -> int) (elem: 'a) (t: 'a btree) : 'a btree = match t with | Empty -> Node (Empty, elem, Empty) | Node (t1, v, t2) -> if (cmp elem v) <= 0 then Node (bt_insert_by cmp elem t1, v, t2) else Node (t1, v, bt_insert_by cmp elem t2) let rec bt_elem_by (eq: 'a -> 'b -> bool) (elem: 'b) (t: 'a btree) : bool = match t with | Empty -> false | Node (t1, v, t2) -> eq v elem || bt_elem_by eq elem t1 || bt_elem_by eq elem t2 let rec bt_to_list (t: 'a btree) : 'a list = match t with | Empty -> [] | Node (t1, v, t2) -> bt_to_list t1 @ [v] @ bt_to_list t2 let rec btfold (e: 'b) (f:'b -> 'a -> 'b -> 'b) (t:'a btree) : 'b = match t with | Empty -> e | Node (t1, v, t2) -> f (btfold e f t1) v (btfold e f t2) let btf_to_list (t: 'a btree) : 'a list = btfold [] (fun l1 v l2 -> l1 @ [v] @ l2) t let btf_elem_by (eq: 'a -> 'b -> bool) (elem: 'b) (t: 'a btree) : bool = btfold false (fun b1 v b2 -> eq v elem || b1 || b2) t