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


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.