FALL '97  MIDTERM #2 SOLUTION

1.

- fun noc (x,w) = w::x;
val noc = fn : 'a list * 'a -> 'a list
- fun accumulate(f,a,nil) = a
   |accumulate(f,a,x::xs) = accumulate(f, f(a,x), xs);
val accumulate = fn : ('a * 'b -> 'a) * 'a * 'b list -> 'a
- fun tc 0 f x = x
   |tc n f x = f(tc (n-1) f x);
val tc = fn : int -> ('a -> 'a) -> 'a -> 'a
- fun invert nil = nil
   |invert ((x,v)::L) = (v,x)::invert L;
val invert = fn : ('a * 'b) list -> ('b * 'a) list
- 

2.
- accumulate(noc,nil,[1,2,3]);
val it = [3,2,1] : int list
- tc 3 (fn n => n+1) 0;
val it = 3 : int
- map(invert,[[(1,2)],[(3,4),(4,5)]]);
val it = [[(2,1)],[(4,3),(5,4)]] : (int * int) list list
- map(map,[(fn n=>n+1,[1,2]), (fn n=>n+n,[1,2])]);
val it = [[2,3],[2,4]] : int list list
- 

3.
- datatype Itree = Node of (int * (Itree list));
datatype  Itree
  con Node : int * Itree list -> Itree

- datatype 'a twothree = leaf of 'a 
	     | TwoNode of 'a * 'a twothree * 'a twothree
	     | ThreeNode of 'a * 'a twothree * 'a twothree * 'a twothree;
datatype  'a twothree
  con ThreeNode : 'a * 'a twothree * 'a twothree * 'a twothree -> 'a twothree
  con TwoNode : 'a * 'a twothree * 'a twothree -> 'a twothree
  con leaf : 'a -> 'a twothree
- 

4.

- fun churchnot cb = cb (fn x => fn y => y) (fn x => fn y => x);
val churchnot = fn : (('a -> 'b -> 'b) -> ('c -> 'd -> 'c) -> 'e) -> 'e


- fun even cb = cb churchnot (fn x => fn y => x);
val even = fn
  : (((('a -> 'b -> 'b) -> ('c -> 'd -> 'c) -> 'e) -> 'e)
     -> ('f -> 'g -> 'f) -> 'h)
    -> 'h
- 


5. 

(\x\y.x) (\u\v.u) p (\z.z) r --> \z.z
(\f((\x.f(x x)) (\x.f(x x)))) \z.z   --> no normal form
(\x\y\z.(xz)(yz)) (\w.w) --> \y\z.z(yz)
\x.(x(\y.y))  -- already in normal form