## Description

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