Comp 210 Lab 6: Descendent Trees

In lecture, we originally discussed Ancester Trees (where each person had exactly two parents), and today turned that on its head and introduced Descendent Trees (where each person has any number of children). This entailed two things -- a data definition for a single Person, and a seperate definition for a list-of-Persons.

With your partner: As in class, write a data definition for a Person, which encapsulates their name, their birthyear, and a list of their kids.

With your partner: As in class, write a data definition and template for a list-of-Persons (since this type of data is intrinsic to our problem).

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 Herbert Homer)))
     (define Abe     (make-Person 'Abe     1920 (list Herbert Homer)))

Note how we're using define to save ourselves typing. (To ask your partner: how would we write the descendent tree for Homer look like, if we hadn't have used define? How about for Abe?)

Review: Write the function size, which takes in a Person, and returns the total number of Persons involved. Here are test cases for the above (again using the defined placeholders to save us typing):

(size Bart)
1

(size Marge)
4             ; Marge, Bart, Lisa, Maggie

(size Abe)
6

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 intendent appropriately, but not necessarily as internalized structure. For instance:

-Jackie (b. 1926)
  |-Selma (b. 1950)
  |-Marge (b. 1956)
  |  |-Bart (b. 1979)
  |  |-Lisa (b. 1981)
  |  |-Maggie (b. 1988)
  |-Patty (b. 1950)

(Okay, for discussion purposes I reversed the order of Marge and Patty.)

With your partner: Write down a couple of other sample outputs (say for Bart, and for Marge). We'll say that a list of kids prints out in the same order as listed in the data structure, which might be

Group discussion: We're going to write a function Person->string (or, "Person.toString" if you prefer) which makes a string-representation of a Person.

How do the solutions to the sub-problem (ie the string version of Marge) relate to the total solution (the string version for, say, Jackie)?
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?

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

  ;; 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 limmy (string-append "There once was a man from Kali,"
                               newline
                               "Whose limerick stopped at line three."
                               newline
                               "You'd think it just started --"))
  limmy
  (display-string limmy)

In retrospect: How do your functions follow from the templates involved? How many lines of code?
(soln.)

Other thoughts, after finishing: Did you use magic string-constants? Did you call newline from only one place (single point of control)? Is your code indented reasonably?

A couple of notes on strings and I/O

Converting data to strings throws away the data's structure. You should never marshall your high-level, structured data down into a string, pass that string to some other function, thus forcing that function to parse the string -- do a bunch of work to re-constitute the inherent 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, you may be interested in drscheme's menu item "insert XML box", and evaluate such boxes (e.g. HTML with fully paired tags) to see one way to internally represent XML as scheme lists.
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 (you input a number by typing it in as an argument; structures are output you've seen).

Formatting output is more important when writing programs that other non-programmers will want to use; to solve your own problems, it's rarely relevant to solving the problem itself. (Some language envireonments 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.)