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.
_______________________________________________________________________
________________________________________________________________________