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    
(define (! n) ...) 

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) 

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

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    
(define (product-from-20 n-above-20) ...) 

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

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

(= (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)) ...])) 

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  contains the complete definition of product-from-20.

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 , 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 (define (! n) (cond [(zero? n) 1] [else (* n (! (sub1 n)))])) ;; product-from-20: N [>= 20] -> N ;; to compute (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 (define (product limit n) (cond [(= n limit) 1] [else (* n (product limit (sub1 n)))])) Figure: 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    
(define (product limit n) ...) 

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].

With this new data definition, we specify the contract for product as follows:

;; product: N[limit] N [>= limit] -> N
;; to compute    
(define (product limit n) ...) 

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

In exercises  and , 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 , , and , 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) ...) 

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