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

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 ;;

...

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 ;; ```

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
((...)::(...),(...)::(...))
;;
```
```

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);; ```

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);; ```