Thank you to the students who showed up so that we get a review session that other students can read over later.

Finding This Page

• Go to http://www.cs.grinnell.edu/~rebelsky/
• Click on "CSC 151" at the top of the page
• Click on "EBoard" in the "Current" row

Overview

• About the quiz
• Your questions.
• Sample quiz questions.
• More of your questions.

The Quiz

Topics

• Recursion

Types of recursive procedures you've seen/written

• Tally (e.g., tally dark elements)
• Extract/remove elements (e.g., remove/preserve dark elements)
• Find extreme value (e.g., find darkest elements)
• Combine elements (e.g., add red components, sum, product)

Types of questions

• Given this code, what is the output?
• Show steps.
• Write a procedure.
• Document this procedure
• Fill in the blanks.
• Identify errors.

Your Questions

Will verifying preconditions be on the quiz?

No.

Do we still need to know what a precondition is?

Yes.

Could we look at the code from the recursion lab, problem 3?

An answer

    (define list-length
      (lambda (lst)
        (if (null? lst)
            0
            (+ 1 (list-length (cdr lst))))))

Thought process: What's a simple case? Empty list! What if we can make someone else count a smaller list? Have them count everything but the first element, then add 1 to their result.

How does it work? Normal Scheme: Work inside-out, substitute body of procedure for call. Do the test for if first. (In the following, "=>" is supposed to be an arrow to show what comes next.)

    (list-length '(3 1 "hello"))
    => (if (null? '(3 1 "hello")) 0 (+ 1 (list-length (cdr '(3 1 "hello"))))
    => (if #f 0 (+ 1 (list-length (cdr '(3 1 "hello")))))
    => (+ 1 (list-length (cdr '(3 1 "hello"))))
    => (+ 1 (list-length '(1 "hello")))
    => (+ 1 (if (null? '(1 "hello")) 0 (+ 1 (list-length (cdr '(1 "hello"))))))
    => (+ 1 (if #f 0 (+ 1 (list-length (cdr '(1 "hello"))))))
    => (+ 1 (+ 1 (list-length (cdr '(1 "hello")))))
    => (+ 1 (+ 1 (list-length '("hello"))))
    => (+ 1 (+ 1 (if (null? '("hello")) 0 (+ 1 (list-length (cdr '("hello")))))))
    => (+ 1 (+ 1 (if #f 0 (+ 1 (list-length (cdr '("hello")))))))
    => (+ 1 (+ 1 (+ 1 (list-length (cdr '("hello"))))))
    => (+ 1 (+ 1 (+ 1 (list-length '()))))
    => (+ 1 (+ 1 (+ 1 (if (null? '()) 0 (+ 1 (list-length (cdr '())))))))
    => (+ 1 (+ 1 (+ 1 (if #t 0 (+ 1 (list-length (cdr '())))))))
    => (+ 1 (+ 1 (+ 1 0)))
    => (+ 1 (+ 1 1))
    => (+ 1 2)
    => 3

When we run recursive procedures according to the rules of Scheme, we tend to build up a large amount of "future" work, hit the base case, and then do the future work.

What's a general thought process for designing recursive procedures over lists?

First, what's a case that even a CEO can do by themselves? (Usually: empty list, or a singleton list.) E.g., sum: empty list has a sum 0. Singleton list has a sum of the one value in the list.

Suppose we've solved the case for the cdr, how does that contribute to the overall answer? E.g., sum: If we've summed the remaining numbers, we just need to add the first number

Sample Quiz Questions

Showing Steps

As you may recall, in Scheme, evaluation happens from the inside out. We also "evaluate" a procedure call by substituting in the body of the procedure, with the formal parameters replaced by the actual paramters. Recursive procedures take advantage of these evaluation strategis by building up parts of the expression that get evaluated "later".

Consider the following definition of product.

(define product
  (lambda (lst)
    (if (null? lst)
        1
        (* (car lst) (product (cdr lst))))))

Here are the first few steps of the evaluation of (product '(4 2 3))

(product '(4 2 3))
=> (if (null? '(4 2 3)) ...)
=> (* (car '(4 2 3)) (product (cdr '(4 2 3))))
=> (* 4 (product (cdr '(4 2 3))))
=> (* 4 (product '(2 3)))
=> (* 4 (if (null? '(2 3) ...)))

Show the remaining steps

Identifying Errors

Consider the following implementation of largest, which is intended to find the largest element in a list.

(define largest
  (lambda (lst)
    (if (null? lst)
        0
        (max (car lst) (largest lst)))))

There are at least two errors in this procedure. Identify them and indicate how to fix them.

A Solution

• We need the largest of the cdr, not the largest of the same list. You'll find that if we use this, it will never stop and DrRacket will crash and possibly even delete all of your work from all eternity.
• 0 seems wrong for the base case, since we don't know that it's in the list.
• Whoops. There is no largest value in an empty list. When you can't answer the question for an empty list, your test should probably be "does it have one element", rather than "does it have no elements"?

Tallying Strings

Fill in the blanks in the following procedure, which tallies the number of strings in a list.

(define tally-strings
  (lambda (lst)
    (cond
      [__________
       0]
      [__________
       (+ 1 (tally-strings (cdr lst)))]
      [else
       _______________________________])))

Tallying Strings, Revisited

Fill in the blanks in the following procedure, which tallies the number of strings in a list.

(define tally-strings
  (lambda (lst)
    (if (null? lst)
        _______
        (+ (if __________ 1 0)
           (tally-strings (cdr lst))))))

Tallying Strings, Re-Revisited

Fill in the blanks in the following procedure, which tallies the number of strings in a list.

(define tally-strings
  (lambda (lst)
    (if _______
        0
        (let ([tally-car ___________]
              [tally-cdr (tally-strings ________)])
          (+ tally-car tally-cdr)))))

Selecting Strings

Fill in the blanks in the following procedure, which selects all the strings in a list.

(define select-strings
  (lambda (lst)
    (cond
      [(null? lst)
       _________]
      [(string? (car lst))
       (__________________ (select-strings (cdr lst)))]
      [else
       _______________________________])))

A Solution

Issue 1: What value do we return in the base case? The list of all the strings in the empty list contains ...?

Issue 2: Suppose the car of the list is a string and we've gotten all the strings in the cdr. What should we do? Example: (select-strings '("a" 2 "c" '() "d" 4 5 "e")), "a" is a string. '("c" "d" "e") are all the remaining strings. What next?

Issue 3: What should we do if the car is not a string? E.g., '(select-strings '(1 "a" 2 "c" '() "d")).

(define select-strings
  (lambda (lst)
    (cond
      [(null? lst)
       null]
      [(string? (car lst))
       (cons (car lst) (select-strings (cdr lst)))]
      [else
       (select-strings (cdr lst))])))

Whatzitdo?

Write the 6P-style documentation for the following procedure.

(define whatzitdo
  (lambda (x)
    (if (null? (cdr x))
        (car x)
        (let ([y (car x)]
              [z (whatzitdo (cdr x))])
          (if (< y z)
              y
              z)))))

A Solution

• Finds the smallest value.
• Precondition: List of real numbers

Whatzitdo?

Write the 6P-style documentation for the following procedure.

(define whatzitdo
  (lambda (x)
    (if (null? x)
        null
        (cons (irgb-bluer (car x))
              (whatzitdo (cdr x))))))

A Solution

• x must be a list of irgb-colors
• it makes each element bluer
• and returns a new list
• A complicated way to write (map irgb-bluer x).

Largest Absolute Value

Suppos we want a procedure that finds the value in a list that has the largest absolute value. For example,

> (largest-absolute-value (list 5 2 -3 4))
5
> (largest-absolute-value (list 5 2 -3 4 -7 1))
-7
> (largest-absolute-value (list 0))
0
> (largest-absolute-value '())
ERROR
> (largest-absolute-value (list 3 19))
19

Finish the definition of largest-absolute-value.

 (define largest-absolute-value
   (lambda (lst)
     (let ([current (car lst)])
       (if _____________
           current
           (let ([alternate (largest-absolute-value (cdr lst))])
             (if ______________
                 current
                 alternate))))))

A solution

Base case test: If there's only one element. One way to test that (= 1 (length lst)). But that's inefficient. So we prefer (null? (cdr lst))

 (define largest-absolute-value
   (lambda (lst)
     (let ([current (car lst)])
       (if (null? (cdr lst))
           current
           (let ([alternate (largest-absolute-value (cdr lst))])
             (if (> (abs current) (abs alternate))
                 current
                 alternate))))))

We could also have written this as follows, but that repeats code.

 (define largest-absolute-value
   (lambda (lst)
       (if (null? (cdr lst))
           (car lst)
           (let ([alternate (largest-absolute-value (cdr lst))])
             (if (> (abs (car lst)) (abs alternate))
                 (car lst)
                 alternate)))))

Additional Questions

Can we talk about copy/paste?