CS 135 (Module 7: Natural Numbers)

empty is a

(listof Int)

Is 0 a natural number?

Yes

What do logicians use to define the natural numbers?

Peano axioms

What do the Peano axioms include?

1. 0 is a natural number
2. For every natural number n, S(n) is a natural number

What is S(n) called?

The successor function

What is a successor function?

It is a function that consumes a natural number, and returns the next

What does the successor function produce?

The "next" natural number

What Racket function is used as the successor function?

add1

What is the inverse function of add1?

sub1

A Nat is one of:

- 0
- (add1 Nat)

What happens if (zero? n) is false?

Then n has the value (add1 k) for some k

How do we compute k?

We subtract 1 from n, using the built-in sub1 function

What do it mean to "go along for the ride"?

It is an informal CS135 expression for an argument that is passed unchanged in the recursive application.

What is the function for counting down?

;; requires: n >= base
(define (countdown-to n base)
(cond [(= n base) (cons base empty)]
[else (cons n (countdown-to (sub1 n)
base))]))

What does countdown-to require?

It requires for the relationship n>=b to hold.

What about counting up to b?

;; requires: n