Solution of the Midterm #2
______________________________________________________________________________
Exercise 1
1. (Maximum: 5 points)
   The correct answer is (b). 
   The two declarations are not equivalent because in ML (as well as in 
   any other functional language) the meaning of a test 
       e1 = e2
   is: compute the value v1 of e1, 
       compute the value v2 of e2,
       and then give result true or false depending on whether 
       v1 and v2 are equal or not
   Thus the test
       t = consbt(x,t1,t2)
   gives an error since x, t1 and t2 are (generally) undefined. 

   People who have given answer (c) have got 3 points since, although 
   the two declarations are not equivalent, their answer makes sense
   in case x, t1 and t2 have been defined before.

2. (Maximum: 4 points)
   The correct answer is (a).
   A lot of people have given answer (b). I think it was because
   they didn't know the meaning of the keyword "rec" (forcing a 
   definition to be interpreted as "recursive") and thought that 
   rec was just a parameter. Thus I have given 3 points to them.
_____________________________________________________________________________
Exercise 2.
A possible definition is the following: 

fun nodes_which_satisfy p emptybt = []
  | nodes_which_satisfy p (consbt(x,t1,t2)) = 
          if p x 
             then x :: (nodes_which_satisfy p t1) @ (nodes_which_satisfy p t2)
             else      (nodes_which_satisfy p t1) @ (nodes_which_satisfy p t2);

______________________________________________________________________________
Exercise 3.
A possible definition is the following: 

fun merge [] l2 = l2
  | merge l1 [] = l1
  | merge (x1::l1) (x2::l2) = if x1 < x2 
                                 then x1 :: (merge l1 (x2::l2))
                                 else x2 :: (merge (x1::l1) l2);
______________________________________________________________________________
Exercise 4.

I list here various equivalent definitions:

fun compose f g h x = h(g(f x));

fun compose f g h = fn x => h(g(f x));

val compose = fn f => fn g => fn h => fn x => h(g(f x));

fun compose f g h = h o g o f;
_____________________________________________________________________________
Exercise 5. 

1. The type of   
      fn f => fn x => fn y => f x y 
   is 
      ('a -> 'b -> 'c) -> 'a -> 'b -> 'c

2. The type of
      fn f => fn (x,y) => f(x,y) 
   is 
      ('a * 'b -> 'c) -> 'a * 'b -> 'c

3. The type of 
      fn f => fn x => fn y => (f x,f y)
   is 
      ('a -> 'b) -> 'a -> 'a -> 'b * 'b

One can use his/her intuition to derive these types, or construct a formal 
proof. Since I have already written LN about the formal method, I will show
here the "intuitive method". (Note that the "intuitive method" is just a 
way of capturing with intuition the formal method.)
==============================================================================
1.
fn f => fn x => fn y => f x y  is a function, so its type must be of the form

  alpha -> beta -> gamma -> delta 

where alpha is the type of f, beta is the type of x, gamma is the type of y, 
and delta is the type of the result. 

Now, let us analyze how these types are related. In the resulting expression, 
f is applied to x and the result is applied to y (remember that f x y = (f x) y
because application is left-associative). Hence alpha = beta -> phi where phi
is the type of (f x). Since I then apply (f x) to y, and we have called delta
the type of the result, we must have phi = gamma -> delta. 

In conclusion the type is: 

  (beta -> gamma -> delta) -> beta -> gamma -> delta

(names are not important, only their relation is)

I have to put parentheses around the first beta -> gamma -> delta because
if I don't do that then I write the type

  beta -> gamma -> delta -> beta -> gamma -> delta

which is interpreted as

  beta -> (gamma -> (delta -> (beta -> (gamma -> delta))))))

since -> is right-associative.

==============================================================================
2. From now on I'll use the notation "z:t" to mean "t is the type of z".

fn f => fn (x,y) => f(x,y) is a function (where the second parameter is a pair)
hence its type must be of the form

  alpha -> (beta * gamma) -> delta 

where f:alpha, x:beta, y:gamma, and (f(x,y)):delta

Since f is applied to (x,y) and the result is of type delta, then it must be 

  alpha = (beta * gamma) -> delta 

hence the type is 

  ((beta * gamma) -> delta) -> (beta * gamma) -> delta 

(the parentheses around (beta * gamma) are not necessary because * has
priority wrt ->)

==============================================================================
3. 
fn f => fn x => fn y => (f x,f y) is a function hence its type must be of form

  alpha -> beta -> gamma -> delta

where f:alpha, x:beta, y:gamma, and (f x, f y):delta

Now, since the result is a pair, we must have delta = phi * psi, where 
(f x):phi and (f y):psi. Since f is applied to x and to y, we must have 
alpha = beta -> phi, and also alpha = gamma -> psi. Hence we obtain 
beta = gamma, and phi = psi. Thus the type is (again, names are not important):

  (beta -> phi) -> beta -> beta -> phi * phi
==============================================================================