Comp 210 Lab 4: Other Recursive Data

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.

Natural Numbers

We have previously written programs for numbers, and have considered numbers to be data without any structure. Frequently, however, it is useful to view the numbers 0,1,2,... as having structure, and use that structure to help us develop our programs. We call these the natural numbers. (While high school textbooks often use this term for 1,2,..., mathematicians and computer scientists use the term for 0,1,2,...)

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

While we can type (add1 (add1 (add1 0))), we can also use the "shorthand" 3.

Since we are just imposing this structure on Scheme's built-in numbers, we have to bend the rules a little on our constructor, selector, and predicate functions.

Constructors: The constant 0 and function add1, as shown above.
Selector: If you have (add1 n), then to get n back, you use sub1! I.e., (sub1 (add1 n)) = n.
Predicates: zero? and positive?.

We use this structure when we want to use all the numbers n, n-1, ..., 1, 0. Previously, we were just doing simple, algebraic, non-repeating calculations. It is up to you to realize which view is appropriate for which application.

Natural number template
So, how should we put those pieces together in a template?
See solution.

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.

Natural number examples
Develop programs to do the following: Given natural number n, compute n+(n-1)+(n-2)+...+0. Given natural numberss n and m, compute mⁿ by multipliying n copies of m. Given a natural number and a symbol, return a list of that many copies of the symbol. E.g., (copies 3 'hi) = (cons 'hi (cons 'hi (cons 'hi empty))) Given a natural number n, return 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. As a more esoteric example, we can define the even negative natural numbers as
```
     ; An even-neg-natnum is one of
     ; -  -2, or
     ; -  (- n 2),
     ;    where n is an even-neg-natnum.
     
```

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

Family Trees

From lecture, we have the data definition and template for family trees:

     ; A ftn (family tree node) is one of
     ; - name,
     ;   where name is a symbol, or 
     ; - (make-ftn name mother father),
     ;   where name is a symbol, and mother and father are ftns.
     (define-struct ftn (name mother father))

     ; (define (f a-ftn ...)
     ;    (cond [(symbol? a-ftn)
                 ...]
     ;          [(ftn? a-ftn)
     ;           ...(ftn-name a-ftn)...
     ;           ...(f (ftn-mother a-ftn) ...)...
     ;           ...(f (ftn-father a-ftn) ...)...]))

The first form represents a person whose parents are not known or not of interest, and the latter represents a person together with their parents' ancestries.

This is not the only useful definition of family trees. In fact, it is rather simplistic, as it is much easier to get information about ancestors than descendants. But it is a useful and intuitive example.

Family tree examples
Develop programs to do the following: Count the number of people in a family tree. Count the number of people whose parents are not given in the family tree. Given a family tree and a name of a person, return either that person's family tree or `'NotFound`, depending on whether that person is in the tree or not. Given a person's family tree, return a list of that person's matriarchal ancestors (i.e., mother, mother's mother, mother's mother's mother, etc.). Given a family tree and a name of a person, return either a list of that person's matriarchal ancestors or `'NotFound`, depending on whether that person is in the tree or not. For the curious... Given a person's family tree and a natural number, count the number of known ancestors in the tree that are the specific number of generations back. E.g., zero generations back is defined as the person him/herself, and one generation back is the person's parents. Hint: A helper function might really be helpful here.

In general, trees are any recursive data structure with more than one recursive case. They are called "trees" because of their pictorial resemblance to the branches of green leafy trees in nature. We will see lots of variants on this basic idea.