Lecture 8: Family Trees

###
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!

Matthias Felleisen | This page was generated on Fri Mar 5 09:04:41 CST 1999.