Comp210: Principles of Computing and Programming
Fall 2004 -- Lab #6: Mutually Recursive Data   

Pragmatically, we would have a representation of family trees that had the advantages of both the ancestor- and descendant-based versions. That is indeed possible. For that, we want a graph, a kind of data structure that we will look at later in the course.

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.

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)
  

     Abe (b. 1920)
     |_ Homer (b. 1955)
        |_ Bart (b. 1979)
        |_ Lisa (b. 1981)
        |_ Maggie (b. 1988)
     |_ Herbert (b. 1950)
  

Like the other pretty-printing examples, this program will involve two separate conceptual strategies: data-driven mutual recursion and problem-driven accumulation (of the prefix string).

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, some additional space. This is an accumulator!

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 /home/comp210/Labs/Lab06/lab06-lib.ss via DrScheme's Language.. menu. 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.

• Some people thing that input and output are intrinsic to programming. They're not -- they're just impediments to get around, before you can even begin to solve the problem you're interested in. DrScheme makes I/O fairly transparent via the calculator-like behavior of the read-eval-print loop.

  Formatting output is more important when writing programs that other non-programmers will want to use. It's rarely relevant to solving the problem itself.n Thus, it's necessary, but uninteresting. (Some language environments don't have default output so nice; in those cases, programmers usually have to spend time, for each structure, writing how to format it, just so they can debug more easily.)

• Converting data to strings throws away the data's structure. You should never convert your high-level, structured data down into a string, pass that string to some other function, and force that function to parse the string back into a structure.

  Working within a single language, it's easy to pass your high-level structures immediately. Saving structured data to a file or communicating across a web-link is more problematic. The recent solution is to encode structure as a series of "tags" in a language called XML. XML is a standard way to convert (nested) lists into strings, in a way that makes it trivial to reconstitute the original structure. If you know some XML (or HTML), you may be interested in DrScheme's menu item Insert XML box.