CSE 428 Fall 1998 Midterm #2 Solution 18 November 1998 1. Give the {\em most general} types for each of the following function declarations. a. fun Curry3 f x y z = f(x,y,z); val Curry3 = fn : ('a * 'b * 'c -> 'd) -> 'a -> 'b -> 'c -> 'd b. fun unCurry3 f (x,y,z) = f x y z; val unCurry3 = fn : ('a -> 'b -> 'c -> 'd) -> 'a * 'b * 'c -> 'd c. fun nf (f,0) (x,y) = (x,y) |nf (f,n) (x,y) = f(nf (f,n-1) (x,y)); val nf = fn : ('a * 'b -> 'a * 'b) * int -> 'a * 'b -> 'a * 'b d. fun comp nil = 0 |comp (f::L) = f(comp L); val comp = fn : (int -> int) list -> int 2. Recall the definition of iterators for Assignment 6: fun iter(f,v) 0 = v |iter(f,v) n = f(iter(f,v) (n-1), n); fun gen_iter(f,g,h) (0,a) = g(a) |gen_iter(f,g,h) (n,a) = f(gen_iter(f,g,h) (n-1,h(n,a)), n,a); Give the value produced by each of the expressions below. a. let val p = iter(fn(x,y)=>x+y*y,0) in p 3 end; val it = 14 : int b. let val q = iter(fn(x,y)=>2*x,1) in q 4 end; val it = 16 : int c. let val r = gen_iter(fn(x,y,z)=>x*z,fn(x)=>1,fn(x,y)=>y) in r(2,3) end; val it = 9 : int 3. Recall the following function definitions: fun map f nil = nil |map f (x::xs) = (f x)::(map f xs); fun accumulate f a nil = a |accumulate f a (x::xs) = accumulate f (f a x) xs; fun reduce f a nil = a |reduce f a (x::xs) = f x (reduce f a xs); fun cons x y = x::y; fun snoc x y = y::x; For each of the following functions, give a brief explanation of what it does. (Each performs a commonly-defined function and can be described in a few words.) a. fun a(ys) = accumulate snoc nil ys; Reverse(ys) b. fun b(ys,zs) = reduce cons zs ys; Append(ys,zs) c. fun c(ys) = accumulate (fn x=>fn y=>x+y) 0 (map (fn z=>1) ys); Length(ys) d. fun d(f,ys) = reduce (fn x=>fn xs=>f(x)::xs) nil ys; Map(f,ys) 4. Recall the datatype declaration for types: datatype tp = tpint | tpbool | tpVar of string | ** of (tp * tp) | --> of (tp * tp); infixr 8 ** ; infixr 4 --> ; Write a function ground: tp -> bool which takes an object t:tp and returns true if t contains no type variables (i.e., no occurrences of tpVar). fun ground (t1 ** t2) = ground t1 andalso ground t2 |ground (t1 --> t2) = ground t1 andalso ground t2 |ground (tpVar _) = false |ground _ = true 5. Consider the following inductive definition of propositional formulae: * An identifier is a formula; * If p is a formula then \neg p is a formula; * If p_1 and p_2 are formulas, then p_1\wedge p_2 and p_1\vee p_2 are both formulae. We will assume that an identifier is simply any string. a. Give an SML {\em datatype} declaration for propositional formulae. (You do not need to include infix declarations) datatype prop = Atom of string | And of prop * prop | Or of prop * prop | Not of prop; b. What is the {\em induction principle} for formulae? To prove that P(a) holds for all propositional formulas a, we must show the following: (i) P(Atom(X)) holds for all strings X (ii) P(a) implies P(Not(a)) for all formulae a (iii) P(a1) and P(a2) implies P(And(a1,a2)) and P(Or(a1,a2)) for all formulae a1 and a2 6. In the movie {\em Bride of Chucky}, what was the name of Chucky's bride? TIFFANY