CSC151.02 2010S Functional Problem Solving : Labs

Laboratory: List Recursion, Revisited


Summary: In this laboratory, you will continue to explore the use of recursion.

Reference

Preparation

a. Make a copy of list-recursion-revisited-lab.scm, which contains useful definitions for this lab.

b. Review the file to see what procedures and values are in the list.

Exercises

Exercise 1: Making Greys

In the code for this lab, you will see three lists of grey values with remarkably similar code. Can we generalize that code? We know how to make lists of numbers. And, once we have a list of numbers, we can certainly figure out what scale factor to use to make greys: It's 255 (or 256) divided by the largest value in the list of numbers. Putting it all together, we get

(define greys
  (lambda (vals)
    (let ((factor (/ 256 (largest vals))))
      (map (lambda (n) (rgb-new (* factor n) (* factor n) (* factor n)))
           vals))))

But how do we find the largest value in the list of numbers? As you've observed, (max val1 val2) computes the largest of val1 and val2. We want to generalize this procedure to work with a list of values.

a. Write (largest vals), a procedure that computes the largest value in a list of real numbers.

b. What results do you expect for the following expressions?

> (map rgb->string (greys (list 1 2 3 4)))
> (map rgb->string (greys (list 1 5 2 3 6 1)))
> (map rgb->string (greys (list 8 4 2 0)))

c. Check your answers experimentally.

d. Create some lists of shades of grey using iota rather than by building the list of numbers by hand.

Exercise 2: Joining Lists

You may recall that the procedure append takes as parameters two lists, and joins the two lists together. Let's generalize that procedure so that it works with more than two lists.

a. Write a procedure, lists-join, that, given a nonempty list of lists as a parameter, joins the member lists together using append.

> (list (list 1 2 3))
((1 2 3))
> (lists-join (list (list 1 2 3)))
(1 2 3)
> (list (list 1 2 3) (list 10 11 12))
((1 2 3) (10 11 12))
> (lists-join (list (list 1 2 3) (list 10 11 12)))
(1 2 3 10 11 12)
> (list (list 1 2 3) (list 10 11 12) (list 20 21))
((1 2 3) (10 11 12) (20 21))
> (lists-join (list (list 1 2 3) (list 10 11 12) (list 20 21)))
(1 2 3 10 11 12 20 21)
> (list null (list 1 2 3))
(() (1 2 3))
> (lists-join (list null (list 1 2 3)))
(1 2 3)
> (list (list 1 2 3) null)
((1 2 3) ())
> (lists-join (list (list 1 2 3) null))
(1 2 3)
> (lists-join (list null (list 1 2 3) null null null null (list 100 99 98) null))
(1 2 3 100 99 98)

Note: At first glance, it may be puzzling to work with a list of lists. However, you can disassemble that list just as you do any other list: the car of a list-of-lists is a list, the cdr of a list-of-lists is a list-of-lists, but with the first list removed.

Hint: Think about when you have a base case, what you do in the base case, and what to do with the result of the recursive case. (Remember, append is generally used to join two lists.)

b. Use lists-join to join some of the color lists your created in the preliminaries.

Exercise 3: Folding

Here are possible answers for exercises 1 and 2.

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

(define lists-join
  (lambda (lst)
    (if (null? (cdr lst))
        (car lst)
        (append (car lst) (lists-join (cdr lst))))))

You'll notice that both do a similar thing: They take a two-parameter procedure (max or append) and generalize it to a list of values. The process of repeatedly applying a two-parameter procedure so as to process a list is often called folding the procedure.

You'll also notice that they both lists-join and largest use similar code. When we identify a common structure for similar procedures, it can be helpful to generalize and then to explore that generalization. You will do so in this exercise.

a. Sketch a template of the common parts of lists-join and largest (with blanks to fill in for the rest).

b. Identify one or two other procedures from the reading that follow the same pattern.

c. Using your template, write a procedure, (smallest lst), that finds the smallest value in a list.

d. Using your template, write a procedure, (rgb-darkest lst), that finds the darkest color in a list of RGB colors.

Hint: You may find it useful to build a utility procedure, (rgb-darker rgb1 rgb2), that finds the darker of two colors.

e. Using your template, write a procedure, (color-name-darkest lst), that finds the darkest color in a list of color names. (You'll need to convert color names to RGB colors in order to compare them. However, you should return a color name, not an RGB color.)

Hint: Again, you'll find it useful to write a utility procedure, such as color-name-darker.

f. Using your template, write a procedure, (closest-to-zero lst), that, given a list of positive and negative numbers, finds the number in the list closest to zero.

Exercise 4: Checking for Brightness

You may recall that in the reading we explored ways to build predicates that apply to lists by starting with predicates that apply to individual values. Let's try writing a few such procedures.

a. Write a procedure, (rgb-all-bright? colors), that, given a list of RGB colors, determines if all of the colors are bright.

b. Write a procedure, (rgb-any-bright? colors), that, given a list of RGB colors, determines if any of them are bright.

Exercise 5: Checking for Primaries

a. Write a procedure, (rgb-all-primary? colors), that, given a list of colors, determines if all of the colors are primary colors (that is, are red, blue, or green).

b. Write a procedure, (rgb-any-primary? colors), that, given a list of colors, determines if any of them are primary colors.

Exercise 6: Checking for Membership

One way to start writing the previous procedures is to define a rgb-primary? predicate.

(define rgb-primary?
  (let ((red (rgb-new 255 0 0))
        (green (rgb-new 0 255 0))
        (blue (rgb-new 0 0 255)))
    (lambda (color)
      (or (equal? color red) (equal? color green) (equal? color blue)))))

Can we generalize this technique for determining whether a value is one of a number of values? Certainly. Let's write a procedure, (member? val vals) that holds only if val appears in vals.

We know that

  • val does not appear in the empty list.
  • val appears in a non-empty vals if val is the car of vals or if it appears in the cdr of vals.

a. Translate this description into Scheme. That is, write member?.

b. Add member? to your library.

c. We can use member? to define the following interesting procedure.

(define greenish?
  (let ((greens (map color-name->rgb (context-list-colors "green"))))
    (lambda (color) (member? color greens))))

Explain what this procedure does.

d. What result do you expect from the following expressions?

> (map greenish? greens)
> (map greenish? my-colors)
> (map greenish? (list (rgb-new 0 0 0) (rgb-new 255 0 0) (rgb-new 128 0 0)))

e. Check your answers experimentally.

Creative Commons License

Samuel A. Rebelsky, rebelsky@grinnell.edu

Copyright (c) 2007-10 Janet Davis, Matthew Kluber, Samuel A. Rebelsky, and Jerod Weinman. (Selected materials copyright by John David Stone and Henry Walker and used by permission.)

This material is based upon work partially supported by the National Science Foundation under Grant No. CCLI-0633090. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

This work is licensed under a Creative Commons Attribution-NonCommercial 2.5 License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc/2.5/ or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.