Answers to Exercises for Chapter 2

**2.1.** The command for invoking ML is operating-system dependent. Most compilers offer the *use* command, but it is not part of the language.

**2.2.** Advantages of a single type of numbers: eliminates overloaded operators; fewer concepts to remember. Disadvantages: confuses (exact) integers with (inexact) reals; type conversions at run time may be unpredictable; probably less efficient at run-time.

**2.3.** Only *g* needs one, since `~` and `*` are both overloaded for types int and real. The constant 2 constrains the type of *double* while *Math.sin* constrains that of *f*.

Now that ML supports default overloading, even the declaration of *g* is accepted. It is assumed to use type *int*.

**2.4.** The first version returns `#"/"` and `#":"`, which are the characters just outside the range of digits in the ASCII character set. The second version reports an error, by raising exception *Subscript*.

**2.5.**

1<=d andalso (m = "January" andalso d<=31 orelse m = "February" andalso d<=28 orelse m = "March" andalso d<=31 orelse m = "April" andalso d<=30 orelse m = "May" andalso d<=31 orelse m = "June" andalso d<=30 orelse m = "July" andalso d<=31 orelse m = "August" andalso d<=31 orelse m = "September" andalso d<=30 orelse m = "October" andalso d<=31 orelse m = "November" andalso d<=30 orelse m = "December" andalso d<=31)

**2.6.** This is just lexicographic ordering on triples.

fun earlier ((h1, m1, apm1), (h2:int, m2:int, apm2)) = apm1 = "AM" andalso apm2 = "PM" orelse apm1=apm2 andalso (h1<h2 orelse h1=h2 andalso m1<m2);

**2.7.** Variable *l* stands for pounds and *d* stands for pence.

fun quorem (m,n) = (m div n, m mod n); fun addMoney ((l1,s1,d1), (l2,s2,d2)) = let val (dcarry,d) = quorem(d1 + d2, 12) val (scarry,s) = quorem(dcarry + s1 + s2, 20) in (scarry + l1 + l2, s, d) end;

Tom Maynard points out that this solution uses `let`, which has not been introduced yet. Here is an alternative definition of *addMoney*:

fun addPounds (l1, l2, (scarry, s), d) = (scarry + l1 + l2, s, d); fun addShillings (l1, l2, s1, s2, (dcarry,d)) = addPounds (l1, l2, quorem(dcarry + s1 + s2, 20), d); fun addMoney ((l1,s1,d1), (l2,s2,d2)) = addShillings (l1, l2, s1, s2, quorem(d1 + d2, 12));

2.8.A type constraint is required because - is overloaded:

fun lifetime({name,born,died,quote,crowned}) : int = died - born;

Its type is `{born:int,crowned:'a,died:int,name:'b,quote:'c} -> int`.

The declaration does not constrain the other fields; their types are polymorphic.

**2.9.** The selector *#born* applies to any record containing the field *born*. Function *born_at* applies to records that contain just that field and no others.

**2.10.** The reduction steps for `powoftwo(8)` are

powoftwo(8) ==> (8=1) orelse (even(8) andalso ...) ==> even(8) andalso powoftwo(8 div 2) ==> powoftwo(4) ==> (4=1) orelse (even(4) andalso ...) ==> even(4) andalso powoftwo(4 div 2) ==> powoftwo(2) ==> (2=1) orelse (even(2) andalso ...) ==> even(2) andalso powoftwo(2 div 2) ==> powoftwo(1) ==> (1=1) orelse (even(1) andalso ...) ==> true

**2.11.** Yes, as shown by the reduction steps. This is because `andalso` and `orelse` are conditional operators rather than functions.

**2.12.** The reduction steps for `power(2,29)`, ignoring the k=1 test, are

power(2,29) ==> if 29 mod 2 = 0 then ... else ... ==> 2 * power(2*2, 29 div 2) ==> 2 * power(4,14) ==> 2 * (if 14 mod 2 = 0 then ... else ...) ==> 2 * (power(4*4, 14 div 2)) ==> 2 * (power(16,7)) ==> 2 * (if 7 mod 2 = 0 then ... else ...) ==> 2 * (16 * power(16*16, 7 div 2)) ==> 2 * (16 * power(256,3)) ==> 2 * (16 * (if 3 mod 2 = 0 then ... else ...)) ==> 2 * (16 * (256 * power(256*256, 3 div 2))) ==> 2 * (16 * (256 * power(65536, 1))) ==> 2 * (16 * (256 * 65536)) ==> 536870912

Real numbers are written without the trailing .0 to avoid clutter.

**2.13.** The worst case is when k has the form 2^n-1, for n>0. Then k remains odd in all the recursive calls and 2n-2 multiplications are performed.

**2.14.** Function power could start with "if k=0 then 1.0...", but the last recursive call would always be x*power(x*x,0), reducing to x. Two needless multiplications would be performed, of which x*x could easily cause overflow. An exponentiation function should handle zero and negative exponents, calling power only for positive k.

