Here are some questions not on the midterm but are pretty good exam
questions (if I do say so myself).
1. ML has an expression form (e1; e2) with this meaning:
* evaluate e1 to a value v1
* evaluate e2 to a value v2
* the result of (e1; e2) is v2
(a) Give an equivalent definition of (e1; e2) using syntactic sugar.
(b) What should the type-checking rule for (e1; e2) be?
(c) Under what circumstances is (e1; e2) contextually equivalent to e2?
2. For each of the following, decide if the result is a function that
always returns its argument plus 1.
(a) let val x = 1
val y = x
val x = 2
in
fn z => y + z
end
(b) let val x = 2
fun f y = y + x
val x = 1
in
f
end
(c) exception E;
fun x => ((x + raise E) handle E => x + 1)
3. Consider fun h (f,g,x) = f (g (f x))
What is the type of h?
4. Write a function filter of type ('a list) * ('a -> bool) -> ('a
list). The result list should have every element from the first
argument such that the second argument applied to the element
returns true.
5. Using the filter function from the previous problem, write a
function of type (int * int * (int list)) -> int list. The result
should have every element from the third argument that is greater
than or equal to the first argument and less than or equal to the
second argument.
6. Consider this code:
fun insert (i,lst) =
case lst of
[] => i::[]
| hd::tl => if i < hd then i :: lst else hd :: (insert (i,tl))
fun sort lst =
case lst of
[] => []
| hd::tl => insert (hd, (sort tl))
(a) Are sort [1,2,3,4,5] and sort [5,4,3,2,1] contextually equivalent?
(b) Does evaluating sort [1,2,3,4,5] create more, less, or the same
number of cons cells as evaluating sort [5,4,3,2,1]?
7. Consider this code:
signature S =
sig
type t
val Foo : int -> t
val f : int*int -> t
val sum : t -> int
end
structure M :> S =
struct
datatype t = Foo of int | Bar of int*int
fun f (i,j) = Bar (3,4)
fun sum x =
case x of
Foo _ => 7
Bar(a,b) => a + b
...
end
(a) Does this type-check? In particular, can structure M have
signature S?
(b) What is the type of f inside structure M (where the ... is)?
What is the type of f outside structure M?
(c) Is sum a constant function inside structure M (where the ... is)?
Is sum a constant function outside structure M?