Natural Numbers & List Abbreviations

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

The class slides had a number of example functions, including

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

We do not suggest actually using this data definition in everyday programs. There are two reasons for looking at this definition. First, it is a second example (after lists), of recursively defined data structures and how we write functions on them. Second, we can take this idea and apply it to Scheme's built-in numbers. The lab's examples will explore both of these.

Adapting to 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, the naturals: 0, 1, 2, 3, …. While these look a bit more familiar to us, the "naturals" and "Naturals" are in a one-to-one correspondence. We can define the naturals and its template as follows:

      ; A natural is one of
      ; - 0
      ; - (add1 n)
      ;   where n is a natural

      ; 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, …

Unlike for Naturals, we are not defining new Scheme values here (i.e., there's no define-struct), but we are defining a subset of all Scheme numbers that we are interested in. The definition and template use some built-in Scheme functions that we haven't seen before (add1, sub1, zero?), but which mean just what their names imply.

If we choose to ignore that Scheme has a built-in function +, we could define it ourselves, just like the above add-Nat on Naturals:

      ; add-nat : natural natural -> natural
      ; Returns the result of adding two naturals.
      (define (add-nat n m)
         (cond
            [(zero? n)      m]
            [(positive? n)  (add1 (add-nat (sub1 n) m))]))

Example functions

Built-in Natural Numbers and Templates

At the beginning of the course, we wrote lots of functions on numbers without using templates, and just using mathematical formulae. In those cases, we were writing functions on numbers without viewing the number as having any kind of internal structure.

Here, we are considering functions that work only on naturals. By adopting the recursive definition on naturals, we get a benefit -- the natural's template guides us in writing our functions.

However, as examples like the logarithm above show, not all functions will follow the template that mimics the data definition. This is a leading example, as we will soon be introducing a more flexible template to help in such situations.

List Abbreviations

Chapter 13 of the book introduces some new, compact methods for representing lists.

NB: From now on, we need to use the "Beginning Student with List Abbreviations" language. Change this now. (The chapter in the book lists "Intermediate Student". We'll get to "Intermediate Student" a little later.)

list

Using list we can quickly write a list with many fewer ()s:

      (list 1 2 3) =>
      (cons 1 (cons 2 (cons 3 empty)))

Notice that we did not end the list construct with an empty. What would happen if we did?:

      (list 1 2 3 empty) =>
      (cons 1 (cons 2 (cons 3 (cons empty empty))))

The last element has become a list of lists.

  (cons (cons 1 empty) empty)

  (cons 1 (cons (cons 2 (cons 3 empty)) (cons 4 (cons (cons 5 empty) empty))))
      

' abbreviations

Using ' notation we can abbreviate our lists even more. ' notation is especially useful when we have nested lists.

      '(1 2 3 4) =>
      (list 1 2 3 4) =>
      (cons 1 (cons 2 (cons 3 (cons 4 empty))))

     '(rabbit bunny) =>
     (list 'rabbit 'bunny) =>
     (cons 'rabbit (cons 'bunny empty))

     '(rabbit (2) (3 4 5)) =>
     (list 'rabbit (list 2) (list 3 4 5))
     (cons 'rabbit (cons (cons 2 empty)
                   (cons (cons 3 (cons 4 (cons 5 empty))) empty)))

We can think of the ' as distributing over the elements. We apply this rule recursively (Yes! Recursion strikes again!) until there are no more '(s left.

     '(rabbit (2) (3 4 5)) =>
     (list 'rabbit '(2) '(3 4 5))
     (list 'rabbit (list '2) (list '3 '4 '5)) =>
     ... =>
     (cons 'rabbit (cons (cons 2 empty)
                   (cons (cons 3 (cons 4 (cons 5 empty))) empty)))

NB: '1 reduces to 1. In general, '<a number> evaluates to <a number>.

  '((make-posn 1 2))

  '(1 (+ 1 1) (+ 1 1 1))
      

If we want to apply functions, we have to use either cons or list. (Not exactly true. There is another abbreviation, quasiquote, that we won't talk about in this course.)