More on the Nature of Natural Numbers

Next: Composing FunctionsRevisited Again Up: Natural Numbers Previous: Alternative Data Definitions for

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 ) 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

contains the complete function definition.

Exercises 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 these definitions, too.

Hint: Recall that multipliplying 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 the 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 ) 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: Adding a natural number to pi

Next: Composing FunctionsRevisited Again Up: Natural Numbers Previous: Alternative Data Definitions for

PLT