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