---------------------------------------
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