The only selfreferential data definitions we have seen thus far involved
cons
and lists of arbitrary length. We needed such data
definitions because the classes of lists that we wanted to process were of
arbitrary size. Natural numbers are another class of data whose elements
are of arbitrary size; after all, there is no limit on how large a natural
number can be, and, at least in principle, a function should be able to
process them all.
In this section, we study how to describe natural numbers with selfreferential data definitions and how to develop functions that process natural numbers in a systematic fashion. Since such functions come in many flavors, we study several different flavors of definitions.
People normally introduce natural numbers via enumeration: 0
,
1
, 2
, etc.^{34} The
abbreviation ``etc.'' at the end says that the series continues in this
manner. Mathematicians and mathematics teachers often use dots for the same
purpose. For us, however, neither the ``etc.'' nor the dots is good
enough, if we wish to design functions on natural numbers
systematically. So, the question is what it means to write down ``etc.,''
or put differently, what a complete, selfcontained description of the
natural numbers is.
The only way to remove the informal ``etc.'' from the enumeration is to describe the collection of numbers with a selfreferential description. Here is a first attempt:
0 is a natural number.While this description is still not quite rigorous,^{35} it is a good starting point for a Schemestyle data description:
If n is a natural number, then one more than n is one, too.
0
or
(add1 n)
if n
is a natural number.
The operation add1
adds 1
to a natural
number. Of course, we could use (+ ... 1)
but add1
stands out and signals ``natural number,'' as opposed to arbitrary number,
to the reader of a data definition and a function.
Although we are familiar with natural numbers from school, it is instructive to construct examples from the data definition. Clearly,
0
is the first natural number, so
(add1 0)
is the next one. From here, it is easy to see the pattern:
(add1 (add1 0)) (add1 (add1 (add1 0))) (add1 (add1 (add1 (add1 0))))
The examples should remind us of the lists construction process. We built
lists by starting with empty
and by cons
tructing on more
items. Now we build natural natural numbers by starting with 0
and
by add
ing on 1
. In addition, natural numbers come with
centuryold abbreviations. For example, (add1 0)
is abbreviated as
1
, (add1 (add1 0))
as 2
, and so on.
A function on natural numbers must extract the number that went into the
construction of a positive natural number just like a function on lists
must extract the list that went into a cons
tructed list. The
operation that performs this ``extraction'' is called sub1
. It
satisfies the law
(sub1 (add1 n)) = n
just as the rest
operation satisfies the law
(rest (cons avalue alist)) = alist
Of course, ( n 1)
would also work, but sub1
stands out
and signals that the function processes natural numbers.
Let us develop the function hellos
. It consumes a natural number
n
and produces a list of n
copies of 'hello
. We
can write the contract for this function:
;;hellos : N > listofsymbols
;; to create a list ofn
copies of'hello
(define (hellos n) ...)
And we can make up examples:
(hellos 0) ;; expected value: empty
(hellos 2) ;; expected value: (cons 'hello (cons 'hello empty))
The design of a template for hellos
follows the design recipe for
selfreferential data definitions. We immediately see that hellos
is a conditional function, that its condexpression has two
clauses, and that the first clause must distinguish 0
from other
possible inputs:
(define (hellos n) (cond [(zero? n) ...] [else ...]))
Furthermore, the data definition says that 0
is an atomic value,
and every other natural number is a compound value that ``contains'' the
predecessor to which 1
was added. Hence, if n
is not
0
, we subtract 1
from n
. The result is also a
natural number, so according to the design recipe we wrap the expression
with (hellos ...)
:
(define (hellos n) (cond [(zero? n) ...] [else ... (hellos (sub1 n)) ... ]))
Now we have exploited every hint in the data definition and are ready to proceed with the definition.
Assume (zero? n)
evaluates to true. Then the answer must be
empty
, as the examples illustrate. So assume the input is greater
than 0
. For concreteness, let us say it is 2
. According
to the suggestion in the template, hellos
should use
(hellos 1)
to compute a part of the answer. The purpose statement
specifies that (hellos 1)
produces (cons 'hello empty)
, a
list with one 'hello
. In general, (hellos (sub1 n))
produces a list that contains n  1 occurrences of 'hello
.
Clearly, to produce a list with n
occurrences, we must
cons
another 'hello
onto this list:
(define (hellos n) (cond [(zero? n) empty] [else (cons 'hello (hellos (sub1 n)))]))
As usual, the final definition is just the template with a few extras.
Let's test hellos
with some handevaluations:
(hellos 0) = (cond [(zero? 0) empty] [else (cons 'hello (hellos (sub1 0)))]) = (cond [true empty] [else (cons 'hello (hellos (sub1 0)))]) = empty
It confirms that hellos
works properly for the first example.
Here is another example:
(hellos 1)
= (cond
[(zero? 1) empty]
[else (cons 'hello (hellos (sub1 1)))])
= (cond
[false empty]
[else (cons 'hello (hellos (sub1 1)))])
= (cons 'hello (hellos (sub1 1)))
= (cons 'hello (hellos 0)
)
= (cons 'hello empty)
For the last step in the calculation, we can exploit that we already know
that (hellos 0)
evaluates to empty
and replace the
(underlined) expression with its result.
The last handevaluation shows that the function works for the second example:
(hellos 2)
= (cond
[(zero? 2) empty]
[else (cons 'hello (hellos (sub1 2)))])
= (cond
[false empty]
[else (cons 'hello (hellos (sub1 2)))])
= (cons 'hello (hellos (sub1 2)))
= (cons 'hello (hellos 1)
)
= (cons 'hello (cons 'hello empty))
We can again exploit what we know about (hellos 1)
, which greatly
shortens the handevaluation.
Exercise 11.2.1.
Generalize hellos
to repeat
, which consumes a natural
number n
and a symbol and produces a list with n
occurrences of the symbol.
Solution
Exercise 11.2.2.
Develop the function tabulatef
, which tabulates the values of
;; f : number > number
(define (f x)
(+ (* 3 (* x x))
(+ (* 6 x)
1)))
for some natural numbers. Specifically, it consumes a natural number
n
and produces a list of n
posn
s. The first one
combines n
with (f n)
, the second one n1
with
(f n1)
, etc.
Solution
Exercise 11.2.3.
Develop applyn
. The function consumes a natural number,
n
. It applies the function move
from
exercise 10.3.6 n
times to FACE
, the list of
shapes from exercise 10.3.1. Each application should
translate the shape by one pixel. The purpose of the function is to
simulate a continuously moving shape on a canvas, the last missing piece of
the extended exercise 10.3.
Solution
Exercise 11.2.4. Lists may contain lists that contain lists and so on. Here is a data definition that takes this idea to an extreme:
s
where s
is some symbol or
(cons dl empty)
, where dl
is a deep list.
Develop the function depth
, which consumes a deep list and
determines how many times cons
was used to construct it.
Develop the function makedeep
, which consumes a symbol
s
and a natural number and produces a deep list containing
s
and cons
tructed with n
cons
es.
Solution
We often encounter situations where we would like to create lists of data
that involve numbers. For example, we may wish to create large lists of
numbers to test a function like extract1
in
section 10.2 on large lists instead of handcoded small
ones. Sometimes we would like to visualize randomly picked data. We can
create such functions using recursion on natural numbers and a
random number generator.
Exercise 11.3.1.
Scheme provides the operation random
. It consumes a natural number
n
greater than 1, and produces a random integer between 0
and n  1
:
;;random : N > N
;; to compute a natural number between0
andn1
(define (random n) ...)
Two successive uses of (random n)
may produce two distinct results.
Now consider the following definition:
;; randomnm : integer integer > integer
;; ...
;; Assume: n < m
(define (randomnm n m)
(+ (random ( m n)) n))
Formulate a succinct and precise purpose statement for randomnm
.
Use a number line with an interval to explain the result of (random
n)
. Use a symbolic evaluation to support your
explanation.
Solution
Exercise 11.3.2.
Develop the function tiedyed
. It consumes a natural number and
produces a list of that many numbers, each randomly chosen in the range
from 20
and 120
. Use tiedyed
to apply
drawcircles
from
exercise 9.5.8.
Solution
Exercise 11.3.3.
Develop the function createtemps
. It consumes a natural number
n
and two integers, called low
and high
. It
produces a list of n
integers that are between low
and
high
.
Use createtemps
to test checkrange
from
exercise 9.5.4.
Finally, discuss the following questions. Can we simply feed the result of
createtemps
into checkrange
or do we need to know the
list that createtemps
produced? Are there values for low
and high
such that we don't need to know the result of
createtemps
and yet we can predict the result of the test? Which
function tests which? What does this tell us about testing with
automatically generated test data?
Solution
Exercise 11.3.4.
Develop the function createprices
, which consumes a natural
number and produces a list with a corresponding number of prices between
$.10 and $10.00 with increments of a dime. Use createprices
to
test dollarstore?
from exercise 9.5.3.
Hint: How many dimes are there between $.10 and $10.00? Solution
Exercise 11.3.5.
Develop a program that visualizes a student riot. In preparation of a
student riot, a small group of students meets to make paintfilled
balloons. The typical riot uses 'red
only. Then, on the evening of
the riot, the students enter a university's progressive theater with the
balloons and throw them all over the seats.
The program's only input should be a natural number, which represents the number of balloons thrown. The visualization should use a canvas that contains a black grid and the positions of the balls:
Assume a random distribution of the balls over the theater's seats. Each box in the grid represents a seat. Configure the program so the change of one variable definition changes the number of columns in the grid and a change to another changes the number of rows.
Hint: Develop auxiliary functions that draw some given number of lines in the vertical and the horizontal direction. Solution
Using the above, standard data definition for natural numbers makes it
easy to develop all kinds of functions on numbers. Consider, for example,
a function that multiplies the first n
numbers. Put differently,
it consumes a natural number n
and multiplies all numbers
between 0
(exclusive) and n
(inclusive). The function
is called factorial and has the mathematical notation !
. Its
contract is easy to formulate:
;; ! : N > N
;; to compute n · (n  1) · ... · 2 · 1
(define (! n) ...)
It consumes a natural number and produces one.
Specifying its inputoutput relationship is a bit more tricky. We
know, of course, what the product of 1
, 2
, and
3
is, so we should have
(= (! 3) 6) and, similarly, (= (! 10) 3628800)
The real question is what to do with the input 0
. According to the
informal description of the task, !
is supposed to produce the
product of all numbers between 0
(exclusive) and n
(inclusive), the argument. Since n
is 0
, this request is
rather strange because there are no numbers between 0
(exclusive)
and 0
(inclusive). We solve the problem by following mathematical
convention and set that (! 0)
evaluates to 1
.
From here, the rest is straightforward. The template for !
is clearly that of a natural number processing function:
(define (! n) (cond [(zero? n) ...] [else ... (! (sub1 n)) ...]))
The answer in the first cond
clause is given: 1
. In the
second clause, the recursion produces the product of the first n 
1
numbers. To get the product of the first n
numbers, we just
need to multiply the (value of the) recursion by
n
. Figure 31 contains the complete definition of
!
.
Exercise 11.4.1.
Determine the value of (! 2)
by hand and with DrScheme.
Also test !
with 10
, 100
, and 1000
.
Note: The results of these expressions are large numbers, well beyond the native capacities of many other programming languages. Solution
Now suppose we wish to design the function productfrom20
, which computes the
product from 20
(exclusive) to some number n
(inclusive)
that is greater or equal to 20
. We have several choices
here. First, we could define a function that computes (! n)
and
(! 20)
and divides the former by the latter. A simple mathematical
argument shows that this approach indeed yields the product of all numbers
between 20
(exclusive) and n
(inclusive):
Exercise 11.4.2.
Use the idea to define product
, a function that consumes two natural
numbers, n
and m
, with m > n
, and that produces
the product of the numbers between n
(exclusive) and m
(inclusive).
Solution
Second, we can follow our design recipe, starting with a precise
characterization of the function's input. Obviously, the inputs belong to
the natural numbers, but we know more than that. It belongs to the following
collection of numbers: 20
, 21
, 22
, .... By now
we know how to describe such a set precisely with a data definition:
A natural number [>= 20]
is either
20
or
(add1 n)
if n
is a natural number [>= 20]
.
Notation: In contracts, we use N [>= 20]
instead of ``natural numbers [>= 20]
.''
Using the new data definition, we can formulate a contract for
productfrom20
:
;; productfrom20: N [>= 20] > N
;; to compute n · (n  1) · ... · 21 · 1
(define (productfrom20 nabove20) ...)
Here is a first example for productfrom20
's inputoutput specification:
(= (productfrom20 21) 21)
Since the function multiplies all numbers between 20
(exclusively)
and its input, (productfrom20 21)
must produce 21
,
which is the only number in the interval. Similarly,
(= (productfrom20 22) 462)
for the same reason. Finally, we again follow mathematical convention and agree that
(= (productfrom20 20) 1)
The template for productfrom20
is a straightforward adaptation of the
template for !
, or any natural numberprocessing function:
(define (productfrom20 nabove20) (cond [(= nabove20 20) ...] [else ... (productfrom20 (sub1 nabove20)) ...]))
The input nabove20
is either 20
or larger. If it is
20
, it does not have any components according to the data
definition. Otherwise, it is the result of adding 1
to a
natural number [>= 20]
, and we can recover this ``component'' by
subtracting 1
. The value of this selector expression belongs to
the same class of data as the input and is thus a candidate for natural
recursion.
Completing the template is equally straightforward. As specified, the
result of (productfrom20 20)
is 1
, which determines the
answer for the first cond
clause. Otherwise,
(productfrom20 (sub1 nabove20))
already produces the product
of all the numbers between 20
(exclusive) and nabove20 
1
. The only number not included in this range is
nabove20
. Hence (* nabove20 (productfrom20 (sub1
nabove20)))
is the correct answer in the second
clause. Figure 31 contains the complete definition of
productfrom20
.
Exercise 11.4.3.
Develop productfromminus11
. The function consumes an integer
n
greater or equal to 11
and produces the product of all
the integers between 11
(exclusive) and n
(inclusive).
Solution
Exercise 11.4.4.
In exercise 11.2.2, we developed a function that
tabulates some mathematical function f
for an interval
of the shape (0,n].
Develop the function tabulatef20
, which tabulates the values of
f
for natural numbers greater than 20
. Specifically,
the function consumes a natural number n
greater or equal to
20
and produces a list of posn
s, each of which has the
shape (makeposn n (f n))
for some n
between
20
(exclusive) and n
(inclusive).
Solution
A comparison of !
and productfrom20
suggests the
natural question of how to design a function that multiplies all
natural numbers in some range. Roughly speaking, product
is like
productfrom20
except that the limit is not a part of the function
definition. Instead, it is another input, which suggests the following
contract:
;; product: N N > N
;; to compute n · (n  1) · ... · (limit + 1) · 1
(define (product limit n) ...)
The intention is that product
, like productfrom20
, computes the
product from limit
(exclusive) to some number n
(inclusive) that is greater or equal to limit
.
Unfortunately, product
's contract, in contrast with
productfrom20
's, is rather imprecise. In particular, it does not
describe the collection of numbers that product
consumes as the
second input. Given its first input, limit
, we know that the
second input belongs to limit
, (add1 limit)
,
(add1 (add1 limit))
, etc. While it is easy to enumerate
the possible second inputs, it also shows that the description of the
collection depends on the first input  an unusal situation that we
have not encountered before.
Still, if we assume limit is some number, the data description for the second input is nearly obvious:
Let limit
be a natural number. A natural
number [>= limit]
(N[>=limit]
) is either
limit
or
(add1 n)
if n
is a natural number [>= limit]
.
In other words, the data definition is like that for natural numbers
[>= limit]
with 20
replaced by a variable
limit
. Of course, in high school, we refer to
N[>=0]
as the natural numbers, and
N[>=1]
as the positive integers.
With this new data definition, we specify the contract for product
as follows:
;; product: N[limit] N [>= limit] > N
;; to compute n · (n  1) · ... · (limit + 1) · 1
(define (product limit n) ...)
That is, we name the first input, a natural number, with the notation
[limit]
and specify the second input using the name for the
first one.
The rest of the program development is straightforward. It is basically
the same as that for productfrom20
with 20
replaced by
limit
throughout. The only modification concerns the natural
recusion in the function template. Since the function consumes a
limit
and a N [>= limit]
, the template
must contain an application of product
to limit
and
(sub1 n)
:
(define (product limit n) (cond [(= n limit) ...] [else ... (product limit (sub1 n)) ...]))
Otherwise things remain the same. The full function definition is contained in figure 31.
Exercise 11.4.5.
In exercises 11.2.2 and 11.4.4, we developed
functions that tabulate f
from some natural number or natural
number [>= 20]
down to 0
or 20
(exclusive),
respectively.
Develop the function tabulateflim
, which tabulates the values of
f
in an analogous manner from some natural number n
down to some other natural number limit
.
Solution
Exercise 11.4.6.
In exercises 11.2.2, 11.4.4,
and 11.4.5, we developed
functions that tabulate the mathematical function f
in various
ranges. In both cases, the final function produced a list of posn
s
that was ordered in descending order. That is, an expression like
(tabulatef 3)
yields the list
(cons (makeposn 3 2.4) (cons (makeposn 2 3.4) (cons (makeposn 1 3.6) (cons (makeposn 0 3.0) empty))))
If we prefer a list of posn
s in ascending order, we
must look at a different data collection, natural numbers up to a
certain point in the chain:
A natural number [<= 20]
(N[<=20]
)
is either
20
or
(sub1 n)
if n
is a natural number [<= 20]
.
Of course, in high school, we refer to N[<=1]
as the negative integers.
;; tabulatefupto20 : N [<= 20] > N
(define (tabulatefupto20 nbelow20) ...)
which tabulates the values of f
for natural numbers less than
20
. Specifically, it consumes a natural number n
less
than or equal to 20
and produces a list of posn
s, each of
which has the shape (makeposn n (f n))
for some n
between 0
and n
(inclusively).
Solution
Exercise 11.4.7.
Develop the function isnotdivisibleby<=i
. It consumes a
natural number [>= 1]
, i
, and a natural number
m
, with i < m
. If m
is not divisible by any
number between 1
(exclusive) and i
(inclusive), the
function produces true
; otherwise, its output is false
.
Use isnotdivisibleby<=i
to define prime?
, which
consumes a natural number and determines whether or not it is prime.
Solution
The natural numbers are a small subset of Scheme's numbers, not all of
them. Hence the function template above cannot be used for
processing arbitrary numbers, in particular, inexact numbers. Still, the template is
a good starting point for functions whose definitions involve both natural
numbers and other Scheme numbers. To illustrate this point, let us design
the function addtopi
, which consumes a natural number n
and produces n + 3.14
without using +
.
Following the design recipe, we start with
;;addtopi : N > number
;; to compute n + 3.14 without using+
(define (addtopi n) ...)
Another easy step is to determine the output for a few sample inputs:
(= (addtopi 0) 3.14) (= (addtopi 2) 5.14) (= (addtopi 6) 9.14)
The difference between hellos
's contract (see exercise 11.2.1)
and that of addtopi
is the output, but as we have seen this
does not affect the template design. We obtain the template for
addtopi
by renaming hellos
appropriately:
(define (addtopi n) (cond [(zero? n) ...] [else ... (addtopi (sub1 n)) ... ])))
In combination with the examples, the template immediately suggests how to
complete the function. If the input is 0
, addtopi
's
answer is 3.14
. Otherwise, (addtopi (sub1 n))
produces ( n 1) + 3.14
; since the correct answer is 1
more than this value, the answer expression in the second
cond
line is (add1 (addtopi (sub1 n)))
. Figure 32 contains the complete function definition.
Exercise 11.5.1.
Define add
, which consumes two natural numbers, n
and
x
, and produces n + x
without using Scheme's
+
.
Solution
Exercise 11.5.2.
Develop the function multiplybypi
, which consumes a natural
number and multiplies it by 3.14
without using *
. For
example,
(= (multiplybypi 0) 0) (= (multiplybypi 2) 6.28) (= (multiplybypi 3) 9.42)
Define multiply
, which consumes two natural numbers, n
and x
, and produces n * x
without using Scheme's
*
. Eliminate +
from this definition, too.
Hint: Recall that multiplying x
by n
means adding
x
to itself n
times.
Solution
Exercise 11.5.3.
Develop the function exponent
, which consumes a natural number
n
and a number x
and computes
Eliminate
*
from this definition, too.
Hint: Recall that exponentiating x
by n
means multiplying
x
with itself n
times.
Solution
Exercise 11.5.4.
Deep lists (see exercise 11.2.4) are another representation for
natural numbers. Show how to represent 0
, 3
, and
8
.
Develop the function addDL
, which consumes two deep lists,
representing the natural numbers n
and m
, and produces a
deep list representing n + m
.
Solution
