Lecture 9: Counting Beans

###
Lecture 9: Counting Beans

1. Postscript on family tree: some family trees don't have father and mother or nobody for each person.
   Example:

                 Eve *
              ____|
             |
           Mary   Louis *
             |_____|
                |
               Ben

   Here we know both parents of Ben, but we don't know Mary's father.

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

       (define-struct child (father name mother))

       A family-tree is either a
         - #f ('Unknown, empty, 5)
         - (make-child F name M)
           where F is family-tree and M is family-tree.

   Let's translate the example:

        (make-family
           (make-family #f 'Louis #f)
           'Ben
           (make-family
             (make-family
                #f
                'Mary
                 (make-family #f 'Eve #f))))

   Now let's prune Louis's tree from ours.

        ;; prune : family-tree -> family-tree
        ;; produces a tree like a-ft but with all trees rooted by 'Louis eliminated
        (define (prune a-ft) ...)

   Finish in preparation for exam.

   Would that have been as easy as that in the previous version? No, choice of data definition matters!

2. Let's count:

        *-----------*   *-----------*   *-----------*   *-----------*
        |           |	 |           |	 |           |	 |           |
        |           |	 |    x      |	 |   x x     |	 | x x x     |
        |           |	 |           |	 |           |	 |           |
        *-----------*	 *-----------*	 *-----------*	 *-----------*

       X's:   0              1                2              3

   These are called ordinals or natural numbers. Describe the set of natural numbers!

       0 1 2 3 ...

   Dots are no good. They don't really tell us what there is in a collection.

   Don't trust mathematicians that use dots. Question their definitions. Make them spell out the details. They are cheating you.

          _________________________________
         |                                 |
         V                                 |
       A natural-number is either a        |
         - 0                               |
         - (add1 N)                        |
           where N is a natural-number------

   Not surprisingly, a self-referential definition.

   Okay, let's program with these things.

       ;; f : natural-number -> XYZ
                ___________________________
               |                           |
               V                           |
       (define (f a-nn)                    |
         (cond                             |
           [(zero? a-nn) ...]              |
           [else ... (sub1 a-nn) ... ------
             ]))

       ;; plus : natural-number number -> number
       (define (plus a-nn X)
         (cond
           [(zero? a-nn) X]
           [else (add1 (plus (sub1 a-nn) X))]))

       ;; times : natural-number number -> number
       (define (times a-nn X)
         (cond
           [(zero? a-nn) 0]
           [else (plus X (times (sub1 a-nn) X))]))

       ;; expt : number natural-number -> number
       (define (expt X a-nn)
         (cond
           [(zero? a-nn) 1]
           [else (times X (expt X (sub1 a-nn)))]))

3. Natural numbers come in different flavors and programmers need to think about these flavors -- for historical reasons:

          _________________________________
         |                                 |
         V                                 |
       A natural-number[>=20] is either a  |
         - 20                              |
         - (add1 N)                        |
           where N is a natural-number[>=20]

          _________________________________
         |                                 |
         V                                 |
       A natural-number[<=20] is either a  |
         - 20                              |
         - (sub1 N)                        |
           where N is a natural-number[<=20]

   Make templates!

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