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?