Lecture 8: Family Trees

1. Exam: FEB 18, 7pm, 1 hour
2. Two questions came up:

   (1) Why not use an example like

   (cons 100 (cons 55 (cons 123 empty)))

   My mistake: I broke the rule of using an example from a boundary.

   (2) Why not roll all cond-clauses into one:

   (define (elim alon) (cond ((empty? alon) empty) (else (cond ((> (first alon) 100) (elim (rest alon))) (else (cons (first alon) (elim (rest alon))))))))

   (define (elim alon) (cond ((empty? alon) empty) ((> (first alon) 100) (elim (rest alon))) (else (cons (first alon) (elim (rest alon))))))

   Answer: suppose your data definition enumerates 10 clauses, three of which must be dealt with via case distinction. That would yield 13 clauses.
   Now someone comes along and inserts a clause into the input data description. Where do you fix the program? -- That's why matching the input data description and the program layout totally is a good idea.

   ---

3. Given: a family tree with respect to some person. Question: How many people are known in the tree?
   Example:

    
   Adam *    Eve *
    |_________|
         |
       Mary   Louis *
         |_____|
            |
           Ben
   

   How can we represent this in Scheme? Here is one idea.

    
   A family tree is either a 
     - name 
     - (cons F (cons name (cons M empty)))
       where F is family-tree and M is family-tree.
   

   We see a fixed-length list. What should we do? Define constructors and selectors!

    
   (define-struct child (father name mother))
   
   A family-tree is either a 
     - name 
     - (make-child F name M)
       where F is family-tree and M is family-tree.
   

   Let's translate the example:

    (make-family (make-family 'Adam 'Mary 'Eve) 'Ben  'Louis) 

   How many family members? 5.

   Let's move on.

   ---

4. Was "Mary" ever used in the family?

   ---

5. Now suppose we run across family trees in which people don't always have a mother and a father? How should we represent those?

    
   (define-struct child (father name mother))
   
   A family-tree is either a 
     - #f
     - (make-child F name M)
       where F is family-tree and M is family-tree.
   

   Now let's prune Louis's tree from ours. Who would want to be a descendant of Louis XIV anyway?

   Would that have been as easy as that in the previous version?

   Choice of data definition matters!

   ---