[2/15/99]

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

* Lists:  continued

  --------------------
     empty - the empty list (sometimes "'()" or just "()")

    (cons x l) - list constructor: get some value x, and a list l, create the
      list that starts with x and continues with l.  Examples.

    (head l) - returns the head of a list.  Also first (and the standard: car).
    (tail l) - returns the tail of a list.  Also rest (and the standard: cdr).

    (list x1 x2...) - short for (cons x1 (cons x2 (cons ... empty)))

    second, third... - useful functions (std: cadr, caddr...).
  --------------------

  A quick note about the old age of the car/cdr names.  Another note - you
  might see these car/cdr in documentations, and also in error messages.

  The only thing we care about with lists is that they behave according to a
  well defined _contract_:

  --------------------
    (head (cons x l)) --> x
    (tail (cons x l)) --> l
  --------------------

  Some more functions, built in but simple to define:

  --------------------
    length
    append
  --------------------

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

* Now to solve the local recursive problem, yet another let relative:

  --------------------
    (letrec ((v1 exp1) (x2 exp2)...) body...)
  --------------------

  Looks exactly like its both relatives, but as expected, behaves differently.
  Actually, the formal substitution rules that we had so far are not enough to
  handle this beast.  In class, you will see a rule to handle that, and it is
  actually fun to try and follow it blindly and see that it works (at least I
  think it's fun...).

  Now we can have local iterative helper functions, as in:

  --------------------
    (define (fact n)
      (letrec ((aux (lambda (n a)
                      (if (zero? n)
                        a
                        (aux (- n 1) (* n a))))))
        (aux n 1)))
  --------------------

  Note that the internal function is a standard tail-recursive function.

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

* Internal definitions: a readable shortcut for letrec is internal define
  statements such as:

  --------------------
    (define (fact n)
      (letrec ((aux (lambda (n a)
                      (if (zero? n)
                        a
                        (aux (- n 1) (* n a))))))
        (aux n 1)))
  --------------------

  can be rewritten as:

  --------------------
    (define (fact n)
      (define (aux n a)
        (if (zero? n)
          a
          (aux (- n 1) (* n a))))
      (aux n 1))
  --------------------

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

* A very important aspect of Scheme - using "higher order" functions -
  functions that get and return functions.
  Here is a ver simple example:

  --------------------
    (define (f x) (lambda () x))
    (define a (f 2))
    (a)  -->  2
    (define b (f 3))
    (b)  -->  3
  --------------------

  Note - what we get is actually an object that remembers (by the substitution
  we're doing) a number.
  How about:

  --------------------
    (define aa (f a))
    (aa)    -->  #<procedure> (this is a)
    ((aa))  -->  2
  --------------------

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

* A bit more sophisticated example:

  --------------------
    (define (plus x) (+ x 2))
  --------------------

  We saw that to generalize this, we replace 2 by a variable and add it to the
  argument list, but what if we think differently - we can say that there are
  many versions of similar functions:

  --------------------
    (define (plus x) (+ x 1)) or (define plus (lambda (x) (+ x 1)))
    (define (plus x) (+ x 2)) or (define plus (lambda (x) (+ x 2)))
    (define (plus x) (+ x 3)) or (define plus (lambda (x) (+ x 3)))
    (define (plus x) (+ x 4)) or (define plus (lambda (x) (+ x 4)))
    ...
  --------------------

  How would we write a function that will get y and return one of these
  functions, namely (lambda (x) (+ x y))?  This is easy to write when thinking
  about it in this way:

  --------------------
    (define plus (lambda (y) (lambda (x) (+ x y))))
  --------------------

  Spend time here clarifying the meaning of plus, (plus 1) and ((plus 1) 2).

  Generally, every function that we write like:

  --------------------
    (define f (lambda (x y...) ...))
  --------------------

  Can be rewritten as:

  --------------------
    (define f (lambda (x) (lambda (y) ...)))
  --------------------

  This is called Currying.

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