---------------------------------------
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.
;-> true
True 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.
;-> true
If 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 -> A
map
;-> (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