**2.15.** Both computations result in repeated function evaluations, but for different reasons. Lazy evaluation does not help. Memo functions, which store previous results, can compute factorial efficiently.

**2.16.** For "steps", count the number of calls to F. It's easy to check that F(0) and F(1) involves one call, and that F(n+2)=F(n)+(F(n-1)+F(n)), so F(n+2) involves more than twice as many calls as F(n). By induction, F(2n) makes at least 2^n calls. Thus F(n) makes at least sqrt(2)^n calls. But fib(n) makes just n calls of itfib.

**2.17.** itfib(n,F(k-1),F(k)) = F(k+n-1). See page 222 for the proof.

**2.18.** This is a challenge rather than an exercise. I do not know of any easy solution, which is precisely the point. David Eger contributes this solution, using an explicit stack to handle the recursion.

int introot(int n) { int rf, stack[20]; for(rf=0; stack[rf] = n; rf++, n=n/4) {} while(rf-->0) { if( (2*stack[rf+1]+1)*(2*stack[rf+1]+1) > stack[rf] ) stack[rf] = 2*stack[rf+1]; else stack[rf] = 2*stack[rf+1]+1; } return stack[0]; }

Michael Winking contributes this solution.

uint64_t increase(uint64_t k, uint64_t n) { return (k+1) * (k+1) > n ? k : k + 1; } uint64_t introot(uint64_t n) { int m; uint64_t k; for(m = 0, k = n; k; m += 2, k >>= 2) {} for(k = 0; m != 0; m -= 2, k = increase(2 * k, n >> m)) {} return k; }

**2.19.** This exercise is from Hoare (1987), page 380, who remarks that experts in complexity theory do not know whether this is the best GCD algorithm. It is certainly longer to code than Euclid's Algorithm. To ensure termination, both arguments must be positive.

fun GCD(m,n) = if m=n then m else if m mod 2 = 0 then if n mod 2 = 0 then 2 * GCD(m div 2, n div 2) else GCD(m div 2, n) else (*m odd*) if n mod 2 = 0 then GCD(m, n div 2) else (*both odd*) if m<n then GCD((n-m) div 2, m) else GCD((m-n) div 2, n);

**2.20.** Nested function declarations can be harder to read. But if they refer to identifiers declared in the local context, they can make do with fewer parameters. The nested function *findroot* refers to *sqroot*'s argument. Nesting *itfib* within *fib* would only introduce confusion between the two variables called *n*.

**2.21.**

fun introotpair n = if n<4 then (1,n-1) else let val (e,re) = introotpair(n div 4) val ri = 4*re + n mod 4 (*remainder if root=2*k*) val rj = ri - (4*e + 1) (*remainder if root=2*k+1*) in if rj<0 then (2*e, ri) else (2*e+1, rj) end;

**2.22.** This exchanges the bindings of *pi* and *log2*. It is equivalent to

val pi=log2 and log2=pi;

**2.23.** We can express P using the mutual recursion as follows:

fun P n = 1 + sumup(n-1) and sumup k = if k<1 then 0 else P(k) + sumup(k-1);

This version is exponential, by similar reasoning as in exercise 2.16. But it is easy to verify by induction that P(n) = 2^(n-1), which gives faster ways of computing it.

**2.24.** Please note that the Basis Library provides an entirely different structure of the same name!

structure Real : ARITH = struct type t = real; val zero = 0.0; fun sum (x,y) = x+y: t; fun diff (x,y) = x-y: t; fun prod (x,y) = x*y: t; fun quo (x,y) = x/y: t; end;

**2.25.** (Correction by Ralf Steinbrueggen.)

structure Rational : ARITH = struct type t = int*int; val zero = (0, 1); fun gcd(m,n) = if m=0 then n else gcd(n mod m, m); fun canon (m,n) = let val d = gcd(abs m, n) in (m div d, n div d) end fun sum ((m,n), (m',n')) = canon(m*n' + m'*n, n*n'); fun diff ((m,n), (m',n')) = canon(m*n' - m'*n, n*n'); fun prod ((m,n), (m',n')) = canon(m*m', n*n'); fun recip (m,n): t = if m<0 then (~n,~m) else (n,m) fun quo (x,x') = prod(x, recip x'); end;

**2.26.** The constant 1 has type *int*, so n-1 means integer subtraction and n has type *int*. The result type of *itfib* is given as *int* by the type constraint; since curr is returns as the result, curr has type *int*. Therefore prev+curr means integer addition and prev has type *int*. Finally, all types agree in the recursive call and the conditional.

**2.27.** Type checking fails because *f*'s argument pattern is a pair, whose type must have the form T1*T2; but *f* is called with an argument of type *int*.

Last modified 31 March, 2008

Back to Exercises page