## 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 (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.