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


  # 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 (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);;

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.