recitation 5: cons/car/cdr/list

--------------------------------------------
cons  "constructor"
car   "contents of address portion of register"
cdr   "contects of decrement portion of register"

is cons/car/cdr/list a special form?  
(car (cons (+ 3 4) (/ 4 0)))

--------------------------------------------
drawing cons cell diagrams:
  * any time you see cons, draw a double box with 2 pointers
  * any time you see list with n items, draw a chain of n cons cells
  * (list) with no items is nil
  * evaluate the stuff inside & point to it

(define a (cons 1 2))
(define b (list (cons 1 2) (cons 1 2)))
(define c (list a a))
(define d (cons 2 nil))
(define e (cons nil 2))
(define f (list 2))
(define g (list))
(define h (list nil))
(define i (list 1 2 3 4))
(define j (list 5 (cdr (cdr i)) (cons 6 7)))

--------------------------------------------
to print a cons structure:
  * each cons cell is printed ( <car> . <cdr> )
  * cross out any ". nil" 
  * cross out any ". (" and it's matching ")"
  * nil (the empty list) may print out as () or #f

(cons 1 2)  
   -> (1 . 2)

(cons (cons 1 2) (cons 3 4)) 
   -> ((1 . 2) . (3 . 4))
   -> ((1 . 2) 3 . 4)

(cons 1 (cons 2 (cons 3 (cons 4 nil)))) 
   -> (1 . (2 . (3 . (4 . nil))))
   -> (1 2 3 4)

(list 1 2 3 4) -> (1 2 3 4)

--------------------------------------------
"cons-ing up a list"

(define (enumerate-interval a b)
  (if (> a b) nil
      (cons a 
	    (enumerate-interval (+ 1 a) b))))

* write an iterative version:

(define (enumerate-interval a b)
  (define (helper b so-far)
    (if (> a b) 
	so-far
	(helper (- b 1) (cons b so-far))))
  (helper b nil))

* iterative procedures often require helper functions,
  but not always

* in block structure, a is known from outer procedure

--------------------------------------------
"cdr-ing down a list"

(define (length lst)
  (if (null? lst)
      0
      (+ 1 (length (cdr lst)))))

* write an iterative version:

(define (length lst)
  (define (helper lst count)
    (if (null? lst) count
	(helper (cdr lst) (+ count 1))))
  (helper lst 0))

--------------------------------------------

"cdr-ing down the input & consing up a result"

(define (cube-neighbor-diff lst)
   (cond ((null? lst) nil)
	 ((null? (cdr lst)) nil)
	 (else (cons (* (- (cadr lst) (car lst))
			(- (cadr lst) (car lst))
			(- (cadr lst) (car lst)))
		     (cube-neighbor-diff (cdr lst))))))

(cube-neighbor-diff (list 1 3 4 7)) -> (8 1 27)

* repeated code, use let:
		  
(let ((a 5)
      (b 10)) 
  (+ a b))

(define (cube-neighbor-diff lst)
  (cond ((null? lst) nil)
	((null? (cdr lst)) nil)
	(else (let ((a (- (cadr lst) (car lst))))
		(cons (* a a a)
		      (cube-neighbor-diff (cdr lst)))))))

* is let a special form?

--------------------------------------------

(define (all-pairs a b) 
  (if (null? a) 
      nil
      (append-list (match-with (car a) b)
		   (all-pairs (cdr a) b))))

(define (append-list a b)
  (if (null? a) 
      b
      (cons (car a) (append-list (cdr a) b))))

(define (match-with e lst)
  (if (null? lst) 
      nil
      (cons (cons e (car lst)) 
	    (match-with e (cdr lst)))))

(all-pairs (list 1 2 3) (list 4 5 6))

* order of growth time O(n^2)
* order of growth space O(n^2)

--------------------------------------------

* whats the minimum number of cons cells needed to store n items?