Comp210: Principles of Computing and Programming
Fall 2004 -- Lab #4: Natural Numbers   

Index: What is a natural number?, Template, Examples

Review: What is a natural number?

Among computer scientists, the natural numbers are 0,1,2,3,... We can define these with the data definition 

     ; A natural number (nat) is one of
     ;    0                             i.e., zero, or
     ;    (add1 n), where n is a nat    i.e., the successor of a nat
We then consider, e.g., 4 only a convenient shorthand for the official way of writing the natural number (add1 (add1 (add1 (add1 0)))).

An aside on zero

Mathematicians disagree on whether zero should be included in the natural numbers. See also some perspectives on zero and a history of zero.

At the beginning of the course we wrote functions on numbers, so what's different now? With the previous functions, we had a nice simple closed form equation for our function. Many other functions on numbers are not so simple and, instead, take advantage of this recursive structure of natural numbers. One commonly seen in high school is factorial:

0! = 1
(n+1)! = n � (n!)

Review: Template

The template is (mostly) straightforward, following the ideas we've seen with lists: 

     ; TEMPLATE
     ; f-nat : nat -> ...
     ; (define (f-nat n)
     ;    (cond
     ;        [(zero? n)      ...]
     ;        [(predicate? n) ...(f-nat (selector n))...]

But what should the predicate and selector be? If we had defined the non-zero natural numbers via our own structure, e.g., 

     (define-struct successor (n))
then we'd know how to answer this. But, we sort of cheated, instead using the built-in add1 function as a constructor and the built-in numbers are "shorthand". We did this solely as a matter of convenience, so that we could use other built-in math functions. So, we'll sort of cheat and use corresponding other built-in functions as the predicate and selector. The following is the resulting template. 

     ; TEMPLATE
     ; f-nat : nat -> ...
     ; (define (f-nat n)
     ;    (cond
     ;        [(zero? n)     ...]
     ;        [(positive? n) ...(f-nat (sub1 n))...]

Examples

Now it's time for a bunch of examples. You probably won't have time for all of these during lab.

Natural number examples

As usual, follow the remaining four function-specific steps of the design recipe for each.

  1. Develop a function returning the sum of the numbers 0..n, given n as input.

  2. Develop a function returning the list of the numbers n..0 (left-to-right), given n as input.

  3. Develop a function returning the list of the numbers 0..n (left-to-right), given n as input.

    Note: This is surprisingly a bit tougher than the previous function. Try both of the following strategies:

    • One strategy is the traditional "reverse accumulation" we've been using. Hint: For this, you also want to write a helper function on lists. What would you like this helper to do?

    • Another is the "forward accumulation" (or accumulator-style) just introduced in class.

  4. Develop a function returning the list of all the prime numbers in n..0, given n as input. To accomplish this, first create the following series of helper functions:

    1. Develop a function determining whether a given n is a factor of a given m. Use non-recursive mathematical functions for this, as we don't need to use the structure of our data.

    2. Develop a function determining whether a given m has any factors between 2 and a given n.

      Hint: This is a good example of one of the few times you want to alter the standard natural number template. We are only interested in this when m≥2, and so we really want to talk about the type natural-numbers-≥2, with an appropriate data definition and template.

    3. Develop a function determining whether a given n is prime. The numbers 0 and 1 are not prime.

      Note: What is an appropriate value of m to give to the previous function?

    Note: There are many other ways of breaking down this problem into subparts. This way is inefficient, but fairly straightforward, and based upon what we've covered so far.

Last Revised Tuesday, 24-Aug-2004 13:49:02 CDT

©2004 Stephen Wong and Dung Nguyen