recitation 5: cons/car/cdr/list

--------------------------------------------
means of combination: compound data!
means of abstraction: data abstraction!
  contract for glue & unglue
  don't need to know implementation details
     (black box)

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)))
 
  no, you follow the normal rules of evaluation
  (evaluating the expression above results in an error)

--------------------------------------------
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)))


 
  * don't forget to label your diagrams with any defined variables
    
  * arrows that point to cons cells can point to any part of the outer box,

  * you can write numbers inside the boxes, or point to them outside the box

  * don't forget to put something in each box (don't forget to put a
    slash in the last box of a list)
 
--------------------------------------------
to print a cons structure:
  * each cons cell is printed ( <car> . <cdr> )
  * cross out any ". nil" 
  * cross out any ". (" and it's matching ")"
  * 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))))
   (1 . (2 . (3 4)))
   (1 . (2 3 4))
   (1 2 3 4)

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

The examples from above print out as follows:

a => (1 . 2)

b => ((1 . 2) . (1 . 2))
     ((1 . 2)  1 . 2)

c => ((1 . 2) . (1 . 2))
     ((1 . 2)  1 . 2)

d => (2 . nil)
     (2)

e => (#f . 2)

f => (2)

g => #f

h => (#f . #f)
     (#f)

i => (1 2 3 4)

j => (5 (3 4) (6 . 7))

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

       n-1 
    
--------------------------------------------
"cons-ing up a list"

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

(enumerate-interval 4 9) => (4 5 6 7 8 9)

* 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)))))

(length (list 1 3 4 7)) => 4

* 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"

Write cube-neighbor-diff:

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

(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))))))

the special form let:
(let ((a 5)
      (b 10)) 
  (+ a b))

using let:
(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)))))))