1. (a)
------
fact(4) = 4 * fact(3)
        = 4 * 3 * fact(2)
        = 4 * 3 * 2 * fact(1)
        = 4 * 3 * 2 * 1 * fact(0)
        = 4 * 3 * 2 * 1 * 1
        = 4 * 3 * 2 * 1
        = 4 * 3 * 2
        = 4 * 6
        = 24

Due to the recursive nature of factorial we "stack up" pending
actions, in this case multiplications. Therefore, for each
recursive call to fact, we must record a deferred
multiplication. Note: the multiplication is deferred because we
do not have the evaluated operands until recursion terminates.
The computation of fact n will require space proportional to n, 
and will require n stacking/unstacking operations.


1. (b)
------

       fun ifact (0,r) = (0,r)
          |ifact (n,r) = ifact(n-1,n*r);

       fun fact n = ifact(n,1);

The above definition is "tail recursive", essentially iterative.
In function ifact (iterative factorial) we can evaluate the
arguments before making the next recursive call. Therefore we do
not need to stack up arguments, as there are no deferred
arguments. The space requireds by this (iterative) definition of
factorial is constant. The principle we have employed is
iteration. We have recognised that recursion in fact was tail
recursion (no follow on actions after the recursive call)
therefore we can map into the (less elegant but more efficient) 
iterative form.



   (c) You are given a family tree, composed of persons, where a
       person has a name and a list of immediate descendants.

        datatype 'a person = empty | Person of ('a * 'a person list)

       (i)   Write a function in ML, called find, that takes as arguments 
             the name of a person and a list of Person's. The function 
             delivers as a result the corresponding person, or empty. 

1. (c) (i)
----------

     fun find sname [] = empty
        |find sname (first::rest) =
          let val Person(name,children) = first
          in if sname = name 
             then first
             else find sname (rest @ children) end; << *** >>

        (iii) Give an informal assessment of function find,
              stating the assumptions you have made, and the 
              computational costs (space and time) associated 
              with that function.

1. (c) (ii)
-----------
Function find assumes that the family tree is in fact a tree. That is, 
there are no loops, no one is their own ancestor. If that was
the case then find might not terminate, if we employ a depth
first search. As given above, we have breadth first search. 
We may make the function go depth first by changing the
recursive call in << *** >> to be

             find sname (children @ rest) 

By going breadth first I hope to find the person as early as
possible. However I must maintain a list of all persons at that
depth in the family tree. If, on average, each person has B
descendants, then at depth N find will consume space
proportional to B**N (B to the power N). If I go depth first,
find will require space of the order N*B (at depth N in the
family tree). However, depth first will tend to explore many
useless paths, but at the family gets larger we may have no
other choice (due to space limits).


1. (c) (iii)
------------

fun ancestorp aname bname family =
    let val a = find aname family
    in if a = empty
       then false
       else let val b = find bname [a]
            in if b = empty 
               then false
               else true end end;