6.001/Recitation 8

Rob Speer

Contents 1 Revisiting the brain teaser 2 Problems 3 Named let 4 A table of procedures with funny names 5 tree-manip: fold-right on crack 6 The master theorem

Revisiting the brain teaser

What's the type of (λ (f) (f f))?

I think it's best expressed as needing to be in two types simultaneously.

Problems

Evaluate these expressions, and give what they evaluate to (or "procedure" or "error"). If it's a simple value or a procedure, give its type. If it's a pair of any sort, draw a box and pointer diagram.

1. ((λ (x y) (x y)) (λ (z) (λ (a) (+ a z))) 8)

2. ((λ (x + y) (+ x y)) 3 * 5)

3. (let ((list (list list list)))
     (apply list))

4. (fold-left cons '(1 2 3))

Named let

Recursing in a part of a procedure with certain initial values can be done with a "let loop" instead of with a helper function. Here's a way to rewrite the iterative Fibonacci function:

(define (fib n)
  (let loop [(a 0) (b 1) (i 0)]
    (if (= i n) a
        (loop b (+ a b) (+ i 1)))))

A table of procedures with funny names

These are some very useful procedures for manipulating the representations of objects.

	Compare by representation	Compare by identity	Compare by value
Test equality	equal?	eq?	eqv?
Find an item in a list	member	memq	memv
Find an item in a mapping	assoc	assq	assv

tree-manip: fold-right on crack

Let's generalize the idea of recursing over a tree, like fold generalizes recursing over a list.

(define (tree-manip tree init leaf accum)
  (cond ((null? tree) init)
        ((not (pair? tree)) (leaf tree))
        (else (accum
                (tree-manip (car tree) init leaf accum)
                (tree-manip (cdr tree) init leaf accum)))))

Here's a tree to use this on: (define test-tree '(1 (2 (3 (4) 5) 6) 7))

Now, using appropriate arguments to tree-manip:

1. Count the number of leaves in the tree.

2. Apply a certain procedure, proc, to each leaf of the tree. (This could be called tree-map.)

3. Flatten the tree, so that test-tree becomes (1 2 3 4 5 6 7).

4. Deep-reverse the tree, so that test-tree becomes (7 (6 (5 (4) 3) 2) 1).

5. Take the product of all the leaves of the tree.

6. Remove the even-valued leaves of the tree, leaving the structure intact. That is, test-tree becomes (1 ((3 () 5)) 7).

7. If there is a subtree of the tree whose leaves add up to less than 10, replace it by its total. For example, (((1 2) (2 3)) 8 (5 (3 4))) becomes (8 8 (5 7)). Don't worry about efficiency.

The master theorem

If you want, I can tell you a more rigorous way to figure out the runtime of a recursive algorithm, called the Master Theorem.