## Suggested Homework #3 (for Quiz #3 on 01/31/07)

Problem 1: Suppose that the following list of bindings was entered into the OCaml interpreter in the sequence shown. For each binding, write down :
(a) If the expression is accepted, the value bound ("fn" for functions) and its type,
(b) If the expression is rejected due to a type error, "type error",
(c) If the expression is rejected due to an unbound variable, the name of the variable that is not bound. Recall that if a type error occurs, then the variable binding does not happen. Check your answers by entering this sequence into the interpreter. ``` # type Tree = Leaf of int | Node of Tree * Tree;; # let b = Leaf [3]; # let c = Node (Leaf 3,Leaf 5); # let d = Node (Leaf 0,c); # let b = Node (c,d); # let f = fun a -> fun b -> a < b; # let g = f 0; # let z = g 4; # let x = g -3; ``` Problem 2: For each function below, determine if the function is tail recursive. ``` # let rec fact1 x = x * (fact (x-1)); # let fact2 x = let rec helper (n,r) = match n with 0 -> r | _ -> helper ((n-1),(x*r)) in helper (x,1) ;; # let rec add1 (n,y) = match n with 0 -> y | _ -> 1 + add1 (n-1,y) ;; # let rec add2 (n,y) = match n with 0 -> y | _ -> add2 (n-1,y+1); ``` Problem 3: Write the following functions on trees described using the datatype Tree shown in Problem 1.
• depth : Tree -> int where the depth of a leaf is 0 and the depth of an internal node is 1 greater than the maximum depths of its children.
• size : Tree -> int which computes the number of leaf nodes of a tree.
• sum : Tree -> int which adds up the values of all the leaves of the tree
• isLeaf : Tree * int -> bool which given a tree and an integer returns true if and only if the integer appears in a leaf of the tree.
• duplicate : Tree -> bool which given a tree returns true if and only if the tree has two distinct leaves with the same value.