Homework Assignment 2 Solution

    • Assignment Policies

Under absolutely no circumstances code can be exchanged between students.

Excerpts of code presented in class can be used.

Assignments from previous o erings of the course must not be re-used. Viola-tions will be penalized appropriately.

    • Assignment

This assignment has two sections. The rst one addresses the de nition of a type dTree encoding binary decision trees in OCaml using algebraic data types and then de ning 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.

    • The Type dTree  in OCaml

        1. De ne dTree, an algebraic type in OCaml which encodes binary decision trees as de-picted in Fig 1. The names of the two constructors should be Leaf and Node. Note that leaves and nodes hold values of di erent 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. De ne 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’


’w’

’x’
8

’x’

’y’
2
5
2
5
7
5


Figure 1: Sample values of type dTree



        ◦ d T r e e _ h e i g h t 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.

        ◦ d T r e e _ s i z e  tLeft ;;

    • -  :  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 f0; 1g 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.


    • d T r e e _ p a t h s  tLeft ;;

    • -  :  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.


    • d T r e e _ i s _ p e r f e c t  tLeft ;;

    • -  :  bool  =  false

        ◦ d T r e e _ i s _ p e r f e c t 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

    • 6


2


x
y
z
f



0
0
0
0

([ ’ x ’; ’ y ’; ’ z ’] ,
0
0
1
1
2
[([0;0;0] ,
0);





([0;0;1] ,
1);
0
1
0
1














4
([0;1;0] ,
1);
0
1
1
0

([0;1;1] ,
0);
1
0
0
1
6
([1;0;0] ,
1);





([1;0;1] ,
0);
1
0
1
0














8
([1;1;0] ,
0);
1
1
0
0








([1;1;1] ,
1)])
1
1
1
1











Figure 2: Binary function and its encoding in OCaml

    • An Application of dTrees: Encoding Boolean Func-tions


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 rst consider the pair-encoding. The pair-encoding consists of a pair where the rst component is the list of its parameters and the second is its graph. For example, the pair-encoding 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



’y


’z

’z

’z

’z
0
1
1
0
1
0
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. De ne 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



’y


’z

’z

’z

’z
0
0
0
0
0
0
0
0

    5. De ne 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. De ne 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.

    • Submission instructions

Submit a    le 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