TeachScheme! 2000

  Structures let us glue related information together
  
  Consider a whole zoo of animals: data to glue together?
  -- what about a shopping list?

  How to define a shopping list?  Structs fixed size, bad design
  We need some way to create data that is _arbitrarily large_.
  How can we define a class of such data?

  Lets' try just list-of-symbol.

  Instead of using a struct with a field for each item, use a struct
  with a field for for just one item, plus another list:
    (define-struct list (first rest))
  where `first' is a symbol and `rest' is another list. Also,
  we need `empty' for lists with no items.

   empty
   (make-list 'apple empty)
   (make-list 'milk (make-list 'apple empty))
   (make-list 'pie (make-list 'apple empty))

   (list-first (make-list 'apple empty)) = 'apple
   (list-rest (make-list 'milk (make-list 'apple empty)))
     = (make-list 'apple empty)

  [Nested cups, box picture on page 115.]

  As it turns out, the `list' structure is so useful that
  typing `make-list' and `list-first' is a waste of energy.
  We abbreviate with `cons', `first', and `rest':

   (make-list 'pie (make-list 'apple empty))
      = (cons 'pie (cons 'apple empty))

   [DrScheme only knows the abbreviation!]

  >> HOW CAN WE DESCRIBE THE **CLASS** OF ALL LISTS? <<
  The design recipe asks for this description!  

  Data Def: A list of symbols is
   - empty
   - (cons symbols los) where los is a list of symbols.

  Self-reference in data definition.
    discuss need for empty clause
    [stress that empty is a constant]
  Show how to derive examples from the data definition. 

  -- how to get to 'apple in (cons 'pie (cons 'apple empty))?
  -- what is (rest (rest (cons 'pie (cons 'apple empty))))?
  -- what is (rest (rest (cons 'apple empty)))?

  ; contains-tea? : list-of-symbols -> boolean

  [Show evaluation in the Stepper]

  >> DESIGN RECIPE FOR RECURSIVE DATA (p128) <<

  Do data defn for list-of-number, do sum