Suggested Homework #3

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.