General Open Questions

What's on the quiz?

Your classmates' pictures.

Maybe one or two extra-credit problems.

Why don't we get to take a quiz on recursion like the other section?

I always have to sneak in one "know your classmates" quiz. This seemed like a good time.

How do I write a local procedure so that I can apply the fold pattern for rgb-darkest?

The fold pattern: Given an operation that combines two values into a single value, generalize it to work with a list of values. * sum: We know how to add two values; we can now add a list of values * list-join: We know how to append two lists; we can now append an arbitrary number of lists * Goal Given a list of colors, find the darkest

The pattern

    (define FOLDED-OP
      (lambda (lst)
         ; If the list has one value
        (if (null? (cdr lst))
            ; Use that value
            (car lst)
            ; Otherwise, recurse on the cdr and combine with the
            ; car using the operation
            (OP (car lst) (FOLDED-OP (cdr lst))))))

Let's write irgb-darkest.

    (define irgb-darkest
      (lambda (lst)
         ; If the list has one value
        (if (null? (cdr lst))
            ; Use that value
            (car lst)
            ; Otherwise, recurse on the cdr and combine with the
            ; car using the operation
            (OP (car lst) (irgb-darkest (cdr lst))))))

The OP should be "given two irgb colors, find the darker of the two".

    (define irgb-darker
      (lambda (color1 color2)
        (if (< (irgb-brightness color1) (irgb-brightness color2))
            color1
            color2)))

We could also make it local

    (define irgb-darkest
      (let ([irgb-darker (lambda (color1 color2)
                            (if (< (irgb-brightness color1) 
                                   (irgb-brightness color2))
                                color1
                                color2))])
        (lambda (lst)
           ; If the list has one value
          (if (null? (cdr lst))
              ; Use that value
              (car lst)
              ; Otherwise, recurse on the cdr and combine with the
              ; car using the operation
              (irgb-darker (car lst) (irgb-darkest (cdr lst))))))

Here's a potential problem with the fold pattern. Can we use the pattern to do difference (generalize subtract?)

    (define difference
      (lambda (lst)
         ; If the list has one value
        (if (null? (cdr lst))
            ; Use that value
            (car lst)
            ; Otherwise, recurse on the cdr and combine with the
            ; car using the operation
            (- (car lst) (difference (cdr lst))))))

    > (difference (list 1 2 3 4 5 6))
    -3

We expected -19 because 1 - 2 - 3 - 4 - 5 - 6 is -19. We got -3. Why? Because the way this is designed makes the operation right-associative.

We know how to make operations left-associative: Use a helper procedure. Should we write a left-associative difference and then find the pattern, or predict a pattern and the write the left-associative difference.

    ; Fold, but left
    (define FOLDED-OP
      (lambda (lst)
        (FOLDED-OP-HELPER (car lst) (cdr lst))))

    (define FOLDED-OP-HELPER
      (lambda (so-far remaining)
        (if (null? remaining)
            so-far
            (FOLDED-OP-HELPER (OP so-far (car remaining))
                              (cdr remaining)))))

    ; Fold, but left
    (define difference
      (lambda (lst)
        (difference-HELPER (car lst) (cdr lst))))

    (define difference-HELPER
      (lambda (so-far remaining)
        (if (null? remaining)
            so-far
            (difference-HELPER (- so-far (car remaining))
                               (cdr remaining)))))

Yay!

• Ask Sam questions.
• Find another interesting problem and solve it.
• Look for other generalized patterns.
• Skip three weeks and see how to do this really concisely.
• Talk about an exam problem. (It won't stay on the eboard.)

Sample Quiz Questions for Recursion Quiz