--------------------------------------- Tutorial notes #4 for 3/5 or 3/6/2007 TA: Stephen McCamant Email: smcc@mit.edu Location: 36-113A or 36-115 http://people.csail.mit.edu/smcc/6.001-sp07/ ---------------------------------------- Quiz 1 logistics You may bring two 8.5"x11" sheets of notes. Regular time: 7:30-9:30pm Thursday Last names A-I: 4-370 J-R: 4-270 S-Z: 4-163 Conflict time: 7:30-9:30pm Wednesday (You should have already emailed Donna dkauf@mit.edu) Last names A-R: 2-190 S-Z: 32-141 Remaining review session: Monday, 7pm in 32-155, with the LAs ---------------------------------------- Project 1 debrief / discussion - Did it take longer than you expected? - Space order of growth confusing? - Write your own test cases! - What are good/bad test cases? Other questions? Project 2 is already out: take a look at it ---------------------------------------- HOPs: repetition (define (identity x) x) ;; Like in recitation, not lecture (define (compose f g) (lambda (x) (f (g x)))) ((deriv square) 10);-> about 20(((n-times 2 deriv) square) 10);-> about 2(define (n-times n f) (cond ((= n 0) __________) (_______ (error "Can't take inverse")) (else (_________ (n-times ________ ______) ________))))(define (n-times n f) (cond ((= n 0) identity) ((< n 0) (error "Can't take inverse")) (else (compose (n-times (- n 1) f) f))))(define (incr x) (+ x 1)) (define (add a b) ((n-times ______ ______) ______))(define (add a b) ((n-times a incr) b))(define (mult a b) ((n-times ____ ________________) _____))(define (mult a b) ((n-times a (lambda (x) (+ x b))) 0))---------------------------------------- HOPs: map, filter, fold-right Suppose that we've defined lst as follows: (define lst (list 3 1 4 1 5 9 2 6 5)) What expression using map, filter, and fold-right would you use to get the following results? (30 10 40 10 50 90 20 60 50);-> (map (lambda (x) (* x 10)) lst)(3 1 1 5 9 5);-> (filter odd? lst)((3 3) (1 1) (4 4) (1 1) (5 5) (9 9) (2 2) (6 6) (5 5));-> (map (lambda (x) (list x x)) lst)32400 ;; the product of the elements;-> (fold-right * 1 lst)((3) (1) (1) (5) (9) (5));-> (map list (filter odd? lst))(3 3 1 1 4 4 1 1 5 5 9 9 2 2 6 6 5 5);-> (fold-right append '() (map (lambda (x) (list x x)) lst))(3 (1 (4 (1 (5 (9 (2 (6 (5 "Burma-Shave")))))))));-> (fold-right list "Burma-Shave" lst)(3 1 4 1 5 9 2 6 5) ; multiple answers;-> (map identity lst);-> (filter (lambda (x) #t) lst);-> (fold-right cons '() lst)---------------------------------------- Cross-product The cross product of two lists is all the pairs (2-element lists) with the first element from the first list and second element from the second list. For instance: (cross-product (list 1 2 3) (list 3 5 7)) -> ((1 3) (1 5) (1 7) (2 3) (2 5) (2 7) (3 3) (3 5) (3 7)) Write cross-product using some higher-order procedures.(define (cross-product as bs) (fold-right append '() (map (lambda (a) (map (lambda (b) (list a b)) bs)) as)))---------------------------------------- Discussion questions on space order of growth True or false: if a procedure is iterative, its space usage is constant.;-> trueTrue or false: if a procedure is recursive, its space usage is linear.;-> false (it could be more or less)True or false: the time order of growth of a procedure is always at least as big as its space order of growth.;-> trueIf procedure "f" takes Theta(n) time, and procedure "g" calls "f" Theta(n) times, what is g's order of growth for time?;-> Theta(n^2)If procedure "f" takes Theta(n) space, and procedure "g" calls "f" Theta(n) times with recursion, what is g's order of growth for space?;-> Theta(n) (you can reuse space)Consider the following function: (define (func n) (cond ((zero? n) 0) ((even? n) (+ 1 (func (- n 1)))) ((odd? n) (func (- n 1))))) Is this recursive or iterative?;-> recursive (there's no such thing as "sometimes iterative")What is its space order of growth?;-> Theta(n/2) = Theta(n)---------------------------------------- All you need is HOPs In my continuing quest to prove that pairs don't need to be a primitive data type, I started to write an implementation of pairs using higher-order procedures: (define (my-car p) (p 0)) (define (my-cdr p) (p 1)) How should I write my-cons?(define (my-cons a b) (lambda (m) (if (= m 0) a b)))Also, I want to get rid of booleans. (define (my-if cond then else) (cond then else)) What definitions of my-true and my-false go with this?(define (my-true then else) then) (define (my-false then else) else)---------------------------------------- What are the types of the following procedures? (Use A, B, C, etc.) identity;-> A -> Amap;-> (A -> B), List<A> -> List<B>filter;-> (A -> boolean), List<A> -> List<A>fold-right;-> (A, B -> B), B, List<A> -> B(define (k x) (lambda (y) x));-> A -> (B -> A)(define (s x y) (lambda (z) ((x z) (y z))));-> (A -> (B -> C)), (A -> B) -> (A -> C)(define i (s k k));-> A -> A