Practice Problems for Midterm
Programming Assignments 1, 2 and 3
PA 1, 2, and 3 are all practice problems for the mideterm, and you
will get questions similar in nature to those assignments.
In addition, here are some additional practice problems.
Additional Practice Problem 1
Suppose that the following list of bindings was entered into the OCaml
interpreter.
For each binding, the interpreter responds with either:
(a) the name of the variable, its value, and its type, as shown for the
first binding in italics , or (b) a type error.
Fill in the blanks ("...") with how the interpreter
would respond if each of the bindings was entered in the sequence shown
below. Recall that if a type error occurs, then the variable binding does not
happen. Note that you could just enter this sequence into the interpreter
and see what happens, but this is a luxury you will not have during the
quiz.
 let x = 2 ;;
val x : int = 2
 let x = 2 + 3  4.0 ;;
...
 let x = 2 + 3 ;;
...
 let x = "a" ;;
...
 let x = (x,3) ;;
...
 let y = ((snd x)^"b" , 2) ;;
...
 let y = ((fst x)^"c" , 4) ;;
...
 let z = if (x = y) then (snd x) else (snd y) ;;
...
 type myrecord = {f1 : int; f2 : string ; f3 : int} ;;
 let a = {f1 = x; f2 = (fst y); f3 = z} ;;
...
 let b = z::(snd y)::[] ;;
...
 let c = (x;y;z) ;;
...
 let c = (x,y,z) ;;
...
 let m = if (snd x) = (snd y) then b else [] ;;
...
 let n = if (1 > 2) then ["a";"b"] else [] ;;
...
 let o = if (m = n) then 2 else 3 ;;
...
Additional Practice Problem 2
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.
 let a =
let x = 20 in
let y =
let x = 5 in
x + x
in
x + y
;;
 let b =
let x = "ab" in
let y = (let x = "cd" in x) ^ x in
x ^ y
;;
 let c =
let x = 22 in
x::y
;;
Additional Practice Problem 3
In each part below you are required to complete the implementation of a
function by filling in the appropriate expressions in the blanks (parts marked
...
).

(a)
everyOther : 'a list > 'a list , a function that takes a list and
returns every other element of the list, i.e. the application
everyOther [v1;v2;3;v4;v5;...] evaluates to [v1;v3;v5;...]
.
let everyOther l =
let rec helper (b,l) =
match l with
[] > ...
 h::t > if b then ... else ...
in
helper (true,l)
;;

(b)
zip : 'a list * 'b list > ('a * 'b) list , a function that
takes two lists (of equal length) and returns a list of pairs of
corresponding elements, i.e. the application
zip ([x1;x2;x3;...;xn],[y1;y2;y3;...;yn]) evaluates to
([(x1,y1);(x2,y2);(x3,y3);...;(xn,yn)]).
.
let rec zip (l1,l2) =
match (l1,l2) with
([],_) > ...
 (_,[]) > ...
 (h1::t1,h2::t2) > (...) :: (...)

(c)
unzip : 'a * 'b list > ('a list * 'b list ) , a function that
takes a list of pairs and returns two lists (of equal length) of the first
elements of the second elements of the pairs, respectively, i.e. the application
unzip [(x1,y1);(x2,y2);(x3,y3);...;(xn,yn)] evaluates to
([x1;x2;x3;...;xn],[y1;y2;y3;...;yn]) .
let rec unzip l =
match l with
(...) > ([],[])
 (...) >
let ... = ... in
((...)::(...),(...)::(...))
;;
Additional Practice Problem 4
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;;
Additional Practice Problem 5
For each function below, determine if the function is tail recursive.
# let rec fact1 x = x * (fact (x1));;
# let fact2 x =
let rec helper (n,r) =
match n with
0 > r
 _ > helper ((n1),(x*r))
in
helper (x,1)
;;
# let rec add1 (n,y) =
match n with
0 > y
 _ > 1 + add1 (n1,y)
;;
# let rec add2 (n,y) =
match n with
0 > y
 _ > add2 (n1,y+1);;
Additional Practice Problem 6
Write the following functions on trees described using the datatype tree
shown in Problem 4.
 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.