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;