Description
1. Let f and g be two functions taking numbers to numbers. We define mf g to be the function so that
mf g (x) = the larger of f (x) and g(x).
For example, if f (x) = x and g(x) = −x then mf g is the absolute value function. Define a function max
which takes a pair of functions, f and g, as an argument and returns the function mf g as its value. (So the
return value is a function: the function which, at every point x, returns the larger value of f (x) and g(x).)
2. Define a SCHEME function, zip, which takes as arguments two lists (a1
. . . an
) and (b1
. . . bn
) of the same
length, and produces the list of pairs ((a1
.b1
). . .(an
.bn
)).
3. Define a SCHEME function, unzip, which takes a list of pairs ((a1
.b1
). . .(an
.bn
)) and returns a pair consisting of the two lists (a1
. . . an
) and (b1
. . . bn
).
(Note that these functions are not exactly inverses of each other, since zip takes its lists as a two arguments,
while unzip produces a pair of lists.)
4. Consider the problem of making change. Given a list of “denominations” (d1d2
. . . dk
) and a positive integer
n, the problem is to determine the number of ways that n can be written as a sum of the di
. For example,
if we consider the denominations used for US coins, (1 5 10 25), the number 11 can be written in 4 ways:
10 + 1, 5 + 5 + 1, 5 + 1 + ··· + 1
| {z }
6
, and 1 + ··· + 1
| {z }
11
.
Note that we do not consider 10+1 and 1+10 as “different” ways to write 11: all that matters is the number
of occurrences of each denomination, not their order.
Write a SCHEME function (change k `) that returns the number of ways to express k as a sum of the
denominations appearing in the list `.
(Hint: There is a nice recursive decomposition of this problem: Let C(n, `) denote the number of ways to
express n as a sum of elements from the list ` = (`1`2
. . . `k
). We can mentally divide the different ways to do
this into two types: those that do not use the denomination `1 and those that do. There are C(n,(`2
. . . , `k
))
ways that do not use the denomination `1
. There are C(n−`1
, `) ways that involve at least one `1
. It follows
that
C(n, `) = C(n,(`2
. . . , `k
)) + C(n − `1
, `),
which you can use in your definition. (To do this, make sure you understand what happens, e.g., when n is
smaller than all of the elements in `.)
5. (The Cantor pairing function.) A pairing function p is a function that places the natural numbers N =
{0, 1, 2, . . .} into one-to-one correspondence with the set of all pairs of natural numbers (usually denoted
N × N). It is somewhat surprising that such a function should exist at all: it shows that the set of natural
numbers has the same “size” as the set of all pairs of natural numbers. To be more precise, a pairing function
p takes two natural numbers x and y as arguments and returns a single number z with the property that
the original pair can always be determined exactly from the value z. (In particular, the function maps no
more than one pair to any particular natural number.)
One famous pairing function is the following:
p(x, y) = 1
2
(x + y)(x + y + 1) + y .
1
(a) Write a SCHEME function encode that computes the pairing function above. (It should take a pair of
numbers as arguments and return a single number.)
(b) As mentioned above, this function has the property that if (x, y) 6= (x
0
, y
0
) then p(x, y) 6= p(x
0
, y
0
):
it follows that, in principle, the pair (x, y) can be reconstructed from the single value z = p(x, y). In
fact, the values x and y can be reconstructed from z = p(x, y) by first computing the quantities
w =
p
8z + 1 − 1
2
, and
t =
w
2 + w
2
.
Then y = z − t and x = w − y.
Write a SCHEME function decode that takes as an argument an integer z and produces the pair (x, y)
for which p(x, y) = z. You’ll need the floor function: (floor x) returns the largest integer less
than or equal to x (that is, it rounds x down to the nearest integer).
Hint: You may wish to use the let* form for this problem. let* has the form
(let* ((x1
(x2
…
(xk
The form is a simple method for writing “nested lets.” It is evaluated, informally, as follows. Starting
with the external environment, expr1 is evaluated and the variable x1 is immediately bound to the resulting value. Following this,
bound to the value. This continues for the remaining variable/expression pairs. Finally,
is evaluated in the resulting environment and its value is returned. Note, for example, that x1 may
appear in
external environment.)
6. Write a SCHEME function positives which takes a list—call it `—as an argument and returns a list consisting of all elements of ` that are positive. In particular, once you have positives defined correctly, you
should be able to reproduce the following behavior.
> ( positives ( list -2 -1 0 1 2))
’(1 2)
> ( positives ( list 2 1 0 -2 -1))
’(2 1)
> ( positives ’(3 1 -1 1 -1))
’(3 1 1)
To keep things simple, it’s fine if your function just removes from the list all numbers that are zero or less
(leaving duplicates in the remaining list, as shown above).
7. Write a SCHEME function that removes all duplicates from a list. (Hint: you might start by defining a
function which removes all duplicates of a particular given value v from a list; then what?)
2
