CS223 Spring 2012
Midterm Exam
4/30/2012, 11:30am-12:20pm, Ryerson 276

1. [20] Consider the following let expression (using ML surface
syntax, but this translates easily to the toy language of
typecheck2/syntax.sml):

  let val r = ref(fn x => x)
   in r := (fn y => y + 1);
      (!r) true
  end;

We assume ref, :=, and ! have the usual polymorphic types in
the base context:

  ref : 'a -> 'a ref
  :=  : 'a ref * 'a -> unit
  !   : 'a ref -> 'a

(a) Using the typechecking algorithm from typecheck2, does this
expression type check? If so, what is it's type (you do not need
to do a detailed derivation of the type).

(b) Does it type check in SML? Explain why or why not.


2. [15] Define a function

  interleave : 'a list -> 'a list -> 'a list

that interleaves two lists. I.e.

  interleave [1,2,3] [4,5,6,7,8] ==> [1,4,2,5,3,6,7,8]


3. [15] Explain in detail how to type check the following
variable declaration:

   f = fn x => if null x then 1 else hd x + 1

As usual, use capital letters in the range P .. Z for the unification
type variables. The list functions null and hd have their usual
polymorphic types.


4. [10] Give the type of the function h in the context of the
following definition (this type will involve types of other variables
in the declaration of f). Just the type is required, not a full
derivation of it.

  fun f x =
      let val y = x::nil
	  fun g z = (rev z, x) :: nil
	  fun h u = tl (g u)
       in h [1,2] end;


5. [15] (a) What is the type of the following function f?  (b) What
does it do?  (d) Redefine it using one of the list fold functions
(foldl or foldr).

  fun f (nil, ys) = ys
    | f (x::xs, ys) = f (xs, x::ys)


6. [25] Represent a labeled binary tree using the datatype:

  datatype 'a tree
    = Lf                             (* leaf node *)
    | Br of 'a * 'a tree * 'a tree   (* branch node labeled by 'a *)
 
Write a function that determines whether two arbitrary trees 
t and u satisfy t = reflect u, where reflect is defined by:

  (* reflect : 'a tree -> 'a tree *)
  fun reflect Lf = Lf
    | reflect (Br(v,t1,t2)) = Br(v, reflect t2, reflect t1)

It relects a tree horizontally into a "mirror image" of itself.

The function specification will be:

   val mirror : ''a tree * ''a tree -> bool

It has an equality polymorphic type because generic equality will
have to be used to compare labels having the type ''a.