TeachScheme! 2002

  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.

   empty
   (cons 'apple empty)
   (cons 'milk (cons 'apple empty))
   (cons 'pie (cons 'apple empty))

   cons : any-value list -> cons
   first : cons -> any-value
   rest : cons -> any-value

   (first (cons 'apple empty)) = 'apple
   (rest (cons 'milk (cons 'apple empty)))
     = (cons 'apple empty)

  Data definitions help us by describing how to _build_ data.  We need
  a definition to help us build list-of-symbols

  Data Def: A list-of-symbols is
   - empty
   - (cons symbol 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)))?

  ;; length : list-of-symbols -> number

  Develop data definition for list-of-number

  ;; sum : list-of-number -> number
  [Show evaluation in the Stepper]

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

  ;; length : list-of-number -> number

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

  [PVD 2001: It's absolutely essential for them to get the contracts of
   recursive functions right.  The wording has to be "tight", too:
   "... consumes ... and produces ...".  Then teach them to substitute
   the argument, say (REST ...), in the purpose.  I had the whole class
   do a read-along, and wouldn't let them go on till they got it
   exactly right.  Later in lab, I found most people having trouble with 
   recursion had rotten or no contracts.  Each time I made them write one,
   cleanse it, then read-along.  It always seemed to help.]