CS61A&Summer&2011&–&Kevin,&Stephanie,&Hamilton,&Eric,&and&Phill&–¬es&courtesy&of&Justin&Chen/Chung&Wu& & 1&CS61A&Notes&–&Week&4:&Pairs&and&lists,&data&abstraction&Pair&Up!&&QUESTIONS:&What&do&the&following&evaluate&to?&&IN&CLASS :&&(define u (cons 2 3)) (define w (cons 5 6)) (define x (cons u w)) (define y (cons w x)) (define z (cons 3 y)) &1. u, w, x, y, z (write them out in Scheme’s notation) u: (2 . 3) w: (5 . 6) x: ((2 . 3) 5 . 6) y: ((5 . 6) (2 . 3) 5 . 6) z: (3 (5 . 6) (2 . 3) 5 . 6) 2. (car y) (5 . 6) 3. (car (car y)) 5 4. (cdr (car (cdr (cdr z)))) 3 5. (+ (cdr (car y)) (cdr (car (cdr z)))) 12 EXTRA&PRACTICE:& 6. (cons z u) ((3 (5 . 6) (2 . 3) 5 . 6) 2 . 3) 7. (cons (car (cdr y)) (cons (car (car x)) (car (car (cdr z))))) ((2 . 3) 2 . 5) &Don’t&You&Mean&sentence?&&QUESTIONS:&&IN&CLASS :&&1. Define&a&procedure&list-4&that&takes&in&4&elements&and&outputs&a&list&equ ivalen t &to&one&created&by&calling&list&(use&cons!).&& (define (list-4 e1 e2 e3 e4) (cons e1 (cons e2 (cons e3 (cons e4 ‘()))))) &&&&&CS61A&Summer&2011&–&Kevin,&Stephanie,&Hamilton,&Eric,&and&Phill&–¬es&courtesy&of&Justin&Chen/Chung&Wu& & 2&2. Write&num-satisfies&that&takes&in&a&sentence&and &a&pred icate ,&and&re turn s&the &number&of&elements&in&the &sen ten ce&that&satisfy&the&given&predicate.&USE&ONLY&HIGHER&ORDER&FUNCTIONS;&DO&NOT&USE&RECURSION.&&(define (num-satisfies sent pred) (count (keep pred sent)))&&3. Rewrite&question&2&to&take&in&a&list&and&a&predicate.&USE&ONLY&HIGHER&ORDER&FUNCTIONS;&DO&NOT&USE&RECURSION.& (define (num-satisfies ls pred) (length (filter pred ls)))&&4. Suppose&we&have&x&bound&to&a&mysterious&element.&All&we&know&is&this:&(list? x) => #t (pair? x) => #f What&is&x?&&The empty list&5. Add&in&procedure&calls&to&get&the&desired&results.&All&the&parens&below&represent&lists.&Blanks&can&be&left&blank:&&( cons ‘a ‘(b c d e) ) => (a b c d e) ( append ‘(cs61a is) (list ‘cool ) ) => (cs61a is cool) ( cons ‘(back to) ‘(save the universe) ) => ((back to) save the universe) ( cons ‘(I keep the wolf) (car ‘((from the door)) ) ) => ((I keep the wolf) from the door) &EXTRA&PRACTICE:&&6. Write&all-satisfies&that&takes&in&a&sentence &and &a&pre dica te,&an d&re turn s&#t&if&an d &o n ly &if&a ll&o f &th e &e lements&in&th e &lis t &satisfy&the&given&predicate.&USE&ONLY&HIG H ER &OR D ER &FU NC TIO N S;&D O &NO T &US E&RE CU R SIO N.&&(define (all-satisfies sent pred) (empty? (keep (lambda (w) (not (pred w))) sent))&(define (all-satisfies sent pred) (= (count (keep pred sent)) (count sent)))&&7. Rewrite&question&3&to&take&in&a&list&and&a&predicate.&USE&ONLY&HIGHER&ORDER&FUNCTIONS;&DO&NOT&USE&RECURSION.&&(define (all-satisfies ls pred) (null? (filter (lambda (w) (not (pred w))) ls))&(define (all-satisfies ls pred) (= (length (filter pred ls)) (length sent))) &8. Write&repeat-evens&that&takes&in&a&sentenc e&o f&numbers&and&repeats &the&e ve n&ele m e nts&tw ice .&USE &ON LY &HIG H ER&O R D ER&FUNCTIONS;&DO&NOT&USE&RECURSION .&&(define (repeat-evens sent) (every (lambda (n) (if (even? n) (se wd wd) wd)) sent))&&9. (Hard!)&Rew rite &qu es tion &8&to &w o rk &on &a&list&o f&nu m b ers.&U SE&O N LY&HIG H ER&O RD ER &FU NC TIO NS ;&DO &NO T&U SE&R ECU R SIO N. & (define (repeat-evens ls) (accumulate append ‘() (map (lambda (n) (if (even? n) (list n n) (list n))) ls)))&&10. Define&a&procedure&(insert-after item mark ls)&which&inserts&item&after&mark&in&ls.&&(define (insert-after item mark ls) (cond ((null? ls) ‘()) ((equal? (car ls) mark) (cons (car ls) (cons item (cdr ls)))) (else (cons (car ls) (insert-after item mark (cdr ls))))))CS61A&Summer&2011&–&Kevin,&Stephanie,&Hamilton,&Eric,&and&Phill&–¬es&courtesy&of&Justin&Chen/Chung&Wu& & 3&&Box&and&Pointer&Diagrams&&QUESTIONS:&Evaluate&the&following,&and&draw&a&boxdanddpointer&diagram&for&each.&(Hint:&It&may&be&easier&to&draw&the&boxdanddpointer&diagram&first.)&&IN&CLASS :&&1. (cons (cons 1 2) (cons 3 4)) &((1 . 2) 3 . 4)&&2. (cons ‘((1 a) (2 o)) ‘(3 g)) &(((1 a) (2 o)) 3 g)&&3. (list ‘((1 a) (2 o)) ‘(3 g)) (((1 a) (2 o)) (3 g)) 4. (append ‘((1 a) (2 o)) ‘(3 g)) ((1 a) (2 o) 3 g) EXTRA&PRACTICE:& 5. (cdr (car (cdr ‘(((1) 3) (4 (5 6))) ))) ((5 6)) 6. (map (lambda (fn) (cons fn (fn 6))) (list square 1+ even?)) &((#[square] . 36) (#[1+] . 7) (#[even?] . #t))&&(Slightly)&Harde r&L ists&&QUESTIONS:&&IN&CLASS :&&1. Define&a&procedure&(remove item ls)&that&takes&in&a&list&and&returns&a&new&list&with&item&removed&from &ls.&&(define (remove item ls) (cond ((null? ls) ‘()) ((equal? item (car ls)) (remove item (cdr ls))) (else (cons (car ls) (remove item (cdr ls))))))&&2. Define&a&procedure&(unique-elements ls)&that&takes&in&a&list&and&returns&a&ne w &list&withou t&dup licates .&You ’ve&already&done&this&with&remove-dups,&and&it&use d&t o&d o &th is: &(remove-dups ‘(3 5 6 3 3 5 9 8)) ==> (6 3 5 9 8) where&the&last&occurrence&of&an&element&is&kept.&We’d&like&to&keep&the&first&occurrences:&(unique-elements ‘(3 5 6 3 3 5 9 8)) => (3 5 6 9 8) Try&doing&it&without&u sing&member?.&You&might &w an t&to &u se &remove& ab ove.&&(define (unique-elements ls) (if (null? ls) ‘() (cons (car ls) (unique-elements (remove (car ls) (cdr ls))))))&CS61A&Summer&2011&–&Kevin,&Stephanie,&Hamilton,&Eric,&and&Phill&–¬es&courtesy&of&Justin&Chen/Chung&Wu& & 4&3. Define&a&procedure&(interleave ls1 ls2)&that&takes&in&two&lists&and&returns&one &list&with&elements&from&both&lists&interleav e d .&S o ,&(interleave ‘(a b c d) (1 2 3 4 5 6 7)) => (a 1 b 2 c 3 d 4 5 6 7) (define (interleave ls1 ls2) (cond ((null? ls1) ls2) ((null? ls2) ls1) (else (cons (car ls1) (interleave ls2 (cdr ls1)))))) EXTRA&PRACTICE:& 4. Define&a&procedure&(count-unique ls)&which,&given&a&list&of&elements,&returns&a&list&of&pairs&whose&car&is&an&element&and&whose&cdr&is&its&number &o f&o c c u r re nces&in&the &list .&F o r &e x a mple,&(count-unique ‘(a b b b c d d a e e f a a)) => ((a . 4) (b . 3) (c . 1) (d . 2) (e . 2) (f . 1)) You&might&want&to&use&unique-elements&and&count-of&defined&above.&&(define (count-unique ls) (map (lambda(x) (cons x (count-of x ls))) (unique-elements ls)))& 5. Write&a&procedure&(apply-procs procs
View Full Document
Unlocking...