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: Family Trees, Natural Numbers, Lists

Family Trees

From lecture, we have the data definition of a FamTree:

Definition: a FamTree is

• 'unknown, or
• (make-child symbol FamTree FamTree number), where the symbol represents a name, the first FamTree is the mother's family tree, the second FamTree is the father's side, and the number is the birthyear.

In case you don't remember, the predicate to test for 'unknown is:

(define (unknown? val) 
	(and (symbol? val) (symbol=? 'unknown val)))  

To do:

1. Develop a program to count the number of known people in the FamTree (this is one of the functions developed in class).
2. Develop a program to count the number of unknown people in the FamTree.
3. Develop a program to see if a supplied name is an ancestor (similar to one of the functions developed in class, but more general).

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 (if you feel you need some warm-up exercises):

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.

To do (once you're ready):

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

2. 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.
       

In each of these cases, your data definition and template should follow the structure that you are using.

Extra! Extra!

Optional problem: Develop a program to count the number of known ancestors in a FamTree that are a supplied number of generations back. "Zero generations back" is defined as the child itself. "One generation back" is thus the child's parents. Hint: A helper function might really be helpful here.

Lists continued (if you have extra time)

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