Section 11

Natural Numbers

The only self-referential 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 self-referential 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.

11.1 Defining Natural Numbers

People normally introduce natural numbers via enumeration: 0, 1, 2, etc.³⁴ 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, self-contained 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 self-referential description. Here is a first attempt:

0 is a natural number.
If n is a natural number, then one more than n is one, too.

While this description is still not quite rigorous,³⁵ it is a good starting point for a Scheme-style data description:

A natural-number is either

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,

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 constructing on more items. Now we build natural natural numbers by starting with 0 and by adding on 1. In addition, natural numbers come with century-old 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 constructed 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 a-value a-list)) = a-list

Of course, (- n 1) would also work, but sub1 stands out and signals that the function processes natural numbers.

11.2 Processing Natural Numbers of Arbitrary Size

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  ->  list-of-symbols
;; to create a list of n 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 self-referential data definitions. We immediately see that hellos is a conditional function, that its cond-expression 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 hand-evaluations:

  (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 hand-evaluation 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 hand-evaluation.

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 tabulate-f, 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 posns. The first one combines n with (f n), the second one n-1 with (f n-1), etc. Solution

Exercise 11.2.3. Develop apply-n. 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:

A deep-list is either

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 make-deep, which consumes a symbol s and a natural number and produces a deep list containing s and constructed with n conses. Solution

11.3 Extended Exercise: Creating Lists, Testing Functions

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 hand-coded 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 between 0 and n-1
(define (random n) ...)

Two successive uses of (random n) may produce two distinct results.

Now consider the following definition:

;; random-n-m : integer integer  ->  integer
;; ... 
;; Assume: n < m
(define (random-n-m n m)
  (+ (random (- m n)) n))

Formulate a succinct and precise purpose statement for random-n-m. 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 tie-dyed. It consumes a natural number and produces a list of that many numbers, each randomly chosen in the range from 20 and 120. Use tie-dyed to apply draw-circles from exercise 9.5.8. Solution

Exercise 11.3.3. Develop the function create-temps. 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 create-temps to test check-range from exercise 9.5.4.

Finally, discuss the following questions. Can we simply feed the result of create-temps into check-range or do we need to know the list that create-temps produced? Are there values for low and high such that we don't need to know the result of create-temps 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 create-prices, 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 create-prices to test dollar-store? 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 paint-filled 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

11.4 Alternative Data Definitions for Natural Numbers

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 input-output 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 product-from-20, 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 product-from-20:

;; product-from-20: N [>= 20]  ->  N
;; to compute n  ·  (n - 1)  ·  ...  ·  21  ·  1
(define (product-from-20 n-above-20) ...)

Here is a first example for product-from-20's input-output specification:

(= (product-from-20 21)
   21)

Since the function multiplies all numbers between 20 (exclusively) and its input, (product-from-20 21) must produce 21, which is the only number in the interval. Similarly,

(= (product-from-20 22)
   462)

for the same reason. Finally, we again follow mathematical convention and agree that

(= (product-from-20 20)
   1)

The template for product-from-20 is a straightforward adaptation of the template for !, or any natural number-processing function:

(define (product-from-20 n-above-20)
  (cond
    [(= n-above-20 20) ...]
    [else ... (product-from-20 (sub1 n-above-20)) ...]))

The input n-above-20 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 (product-from-20 20) is 1, which determines the answer for the first cond-clause. Otherwise, (product-from-20 (sub1 n-above-20)) already produces the product of all the numbers between 20 (exclusive) and n-above-20 - 1. The only number not included in this range is n-above-20. Hence (* n-above-20 (product-from-20 (sub1 n-above-20))) is the correct answer in the second clause. Figure 31 contains the complete definition of product-from-20.

Exercise 11.4.3. Develop product-from-minus-11. 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 tabulate-f20, 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 posns, each of which has the shape (make-posn n (f n)) for some n between 20 (exclusive) and n (inclusive). Solution

;; ! : N  ->  N
;; to compute n  ·  (n - 1)  ·  ...  ·  2  ·  1
(define (! n)
  (cond
    [(zero? n) 1]
    [else (* n (! (sub1 n)))]))

;; product-from-20: N [>= 20]  ->  N
;; to compute n  ·  (n - 1)  ·  ...  ·  21  ·  1
(define (product-from-20 n-above-20)
  (cond
    [(= n-above-20 20) 1]
    [else (* n-above-20 (product-from-20 (sub1 n-above-20)))]))

;; product: N[limit] N[>= limit]  ->  N
;; to compute n  ·  (n - 1)  ·  ...  ·  (limit + 1)  ·  1
(define (product limit n)
  (cond
    [(= n limit) 1]
    [else (* n (product limit (sub1 n)))]))

Figure 31: Computing factorial, product-from-20, and product

A comparison of ! and product-from-20 suggests the natural question of how to design a function that multiplies all natural numbers in some range. Roughly speaking, product is like product-from-20 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 product-from-20, 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 product-from-20'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 product-from-20 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 tabulate-f-lim, 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 posns that was ordered in descending order. That is, an expression like (tabulate-f 3) yields the list

(cons (make-posn 3 2.4)
  (cons (make-posn 2 3.4)
    (cons (make-posn 1 3.6)
      (cons (make-posn 0 3.0)
        empty))))

If we prefer a list of posns 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.

Develop the function

;; tabulate-f-up-to-20 : N [<= 20]  ->  N
(define (tabulate-f-up-to-20 n-below-20) ...)

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 posns, each of which has the shape (make-posn n (f n)) for some n between 0 and n (inclusively). Solution

Exercise 11.4.7. Develop the function is-not-divisible-by<=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 is-not-divisible-by<=i to define prime?, which consumes a natural number and determines whether or not it is prime. Solution

11.5 More on the Nature of Natural Numbers

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 add-to-pi, which consumes a natural number n and produces n + 3.14 without using +.

Following the design recipe, we start with

;; add-to-pi : N  ->  number
;; to compute n + 3.14 without using +
(define (add-to-pi n) ...)

Another easy step is to determine the output for a few sample inputs:

(= (add-to-pi 0) 3.14)
(= (add-to-pi 2) 5.14)
(= (add-to-pi 6) 9.14)

The difference between hellos's contract (see exercise 11.2.1) and that of add-to-pi is the output, but as we have seen this does not affect the template design. We obtain the template for add-to-pi by renaming hellos appropriately:

(define (add-to-pi n)
  (cond
    [(zero? n) ...]
    [else ... (add-to-pi (sub1 n)) ... ])))

In combination with the examples, the template immediately suggests how to complete the function. If the input is 0, add-to-pi's answer is 3.14. Otherwise, (add-to-pi (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 (add-to-pi (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 multiply-by-pi, which consumes a natural number and multiplies it by 3.14 without using *. For example,

(= (multiply-by-pi 0) 0)
(= (multiply-by-pi 2) 6.28)
(= (multiply-by-pi 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

;; add-to-pi : N  ->  number
;; to compute n + 3.14 without using +
(define (add-to-pi n)
  (cond
    [(zero? n) 3.14]
    [else (add1 (add-to-pi (sub1 n)))]))

Figure 32: Adding a natural number to pi

³⁴ It is important to start counting at 0 so that we can use the natural numbers for counting the number of items on a list or the members of a family tree.