CS496 Homework 2 Solution

ts. Excerpts of code presented in class can be used.
Assignments from previous offerings of the course must not be re-used. Violations will be penalized appropriately.
2 Assignment
type ’a gt = Node of ’a*(’a gt) list
The type ’a gt has only one constructor, namely Node, whose argument is a tuple of type ’a*(’a gt) list. Thus a general tree is a node that has a data value of type ’a and a list of children (each of which are general trees). The simplest example of a general tree is a leaf. Leaves have an empty list of children. For example, the expression Node(12,[]), of type int gt, models a leaf that holds the integer 12 as data. The following expression t, of type int gt, represents the tree depicted in Figure 1:

Figure 1: Sample value of type int gt
let t : int gt =
Node (33,
[Node (12,[]); Node (77,
[Node (37,
[Node (14, [])]);
Node (48, []);
Node (103, [])])
])
2
4
6
8
Here is a sample function that given n builds a general tree that is a leaf holding n as data.
let mk_leaf : ’a -> ’a gt =
fun n ->
Node(n,[])
2
For example, mk_leaf 12 returns the leaf Node(12,[]).
3 Operations to be Implemented
Please implement the following operations. For each operation, indicate its type by annotating the function definition as seen in class.
1. height: that given a general tree returns its height. The height of a tree is the length of the longest (in terms of number of nodes) path from the root to a leaf. Eg.
# height t;;
- : int = 4
2
2. size: that given a general tree returns its size. The size of a general tree consists of the number of nodes.
# size t;; - : int = 7
2
3. paths_to_leaves t: returns a list with all the paths from the root to the leaves of the general tree t. Let n be the largest number of children of any node in t. A path is a list of numbers in the set {0,1,...,n−1} such that if we follow it on the tree, it leads to a leaf. The order in which the paths are listed is irrelevant. Eg.
# paths_to_leaves t;;
- : int list list = [[0]; [1; 0; 0]; [1; 1]; [1; 2]]
2
4. is_leaf_perfect: that determines whether a general tree is leaf perfect. A general tree is said to be leaf perfect if all leaves have the same depth. Eg.
# is_leaf_perfect t;;
- : bool = false
2
5. preorder: that returns the pre-order traversal of a general tree. Eg.
# preorder t;;
- : int list = [33; 12; 77; 37; 14; 48; 103]
2
6. mirror: that returns the mirror image of a general tree. Eg.
# mirror t;;
- : int gt =
Node (33,
[Node (77, [Node (103, []); Node (48, []); Node (37, [Node (14, [])])]);
Node (12, [])])
2
4
7. mapt f t: that produces a general tree resulting from t by mapping function f to each data item in d. Eg.
mapt (fun i -> i>20) t;;
- : bool gt =
Node (true,
[Node (false, []);
Node (true,
[Node (true, [Node (false, [])]); Node (true, []); Node (true, [])])])
2
4
6
8. foldt f t: that encodes the recursion scheme over general trees. Its type is
foldt: (’a -> ’b list -> ’b) -> ’a gt -> ’b
let sumt t = foldt (fun i rs -> i + List.fold_left (fun i j -> i+j) 0 rs) t
let memt t e =
foldt (fun i rs -> i=e || List.exists (fun i -> i) rs) t
2
4
Here is the result of applying these functions in some examples involving t,
# sumt t ;;
- : int = 324
# memt t 12;;
- : bool = true # memt t 33;;
- : bool = true
# memt t 35;;
- : bool = false
2
4
6
8
9. Implement mirror’ using foldt. It should behave just like Exercise 6.
4 Submission instructions
Submit a file gt.ml through Canvas. Each exercise is worth ten points, except the last two which are worth 15 points each.