COMP 210 Lab 6: Mutually Recursive Data

Descendant Family Trees

Review: In class, we originally discussed Ancestor Family Trees (where each person had exactly two parents), and today turned that on its head and introduced Descendent Family Trees (where each person has any number of children). This entailed two separate interrelated types: 

     ;; A Person is a structure
     ;; where name is their name, year is their birth year
     ;; and kids is a list the person's children.
     ;; (make-Person symbol num list-of-Persons)
     (define-struct Person (name year kids))

     ;; A list-of-Persons is either
     ;; - empty
     ;; - (cons Person list-of-Persons)

As a reminder, here are their templates: 

     ;; Template for Person
     (define (f-Person a-person)
        ...(Person-name a-person)...
        ...(Person-year a-person)...
        ...(f-lop (Person-kids a-person))...)))
     ;; Template for list-of-Persons

      (define (f-lop a-lop)
        (cond
          [(empty? a-lop) ...]
          [(cons? a-lop)  ...(f-Person (first a-lop))...
                          ...(f-lop (rest a-lop))...)]))

Some examples of this data might be 

     (define Bart    (make-Person 'Bart    1979 empty))
     (define Lisa    (make-Person 'Lisa    1981 empty))
     (define Maggie  (make-Person 'Maggie  1988 empty))
     (define Homer   (make-Person 'Homer   1955 (list Bart Lisa Maggie)))
     (define Marge   (make-Person 'Marge   1956 (list Bart Lisa Maggie)))
     (define Selma   (make-Person 'Selma   1950 empty))
     (define Patty   (make-Person 'Patty   1950 empty))
     (define Jackie  (make-Person 'Jackie  1926 (list Selma Patty Marge)))
     (define Herbert (make-Person 'Herbert 1950 empty))
     (define Mona    (make-Person 'Mona    1929 (list Homer Herbert)))
     (define Abe     (make-Person 'Abe     1920 (list Homer Herbert)))

Descendant Family Tree warm-up exercises

These are variations on the in-class example. Do some to make sure you understand the template, before moving on to the more difficult next exercise.

  1. Note how we're using define to save ourselves typing. How would we write the descendent tree for Homer, if we hadn't have used define? How about for Jackie?

  2. Develop a function that counts the number of decendants in a person's family tree. Include the person in the count.

  3. Develop a function that returns whether there is someone in a family tree with a certain given name.

Descendant Family Tree pretty-printing exercises

Note how DrScheme displays the value Abe: nicely indented, but in Scheme format, using "make-Person", "list", etc. This is the preferred way for us programmers, because it shows the structure of the data. But suppose we want to show our data to non-programmers. We still want things indent appropriately, but not necessarily as internalized structure, e.g., 

     Jackie (b. 1926)
     |_ Selma (b. 1950)
     |_ Patty (b. 1950)
     |_ Marge (b. 1956)
        |_ Bart (b. 1979)
        |_ Lisa (b. 1981)
        |_ Maggie (b. 1988)
or 
     Abe (b. 1920)
     |_ Homer (b. 1955)
        |_ Bart (b. 1979)
        |_ Lisa (b. 1981)
        |_ Maggie (b. 1988)
     |_ Herbert (b. 1950)
We will write a function Person->string produces that output as a string. This will be similar to the corresponding function for Ascestor Family Trees shown in class.

  1. What are a couple of other sample outputs (e.g., for Abe and Bart)?

    Assume that a list of children should print out in the same order as listed in the data structure. That does not necessarily correspond to birth order.

  2. Group discussion: How do the solutions to the sub-problem (e.g., the string version of Marge) relate to the total solution (e.g., the string version of Jackie)?

  3. Group discussion: What info do we need to keep track of, when writing these examples on the board? We need to keep track of what to output at the beginning of each line -- at first nothing, but for each generation, another copy of " |". This is an accumulator! I suggest naming the accumulator prefix; how does the prefix for one's kids differ from one's own prefix?

  4. Okay, write the function!

    A couple of built-in functions you'll need to use are symbol->string and number->string. Also, load the teachpack (through DrScheme's Language.. menu.) 

             /home/comp210/Labs/Lab06/lab06-lib.ss
    This provides you with the following constant and function: 
             ;; newline: string
         ;; The one-character string with a carriage-return.
  
         ;; display-string: string -> true
         ;; Display the given string in a text-box.
         ;; Always returns true.

         ; Example:
         (define limerick (string-append "There once was a man from Kali,"
                                         newline
                                         "Whose limerick stopped at line three."
                                         newline
                                         "You'd think it just started --"))

         limerick
         (display-string limerick)

  5. For the curious... For similarity to the pretty-printing with ancestor trees, we'd prefer the output for Abe to be 

             Abe (b. 1920)
         |_ Homer (b. 1955)
         |  |_ Bart (b. 1979)
         |  |_ Lisa (b. 1981)
         |  |_ Maggie (b. 1988)
         |_ Herbert (b. 1950)
    without changing the output for Jackie. Write that version.

    Hint: Note that the last child is treated differently than the others in that his/her children are not prefixed by a vertical bar. You'll need to check for that, while not breaking encapsulation.

Sample solution.