...
Instructions for students & labbies: Students use DrScheme, following the design recipe, working on the exercises at their own pace, while labbies wander among the students, answering questions, bringing the more important ones to the lab's attention. Students should feel free to skip the challenge exercises.
Natural Numbers
Review: Definition
In class, we defined our own version of natural numbers, its
corresponding template, and example data:
; A Natural is one of
; - 'Zero
; - (make-next n)
; where n is a Natural
(define-struct next (nat))
; f : Natural -> ...
(define (f n)
(cond (symbol? n) … (next? n) …(f (next-nat n))…))
(define Zero 'Zero)
(define One (make-next Zero))
(define Two (make-next One))
(define Three (make-next Two))
(define Four (make-next Three))
Here is an example function:
; add-Nat : Natural Natural -> Natural
; Returns the result of adding two Naturals.
(define (add-Nat n m) (cond (symbol? n) m (next? n) (make-next (add-Nat (next-nat n) m))))
Exercises
- Use the stepper on (add-Nat Two Two)to see how it works.
...
Scheme's
...
Built-in Naturals
We already know Scheme has lots of numbers built-in, like 3, 17.83, and -14/3. It is often convenient to limit our attention to a subset of these , such as the naturals: 0, 1, 2, 3, ... . We can define the naturals and its template as follows:
| Code Block |
|---|
; A natural |
...
is either:
; - 0
; - (add1 n)
; where n is a natural
; Template
; nat-f : natural -> ...
(define (f ... n ... )
(cond [(zero? n) ...]
[(positive? n)
... (f ... (sub1 n) ... ) ...]))
|
Of course, we already know what the example data looks like: 0, 1, 2, 3, ...
...