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

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

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

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 

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   )

= (cons 'hello empty) 

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   )

= (cons 'hello (cons 'hello empty)) 

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

Exercise 11.2.3

Develop apply-n. The function consumes a natural number, n. It applies the function move from exercise  n times to FACE, the list of shapes from exercise . 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 . 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