Laboratory: Recursion Basics

a. Read through sum so that you have a sense of how it accomplishes its purpose.

b. Verify that sum produces the same results as in the corresponding reading.

c. What value do you expect sum to produce for the empty list?

d. Check your answer experimentally.

e. What value do you expect sum to produce for a singleton list? (A “singleton list” is a list with only one value.)

f. Check your answer experimentally.

g. Try sum for a few other lists, too.

h. What do you expect the following to compute?

> (sum 1 2 3)

i. Check your answer experimentally.

a. Read through the definition of irgb-filter-out-dark to try to understand what it does.

b. Determine which colors in my-colors are dark with (map irgb-dark? my-colors).

c. Create a list of non-dark colors with (irgb-filter-out-dark my-colors).

d. Verify that all the resulting colors are not dark, using a technique similar to the one that you used in step b.

e. Find out the names of the non-dark colors with

> (map irgb->color-name (irgb-filter-out-dark my-colors))

Suppose the length procedure, which computes the length of a list, were not defined. We could define it by recursing through the list, counting 1 for each value in the list. In some sense, this is much like the definition of sum, except that we use the value 1 rather than the value of each element.

a. Using this idea, write a recursive procedure, (list-length lst) that finds the length of a list. You may not use length in defining list-length.

b. Check your answer on a few examples: the empty list, the list of colors you created, and a few more lists of your choice.

Write a recursive procedure, (product nums), that computes the product of a list of numbers. You should feel free to use sum as a template for product. However, you should think carefully about the base case.

The length procedure counts the number of values in a list. What if we don't want to count every value in a list? For example, suppose we only want to count the dark values in a list of colors. In this case, we still recur over the list, but we sometimes count 1 (when the color is dark) and sometimes count 0 (when the color is not dark).

a. Using this idea, write a procedure, (irgb-tally-dark colors), that, given a list of colors, counts how many are dark. Note: You should not call list-length, length, or irgb-filter-dark in your solution. Instead, use the ideas behind these functions in crafting your own recursive solution.

b. Check how your procedure functions on a variety inputs. For example, you might start with the following

> (irgb-tally-dark null)
> (irgb-tally-dark (map color-name->irgb (list "black" "black" "white")))
> (irgb-tally-dark (map color-name->irgb (list "white" "white" "black" "black")))
> (irgb-tally-dark (map color-name->irgb my-colors))

In the past, we've found it useful to find the average of two colors. Let's consider how we might find the average of a list of colors. First, we would need to find the number of colors in the list. That's easy, we just use the length procedure. Next, we need to find the sum of each component. That's a bit harder, but let's suppose we can do it. We next divide each sum by the length, and get the average of that component. Finally, we put it all together with irgb-new.

That is, we might write

(define irgb-list-average
  (lambda (colors)
    (let ([count (length colors)])
      (irgb (/ (sum-red colors) count)
            (/ (sum-green colors) count)
            (/ (sum-blue colors) count)))))

Of course, for this to work, we need to write sum-red, sum-blue, and sum-green. For now, we'll write one of the three. (One we've written that one, the other two should be obvious.)

a. Write a procedure, (sum-red colors), that computes the sum of the red components in a list of colors. You should use direct recursion in your definition sum-red. (That is, you should use recursion, and not take advantage of the already-written sum procedure, other than as a template for your code.) You may want to base your definition on the definition of sum.

b. Check your procedure on a list of a single color.

c. Check your procedure on the my-colors list you wrote earlier.

d. It is possible to write sum-red without using direct recursion. How? An appropriate combination of map and sum. Try doing so.

If you can't find a solution, look at the notes on this exercise.

(a) Write a procedure, (find-first-skip lst) that takes a list of symbols as a parameter and returns the index of the first instance of the symbol skip in lst, if skip appears in lst. Your procedure may return an error if the symbol skip does not appear in the list.

> (find-first-skip (list 'hop 'skip 'and 'jump))
1
> (find-first-skip (list 'skip 'hop 'jump 'skip 'and 'skip 'again))
0
> (find-first-skip (list 'hop 'to 'work 'jump 'to 'school 'but 'never 'skip 'class))
8

(b) Extend your find-first-skip procedure so that, when the symbol skip is not in the list, the procedure produces #f rather than an error.

> (find-first-skip (list 'hop 'to 'work 'jump 'to 'school 'but 'never 'skip 'class))
8
> (find-first-skip (list 'hop 'and 'jump))
#f

Write a procedure, (index-of val lst) that takes a value and a list of values as its parameters and returns the index of the first instance of val in lst, if the value appears in the list. If the value does not appear, index-of should return #f.

> (index-of 'skip (list 'hop 'skip 'and 'jump))
1
> (index-of 5 (list 5 4 3 2 1 2 3 4 5))
0
> (index-of "eraser" (list "pencils" "paper" "index cards" "markers" "ball-point pens"))
#f

Write and document a function (riffle first second) that produces a new list containing alternating elements from the lists first and second. If one list runs out before the other, then the remaining elements should appear at the end of the new list.

> (riffle (list 'a 'b 'c) (list 'x 'y 'z))
(a x b y c z)
> (riffle (list 'a 'b 'c) (iota 10))
(a 0 b 1 c 2 3 4 5 6 7 8 9)

We can use map to extract the red component of each color.

(map irgb-red colors)

That gives us a list of numbers, which we can sum with sum.

(sum (map irgb-red colors))

Putting it all together in a procedure, we get

(define sum-red
  (lambda (colors)
    (sum (map irgb-red colors))))

Return to the exercise.