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 ( . ) * 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?