CS 130 Fall 07: Sample Questions for Final _________________________________________________________________________ _________________________________________________________________________ Problem 1: --------- For each ML function given below, if the function is well typed, then write down its type, otherwise explain in less than two lines why Ocaml rejects the function. (a) let rec rev l = match l with [] -> [] | (h::t) -> (rev t)::h (b) let rec f l = match l with [] -> [] | (h::t) -> (List.hd h)::t (c) let rec f (tup,l) = match l with [] -> 0 | (h::t) -> tup.h + f (tup,t) (d) let rec f (x,y) = if x then (List.hd y) + 20 else if not x then 0 else y (e) let rec f l = match l with [] -> [] | f (h::t) -> h @ (flatten t) _________________________________________________________________________ Problem 2: --------- Which of the functions below are tail recursive ? Also, for each function, write down its type. For the ones that are not, write down tail recursive versions that achieve the same task. (a) let rec map f l = match l with [] -> [] | (h::t) -> (f h) :: (map f t) (b) let rec fold f b l = match l with [] -> b | (h::t) -> fold f (f (h,b)) t (c) let rec len l = match l with [] -> 0 | (h::t) -> 1 + len t (d) let rec f (n,l) = match l with [] -> n | (n,h::t) = if (h>n) then f (h,t) else f(n,t) Solution: run Ocaml to get types. -------- (a) Not tail recursive. let map f l = let rec helper (acc,l') = match l' with [] -> acc | (acc,h::t) = helper((f h)::acc,t) in List.rev(helper([],l)) (b) Tail recursive. (c) Not tail recursive. let len l = let rec helper (n,l') = match l' with [] -> n | helper (n,_::t) = helper(s+1,t) in helper(0,t) (d) Tail recursive. _________________________________________________________________________ Problem 3: --------- The following datatype can be used to represent arbitrarily nested lists. type 'a nlist = Nil | Cons of 'a elt * 'a nlist and 'a elt = E of 'a | NL of 'a nlist The list [1,2] could be represented as Cons(E 1,Cons(E 2,Nil)), the list [[1],2] as Cons(NL(Cons((E 1),Nil)),Cons(E 2,Nil)) and the list [[[],[1]],2] as Cons(NL(Cons(NL Nil,Cons (E 1,Nil))), Cons(E 2,Nil)). Using only pattern-matching (i.e. no if-then-else expressions): (a) Write a function: nlist_toString: ('a -> string) -> 'a nlist -> string such that if nl is bound to Cons(NL(Cons(NL Nil,Cons (E 1,Nil))), Cons(E 2,Nil)), then (nlist_toString Int.toString nl) evaluates to: "[[[],[1]],2]". (b) Write a function flatten: 'a nlist -> 'a list that returns the list of elements appearing in the nested list in order. Thus when applied to any of the lists shown above, flatten returns the list [1,2]. _________________________________________________________________________ Problem 4: --------- We say that two expressions e1 and e2 are semantically equivalent if in every environment E, evaluating e1 and evaluating e2 produces the same result. For each of the following pairs of expressions, explain why they are semantically equivalent, or if not, then give an environment that distinguishes the two, i.e. in which evaluating the two expressions gives different results. (a) (* e1 *) let x = 0 in x (* e2 *) let x = (f 1) * 0 in x (b) (* e1 *) (fun a -> fun b -> a + b) p q (* e2 *) (fun b -> fun a -> b + a) p q (c) (* e1 *) let x = a + 1 in let y = b + 2 in 2*x + 3*y (* e2 *) let y = b + 2 in let x = a + 1 in 2*x + 3*y (d) (* e1 *) let x = a + 1 in let y = x + 2 in 2*x + 3*y (* e2 *) let y = x + 2 in let x = a + 1 in 2*x + 3*y Solution: -------- (a) Not equivalent: as f may not terminate or throw an exception! Distinguishing environment: where f is: fun f x = f x (b) Equivalent -- as the arguments or "formals" for the two functions have just been renamed. (c) Equivalent -- as only difference is order but the same expressions are evaluated in both cases giving same values. (d) Not Equivalent -- a distinguishing environment is where x is bound to 0 and a is bound to 0,a are bound to 0,0. The "free" occurrence of x gets its value 0 from the environment, and thus y gets bound differently leading to different evaluations. _________________________________________________________________________ Problem 5: --------- Does the following code work correctly ? If not, find and fix the bug. (a) For PA #2, Problem #1 (c): let rec ffor (i,j,f) = if i=j then () else ((f i); ffor (i+1,j,f)) (b) For PA #2, Problem #1 (b): Recall that isMember (x,l) returns true if the value x appears in the list l, and listReverse l returns a list with the the elements of l in reversed order. let cleanList l = let rec helper (seen,rest) = match rest with [] -> seen | h::t -> let seen' = if isMember (h,t) then seen else (h::seen) in let rest' = t in helper (seen',rest') in listReverse (helper ([],l)) (c) Implementation of a function pow : 'a list -> 'a list list which takes a list [x1,...,xn] and returns the list of all subsets of {x1,...,xn}. That is: pow [1,2,3] should return [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]], though the actual "order" of the subsets doesnt matter (i.e. its ok to also return [[1,2,3],[1,2],[1],[2,3],[2],[1,3],[3],[]] (or any other permutation). let pow l = match l with [] -> [] | (h::t) -> let val sub = pow t in (map (fun l -> h::l) sub) _________________________________________________________________________ Problem 6: --------- Consider the following structure: module L : LSIG = struct type my int list = Empty | Cons of int * my int list exception BadList let makeOne i = Cons(i,Empty) let makeCons (i,l) = Cons(i,l) let my hd lst = ________________________ let my tl lst = ________________________ end (a) Write bodies for my_hd and my_tl such that each takes a value of type my_int_list, raises BadList if the value is Empty, and evaluates to the first (for my_hd) or second (for my_tl) element of the pair that Cons carries. (b) For each of the following LSIG definitions, determine if a client of L can make BadList get raised. If so, give an example client for which BadList is raised. If not, briefly explain why not. (i) module type LSIG = sig datatype my_int_list = Empty | Cons of int * my_int_list val my_hd : my_int_list -> int val makeOne : int -> my_int_list end (ii) module type LSIG = sig type my_int_list val makeCons : int * my_int_list -> my_int_list val my_hd : my_int_list -> int val makeOne : int -> my_int_list end (iii) module type LSIG = sig type my_int_list; val makeCons : int * my_int_list -> my_int_list val my_tl : my_int_list -> my_int_list val makeOne : int -> my_int_list end _________________________________________________________________________ Problem 7: --------- Below we list some Scala functions and two inputs for each function. Describe the result of running each function on the two inputs shown. Report what value is computed if the function finishes successfuly, or write "error" if an exception is thrown. (a) def rev[A](xs: List[A]) : List[A] = xs match { case Nil => List() case h::t => rev(t) ++ List(h) } Inputs:(i) List(1,2,3) (ii) List(List(), 1, List(2)) (b) def f[A](xs: List[List[A]] : List[A] = xs match { case Nil => List() case h::t => List(h(0)) ++ f(t) } Inputs:(i) [1,2,3] (ii) [[0],[1,2],[2, 3, 4]] (d) def f(x: Boolean, y: List[Int]) = if (x) { y(0) + 10 } else { 0 } Inputs:(i) (false, List(1,2,3)) (ii) (true, List(1,2,3)) ________________________________________________________________________ Problem 10: ---------- Consider the following Scala code. class E1 extends Throwable class E2 extends E1 class E3 extends E2 def f(){ println("begin f") try{ g() } catch { case _:E1 => () } println("end f") def g(){ println("begin g") try { h() } catch { case _:E3 => () } println("end g") def h(){ println("begin h") throw (new E2) println("end h") What is the result of: scala> f() i.e. of calling the function f ? ________________________________________________________________________ Problem 11: ---------- Consider the following Scala code: trait A { def m(y: A): Unit } trait C extends A { def n(y: C): A } class B extends A { val x : Int def m(y: A){ return } } class D extends B { val y: Int = 0 } class E extends B with C { def n(z: C): A = { return z; } } (a) Name the types, classes and interfaces that have been created. (b) Which of the following is true ? (i) A <: B (ii) A <: C (iii) B <: A (iv) D <: C (v) D <: B (vi) E <: C (vii) E <: B (viii) E <: A (c) Which of the following is true ? (i) A inherits from B (ii) A inherits from C (iii) B inherits from A (iv) D inherits from C (v) D inherits from B (vi) E inherits from C (vii) E inherits from B (viii) E inherits from A (d) Consider the following methods. Which of them typecheck ? (i) def fa(A x): Unit = { x.m(x); }; (ii) def fb(B x): Unit = { x.n(x); }; (iii) def fc(C x): Unit = { x.n(x); }; (e) Suppose that there were methods: def fa(x: A): Unit = { return } def fb(x: B): Unit = { return } def fc(x: C): Unit = { return } Which of the following typecheck ? Explain. (i) val a:A = new A fa(a) (ii) val b:B = new B fa(b) (iii) val b:B = new B fc(b) (iv) val d:D = new D fa(d) (v) val d:D = new D fa(d) fb(d) fc(d) (vi) val e:E = new E fa(e) fb(e) fc(e) Solution: -------- (a) Types: A,B,C,D,E. Classes: B,D,E Interfaces: A,C (b) True: (i),(iii),(v),(vi),(vii),(viii) (c) True: (v),(vii) (d) (i) and (iii) typecheck. (e) (i) No. Cannot instantiate an interface! (ii) Yes. B <: A (iii) No. B is not a subtype of C. (iv) Yes. D <: A (v) No. D is not a subtype of C. (vi) Yes. E <: A,B,C. _______________________________________________________________________ ________________________________________________________________________