Notes: Friday 30 January 2004

Schedule

• Monday, 2 February: Problem Set 2
• Wednesday, 4 February: Read SICP, 2.1 and 2.2 (through page 127). You don't need to read the example section 2.2.4, but probably don't want to miss the footnote on page 127 about William Barton Rogers, MIT's founder, who left UVa after too many students were rioting outside his pavillion.
• Before 10 March: Read rest of GEB part I (Chapters 2-4 and 6-9, in addition to Chapters 1 and 5 you have already read). There will be no more specific reading assignments from GEB until end of Spring Break (there will be other reading assignments from SICP). By March 10th, you will be expected to have read all of Part I (through page 272) of GEB. I recommend reading about a Chapter a week, but if you prefer to read it all over Spring Break that is fine too.

Recusive Definitions on Lists

1. Be very optimistic. Since lists themselves are recursive structures, we should be able to come up with a recursive definition for almost anything we can think of doing with a list.
   1. Assume we can solve a smaller version of the problem.
   2. Break the problem into the original list and its cdr.
2. Think of the simplest version of the problem, something you can solve already. For lists, this is usually the null list. (Sometimes, it might be the length 1 list.)
3. Combine them to solve the problem. For lists, we will usually do combine the result of the recursive evaluation on the cdr with the result of doing something with the car of the list.

Many recursive list procedures can be defined with this template:

(define (listproc lst)
  (if (null? lst)
      [[[ insert base case here ]]]
      ([[[ f ]]] (car lst) (listproc (cdr lst)))))

For example:

(define (sumlist lst)
  (if (null? lst) 
      0 
      (+ (car lst) (sumlist (cdr lst)))))

(define (insertl lst f stopval)
  (if (null? lst)
      stopval
      (f (car lst) 
	 (insertl (cdr lst) f stopval))))

(define (sumlist lst) (insertl lst + 0))

(define (productlist lst) (insertl lst * 1))

(define (length lst) 
  (insertl lst (lambda (head rest) (+ 1 rest)) 0))

In mathematics you don't understand things, you just get used to them.
John Von Neumann