4.5 Guarded Rules

Answers to Exercises, by David Rudel

Problem 1

••• Continue the development of recursive function theory by defining the following, using guards where it is helpful:

mod(M, N)

is the remainder after dividing M by N (use the convention that mod(M, 0) is 0. (In rex, mod(M, N) is available as M % N, also read “M modulo N”, or “M mod N”.)

div(M, N)

is the quotient obtained by dividing M by N (again with div(M, 0) defined to be 0). (In rex, div(M, N) is available as M / N.)

Problem 2

••• Show how Euclid's algorithm can be “sped up” if mod were available as a primitive function.

rex> gcd(0, Y) => Y;
gcd

rex> gcd(X, Y) => X <= Y ? gcd(mod(Y, X), X);
gcd

rex> gcd(X, Y) => gcd(Y, X);
gcd

These rules work precisely as those given in the text except that these subtract out all the X's possible from the Y in one command rather than going through [Y/X] command iterations to do so.