Comp 210 Lab 4: More Lists, Natural Numbers

This lab provides additional practice with lists, emphasizing more interesting uses than in the previous lab. We also review and use the very similar datatype of natural numbers.

Important for all examples:

• Follow the design recipe.
• For each group of examples, use the same template, because the functions are on the same kind of data.
• Use the stepper to help understand the programs.

Index: Lists, Natural Numbers

Continue with last week's list examples, in particular, the functions resulting in lists, non-empty lists, and as seen in class, heterogenous lists.

As discussed in class, natural numbers are all the non-negative integers. It is often convenient to consider them with the following recursive data definition.

     ;; A natural number (nat) is one of
     ;;   - 0, or
     ;;   - (add1 n)
     ;;     where n is a natural number.

When we originally worked with numbers, we didn't use such templates. What's the difference, and why should we use them now? Before, we simply looked at numbers as data with no inherent structure and only used them for standard algebraic equations. Now, we sometimes want to view natural numbers as having structure. In particular, whenever you want to use all the numbers n, n-1, ..., 1, 0, we are using this structure. It is up to you to realize which view is appropriate for which application.

For the curious... Note that the natural numbers are structurally just like lists, if you ignore the elements of the lists. In computer science, recognizing such isomorphisms (iso- = same, -morph = shape) is often helpful in adapting solutions from one domain to another.

To do:

1. Develop a program which computes n+(n-1)+(n-2)+...+0 for natural number n.
2. Develop a program which computes mⁿ by multipliying n copies of m.
3. Develop a program which consumes a natural number and a symbol and returns a list of that many copies of the symbol. E.g.,

        (copies 3 'hi) = (cons 'hi (cons 'hi (cons 'hi empty)))
        

4. Develop a program which consumes a natural number n and returns a list of the natural numbers from n-1 to 0.

For the curious... Sometimes it is worthwhile to view some subset of numbers as having other structure. For example:

• As we've seen before with tax brackets, we sometimes want to divide the numbers into intervals, and these intervals are the only interesting structure.
• We sometimes want to count up (or down!) from some other number than 0. For example, if we are only interested in positive numbers, we can define

       ; A pos-natnum is one of
       ; -  1, or
       ; -  (add1 n),
       ;    where n is a pos-natnum.
       

  Notice the isomorphism between positive natural numbers and non-empty lists. Or, for something more esoteric like just the even negative numbers, we can define

       ; An even-neg-natnum is one of
       ; -  -2, or
       ; -  (- n 2),
       ;    where n is an even-neg-natnum.