CS61A Lecture 8Clicker Test Cons and Listscons makes pairsLists are made with pairs!Make the Empty List the cdrMake the Empty List the carDotsSlide 9Practice Removing DotsSlide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18SolutionAccessing ElementsThe Empty List w/ car & cdrHow do you get the 2?How do you get the 3?Scheme is BEAUTIFUL!We don’t need no stinkin’ pairsTry It!List MethodslistappendSlide 30The truth about appendconsSlide 33Data AbstractionData Abstraction GoalsVery Happy Code Use the right one or it is a DAVSlide 38Implement se2Modify this to work with lists (without sub-lists)Slide 41map2 (like every)The real mapmapSlide 45Slide 46CS61A Lecture 82011-06-30Colleen LewisClicker Test Do you read the homework/disc/lab solutions?A)YesB)NoC)SometimesCons and ListsDEMOcons makes pairsPairscar cdr conscar cdrConstructorsSelectorsLists are made with pairs!STk> (define a (list 1 2 3 4))1car cdr2car cdr3car cdr4car cdraSTk> (define b (list 1 2))1car cdr2car cdrbMake the Empty List the cdrSTk> (cons 2 ‘())(2)2car cdrMake the Empty List the carSTk> (cons ‘() ‘())(())()car cdrDotsSTk> (cons 1 2)(1 . 2)STk> (cons 1 ‘())(1)STk> (cons 1 ‘())(1 .( )) 1car cdr1 2car cdrDotsSTk> (cons 1 ‘())(1 . ()) (1)STk> (cons 1 (cons 2 ‘()))(1 . (2 .( )))(1 2)1car cdr1car cdr2car cdrPractice Removing Dots(cons (cons 1 '()) (cons 2 (cons (cons 3 4) (cons 5 '()))))A) Draw the boxesB) What scheme would printC) Write it with dotsD) Invent a new puzzleE) Stuck!!!Practice Removing Dots(cons (cons 1 '()) (cons 2 (cons (cons 3 4) (cons 5 '()))))1car cdr5car cdrPractice Removing Dots(cons (cons 1 '()) (cons 2 (cons (cons 3 4) (cons 5 '()))))1car cdr5car cdr3 4car cdrPractice Removing Dots(cons (cons 1 '()) (cons 2 (cons (cons 3 4) (cons 5 '()))))1car cdr5car cdr3 4car cdrcar cdrPractice Removing Dots(cons (cons 1 '()) (cons 2 (cons (cons 3 4) (cons 5 '()))))1car cdr5car cdr3 4car cdrcar cdrPractice Removing Dots(cons (cons 1 '()) (cons 2 (cons (cons 3 4) (cons 5 '()))))5car cdr3 4car cdrcar cdr1car cdrPractice Removing Dots(cons (cons 1 '()) (cons 2 (cons (cons 3 4) (cons 5 '()))))5car cdr3 4car cdrcar cdr1car cdr2car cdrPractice Removing Dots(cons (cons 1 '()) (cons 2 (cons (cons 3 4) (cons 5 '()))))5car cdr3 4car cdrcar cdr1car cdr2car cdrPractice Removing Dots(cons (cons 1 '()) (cons 2 (cons (cons 3 4) (cons 5 '()))))5car cdr3 4car cdrcar cdr1car cdr2car cdrcar cdrSolutioncar cdr2car cdr car cdr5car cdr1car cdr3 4car cdr((1) 2 (3 . 4) 5)((1.()).(2.((3.4).(5.()))))Accessing ElementsUsing car and cdrThe Empty List w/ car & cdrSTk> (define x (cons 2 ‘())xSTk> x(2)STk> (car x)2STk> (cdr x)() 2car cdrxHow do you get the 2?STk> (define a (list 1 2 3 4))1car cdr2car cdr3car cdr4car cdraA) (car (cdr a))B) (cdr (car a))C) (cdr (cdr (car a)))D) (car (cdr (cdr a)))E) (cdr (car (car a)))How do you get the 3?STk> (define a (list 1 2 (list 3 4) 5))1car cdr2car cdr car cdr5car cdra3car cdr4car cdrA) (car (car (cdr (cdr a))))B) (cdr (cdr (car (car a))))C) (cdr (car (cdr (car a))))D) (car (cdr (car (cdr a))))E) ???Scheme is BEAUTIFUL!We don’t need no stinkin’ pairs(define (cons x y) (lambda (which) (cond ((equal? which 'car) x) ((equal? which 'cdr) y) (else (error "Bad message" which)))))(define (car pair) (pair 'car))(define (cdr pair) (pair 'cdr))Try It!•Try to use this new cons! Does it work the same way as before? A)YesB)NoC)I don’t knowList Methodslist•Takes any number of arguments and puts them in a listappend•Takes two lists and turns them into one•Both arguments MUST be listsappend•Examples–(append ‘(cat) ‘(dog)) ‘(cat dog)–(append ‘(cat) ‘()) ‘(cat) –(append ‘() ‘(dog)) ‘(dog)–(append ‘(cat) ‘(())) ‘(cat ()) –(append ‘(()())‘(dog)) ‘(() () dog)The truth about appendSTk> (define a (list 1 2))STk> (define b (list 3 4 5))STk> (define c (append a b))3car cdr4car cdr5car cdrb1car cdr2car cdrc1car cdr2car cdracons•Takes two arguments•If the second arg is a list–Makes the first arg the car of the new list–Makes the second arg the cdr of the new listcons•Examples–(cons ‘cat ‘( dog )) ‘(cat dog) –(cons ‘(cat) ‘( dog )) ‘((cat) dog) –(cons ‘cat ‘()) ‘(cat) –(cons ‘() ‘( () dog )) ‘(() () dog) –(cons ‘(cat) ‘dog ‘((cat) . dog)Data AbstractionData Abstraction Goals•To talk about things using meaning not how it is represented in the computer•To be able to change how it is represented in the computer without people who use our program caringVery Happy Code (define (total hand)(if (empty? hand)0(+ (rank (one-card hand))(total (remaining-cards hand) ))))(define (rank card) (butlast card))(define (suit card) (last card))(define (one-card hand) (last hand))(define (remaining-cards hand) (bl hand))(define (make-card rank suit)(word rank (first suit)))(define make-hand se)lastData Abstraction Violation(D.A.V.)Use the right one or it is a DAVsentence & word stufflist stufffirst carbutfirst cdrlastbutlastUse the right one or it is a DAVsentence & word stufflist stuffempty? null?sentence? list?item list-refsentence append, cons, listImplement se2(define (se2 a b) (cond ((and (word? a) (word? b)) (list a b)) ((word? a) (cons a b)) ((word? b) (append a (list b))) (else (append a b))))Modify this to work with lists (without sub-lists)(define (square-sent sent) (if (empty? sent) sent (sentence (square (first sent)) (butfirst sent))))Modify this to work with lists (without sub-lists)(define (square-sent sent) (if (empty? sent) sent (sentence (square (first sent)) (butfirst sent))))null?carcdrCONSmap2 (like every)(define (map2 fn lst) (if (null? lst) lst (cons (fn (car lst)) (map2 fn (cdr lst)))))STk> (map2 square ‘(1 2 3 4))(1 4 9 16)The real map(map procedure list1 list2…)•procedure –a procedure that takes in some # of arguments•Some # of lists–The number of lists MUST match the number of arguments that the procedure takesmap(define (add-2-nums x y)(+ x y))(map add-2-nums ‘(1 2 3) ‘(4 5 6)) ‘(5 7 9)map(define (add-3-nums x y z)(+ x y z))(map add-3-nums ‘(1 2 3) ‘(4 5 6) ‘(7 8 9)) ‘(12 15 18)map(map cons ‘(1 2 3) ‘((4) (5) (6))) ‘((1 4) (2 5) (3
View Full Document
Unlocking...