M07: Natural Numbers

Slides

Commentary

Recursion is an important tool for working with lists. In this lecture module we extend our recursive capabilities with a self-referential data definition for natural numbers, a corresponding template, and examples of problems that we can now solve.

We’ll start with a quick review of lists because our work with natural numbers will have many parallels.

The data definition tells us how we can build a (listof Int) (or any other type):

  • empty is a (listof Int) by definition.
  • 29 is an Int and therefore (by the second clause) (cons 29 empty) is a (listof Int).
  • 3 is an Int and therefore (by the second clause) (cons 3 (cons 29 empty)) is a (listof Int).
  • 5 is an Int and therefore (cons 5 (cons 3 (cons 29 empty))) is a (listof Int).

Alternatively, given (cons 5 (cons 3 (cons 29 empty))) we can use the data definition to work backwards, proving that it is a (listof Int). In fact, with the built-in predicate integer? we can write a function that determines whether its argument is a list of integers:

;; (listof-int? x) produces true if x is (listof Int) and 
;;     false otherwise.
;; Examples:
(check-expect (listof-int? empty) true)
(check-expect (listof-int? (cons 1 (cons 2 empty))) true)
(check-expect (listof-int? (cons "a" empty)) false)
(check-expect (listof-int? "A string") false)

;; listof-int?:  Any -> Bool
(define (listof-int? x)
  (cond [(empty? x)  true]
        [(cons? x)   (and (integer? (first x))
                          (listof-int? (rest x)))]
        [else        false]))

By the way, can you rewrite this function to eliminate the cond? You should.

Note that this doesn’t look quite like the listof-X-template because we aren not necessarily consuming a list.

Given the data definition on the previous slide, let’s review how we developed the template.

To repeat this reasoning, we’ll need to start with a data definition for natural numbers.

Just like we built up a list based on the data definition, we can use this data definition to build natural numbers.

  • 0 is a natural number by definition (first clause).
  • 1 is a Nat because it’s 1 more than 0, which is a Nat (second clause).
  • 2 is a Nat because it’s 1 more than 1, which is a Nat (second clause).
  • 3 is a Nat because it’s 1 more than 2….
  • 4 is a Nat because it’s 1 more than 3….

This logic parallels the logic for the list template. Note that for both data definitions we:

  • use a predicate to determine which case of the data definition applies
  • figure out how to pull the second, self-referential case apart into its pieces
  • apply the template recursively to the self-referential part of the data definition

NASA would love this function! Launch in T-10, 9, 8, … Liftoff!

Note that (countdown 2) produces 2 cons’d onto the result of (countdown 1) and that (countdown 1) produces 1 cons’d onto the result of (countdown 0).

countdown, applied to n-1, is the rest of the list.

Just like with the list template, we have some crucial questions to answer:

  1. What do we produce in the base case?
  2. In the recursive case, what (if anything) do we do to transform n?
  3. What is the result of processing (f (sub1 n)) recursively?
  4. How do we combine 2 and 3 to obtain the result for (f n)?

We should have the answer to question 1 from our examples. The answer to question 3 should be obvious from our purpose statement.

In this case, we do nothing to transform n (question 2); we just cons it onto the result of processing (f (sub1 n)) (question 4).

Predict what will happen if countdown consumes a negative value. Then check your prediction.

How long will this go on? Is there something you can do to the function to catch this and stop it?

What values can we generate from this data definition? Well, 7 belongs thanks to the first clause in the data definition. Because of that, 8 belongs and 9 and 10 and ….

Remember the definition of “simple recursion”? All the arguments in each recursive application are either unchanged or one step closer to a base case.

“Going along for the ride” is a informal CS135 expression for an argument that is passed unchanged to the recursive application.

Notice that the recursive applications all have two parameters, one for n and one for the base or stopping condition.

This work just find if we put in a negative number for the base – so long as the requires relationship still holds: n>=b.

A simple change in the data definition gives us the non-positive integers.

Carrying that change through to a template and then a function gives us a way to count up instead of down (sorry, NASA).

Doing a task some number of times is a common thing, both in real life and in programming. countup-to and countdown-to give us a mechanism to do that. We happened to use it to build a list, but there’s no reason we couldn’t substitute other tasks like finding the nth prime number or deploying n stuffed bears in a game or displaying a list of n friends on Facebook.

Combining the countup template with higher-order functions (Module 14) will be a powerful and flexible tool in our toolbelt.

This exercise can be done with information you now have, with careful thought. We’ll be talking about similar problems in the next lecture module, too.