Assignment 2 dTree encoding binary decision trees

CS 496: Homework Assignment 2

2 Assignment
This assignment has two sections. The first one addresses the definition of a type dTree
encoding binary decision trees in OCaml using algebraic data types and then defining some
simple operations on them. Two examples of such trees are given in Fig. 1. The second
section presents a small application using dTrees which you are requested to implement.
3 The Type dTree in OCaml
1. Define dTree, an algebraic type in OCaml which encodes binary decision trees as depicted in Fig 1. The names of the two constructors should be Leaf and Node. Note that
leaves and nodes hold values of different types. Also, an expression of the form ’a’
has type char. Finally, note that values of type dtree cannot be empty, they are either
leaves or internal nodes.
2. Define two expressions, tLeft and tRight, of type dTree that represent each of the two
trees in Fig. 1:
let tLeft = (* complete *)
2
let tRight = (* complete *)
3. Implement the following functions indicating, for each one, its type. In the examples
below, we use tLeft to denote the example tree (Fig. 1–left) encoded as a value of type
dTree and similarly for tRight.
(a) dTree_height: that given a dTree returns its height. Eg.
1
’w’
’x’ 8
2 5
’w’
’y’
7 5
’x’
2 5
Figure 1: Sample values of type dTree
# dTree_height tLeft ;;
2 - : int = 2
(b) dTree_size: that given a dTree returns its size. The size of a dTree consists of the
number of nodes and leaves.
# dTree_size tLeft ;;
2 - : int = 5
(c) dTree_paths: that given a dTree returns a list with all the paths to its leaves. A
path is a list of digits in the set {0, 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.
# dTree_paths tLeft ;;
2 - : int list list = [[0; 0]; [0; 1]; [1]]
(d) dTree_is_perfect: that determines whether a dTree is perfect. A dTree is said to be
perfect if all leaves have the same depth. Eg.
# dTree_is_perfect tLeft ;;
2 - : bool = false
# dTree_is_perfect tRight ;;
4 - : bool = true
(e) dTree_map: that given the following arguments
f: char - char
g: int - int
t: dTree
returns a new dTree resulting from t by applying f to the characters in each node
and g to the numbers in each leaf. For example,
dTree_map Char.uppercase_ascii (fun x - x+1) tLeft
should return an expression of type dTree representing the tree
’W’
’X’ 9
3 6
2
x y z f
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
([ ’x ’; ’y ’; ’z ’] ,
2 [([0;0;0] , 0);
([0;0;1] , 1);
4 ([0;1;0] , 1);
([0;1;1] , 0);
6 ([1;0;0] , 1);
([1;0;1] , 0);
8 ([1;1;0] , 0);
([1;1;1] , 1)])
Figure 2: Binary function and its encoding in OCaml
4 An Application of dTrees: Encoding Boolean Functions
A boolean function is a function from booleans to booleans. An example is given on the left
in Fig. 2. There are many ways to encode boolean functions in OCaml; in this exercise we
consider two of them:
• pair-encoding
• tree-encoding
Let us first consider the pair-encoding. The pair-encoding consists of a pair where the first
component is the list of its parameters and the second is its graph. For example, the pairencoding of f is indicated in Fig. 2 on the right. The tree-encoding of a boolean function
consists of a codedTree in which each value of the function is given by a path in the tree
(the leaf at the end of the path). For example, the tree-encoding of f is:
’x
’y
’z
0 1
’z
1 0
’y
’z
1 0
’z
0 1
The aim of this exercise is to a function bf_to_dTree that takes a pair-encoding of a
boolean function and returns its tree-encoding.
4. Define list_to_tree, a function that given a list of characters l, creates a tree in which
the symbols of an inner node at level n corresponds to the n-th element in l. The
value of all of its leaves may be set to 0. E.g. list_to_tree [’x’;’y’;’z’] produces the
dTree representing:
3
’x
’y
’z
0 0
’z
0 0
’y
’z
0 0
’z
0 0
5. Define replace_leaf_at, a function that given a tree t and a graph for a function f,
replaces all the leaves in t by the value indicated in the graph of the function.
6. Define a function bf_to_dTree that takes a pair-encoding of a boolean function and
returns its tree-encoding. Note that, depending on the order in which the formal
parameters are processed, there may be more than one possible tree-encoding for a
given pair-encoding. You may return any of them.
5 Submission instructions
Submit a file hw2.ml through Canvas. Your grade will be determined as follows:
Exercise Grade
1 1
2 1
3(a)-(e) 5 (1 each)
4 1
5 1
6 1
4