[3/3/99]

===============================================================================

* Last thing with lists - "folding":

  --------------------
    (define (fold bin-op l)
      (cond ((null? l) (error "fold: expecting a non-empty list"))
            ((= (length l) 1) (head l))
            (else (bin-op (head l) (fold bin-op (tail l))))))
  --------------------

  Quick discussion - why is the (= (length l) 1) condition very inefficient?
  What is the run time?  Soltion - use (null? (tail l)) instead.

  Our fold function can uses the binary operator in a right associative manner,
  so we could name that folr-right, and also implement fold-left, which is
  easily implemented using tail recursion (without error checking):

  --------------------
    (define (fold-left bin-op l)
      (define (iter n l)
        (if (null? l)
          n
          (iter (bin-op n (head l)) (tail l))))
      (iter (head l) (tail l)))
  --------------------

===============================================================================

* A point about interface functions:

  Whenever we define some data type with functions that manipulate this type,
  it should be clear when we use these functions and when not.  For example, in
  PS#3 we have the interface functions for terms:

  --------------------
    (define formula? list?)
    (define op first)
    (define terms rest)
  --------------------

  These are simply lists, but they must be used whenever you handle terms, for
  example, to get the operator symbol of a term t, you can use (head t), but
  this is a mistake since you "cross interface boundaries" - relying on the
  fact that a term is a list with the operator being the first symbol.  A good
  indication for things going the wrong way is thinking about what will happen
  if we modify the implementation, say that a term holds the operator as the
  middle symbol as in '(x and y) - this will make the code that uses (head t)
  fail.

  You might also say that under the given interface, getting the first subterm
  of a term t can be done with (op (terms t)), but this is just as wrong!  It
  uses the "op" function, relying on the fact that it returns the first element
  of a list so it is also breaking the interface abstraction layer.  What
  should be realized is that the terms "function" actually returns a list, so
  it should be used with list functions.  The same common sense rule can be
  applied here, seeing that such code will also break.

===============================================================================

* Association lists:

  Many times, it is useful to use lists as an associative collection of some
  sort.  for example, we might want to use an association that "binds" an email
  address to a number, this can be represented by a list like:

  --------------------
    (define users '((234 "abc12@cornell.edu") (987 "zyx87@cornell.edu") ...))
  --------------------

  And how would we get a value bound to some number?  We can write this
  function (note the use of the equal? function - compare any two values
  recursively):

  --------------------
    (define (assoc key alist)
      (cond ((null? alist) #f)
            ((equal? (first (first alist)) key) (second (first alist)))
            (else (assoc key (tail alist)))))
  --------------------

  The problem is - how do we know if the associated value is actually #f?  For
  this reason, the built-in assoc function returns the actual list whose head
  matches the given key:

  --------------------
    (assoc 987 users)  -->  (987 "zyx87@cornell.edu")
  --------------------

  A quick game with lists - how would you implement an rassoc function that
  takes an association list and uses it _backwards_?

  --------------------
    (define (rassoc key alist) (assoc key (map reverse alist)))
    (rassoc "zyx87@cornell.edu" users)  -->  ("zyx87@cornell.edu" 987)
  --------------------

===============================================================================