Laboratory: List Recursion, Revisited

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

Reference

Preparation

a. Add the following procedures to your definitions pane or your library. 

;;; Procedure:
;;;   rgb-brightness
;;; Parameters:
;;;   color, an RGB color
;;; Purpose:
;;;   Computes the brightness of color on a 0 (dark) to 100 (light) scale.
;;; Produces:
;;;   b, an integer
;;; Preconditions:
;;;   color is a valid RGB color.  That is, each component is between
;;;     0 and 255, inclusive.
;;; Postconditions:
;;;   If color1 is likely to be perceived as lighter than color2,
;;;     then (brightness color1) > (brightness color2).
(define rgb-brightness
  (lambda (color)
    (round (* 100 (/ (+ (* 0.30 (rgb-red color))
                        (* 0.59 (rgb-green color))
                        (* 0.11 (rgb-blue color)))
                      255)))))

;;; Procedure:
;;;   rgb-brighter
;;; Parameters:
;;;   color1, an RGB color.
;;;   color2, an RGB color.
;;; Purpose:
;;;   Find the brighter of color1 and color2.
;;; Produces:
;;;   brighter, an RGB color.
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   brighter is either color1 or color2
;;;   (rgb-brightness brighter) >= (rgb-brightness color1)
;;;   (rgb-brightness brighter) >= (rgb-brightness color2)
(define rgb-brighter
  (lambda (color1 color2)
    (if (>= (rgb-brightness color1) (rgb-brightness color2))
        color1
        color2)))

;;; Procedure:
;;;   rgb-bright?
;;; Parameters:
;;;   color, an RGB color
;;; Purpose:
;;;   Determines whether the color is bright.
;;; Produces:
;;;   bright?, a boolean
;;; Preconditions:
;;;   color is a valid RGB color.  That is, each component is between
;;;     0 and 255, inclusive.
;;;   rgb-brightness is defined.
;;; Postconditions:
;;;   bright? is true iff (rgb-brightness color) >= 67.
(define rgb-bright?
  (lambda (color)
    (<= 67 (rgb-brightness color))))

b. Create a list of a dozen or so colors and call it my-colors. (Put this definition in the definitions pane.) For example, 

(define my-color-names 
  (list "palevioletred" "cadetblue" "darkseagreen" "goldenrod"
        "hotpink" "lightsteelblue" "burlywood" "mistyrose"
        "salmon" "peru" "plum" "turquoise"))
(define my-colors
  (map color-name->rgb my-color-names))

c. Create a list of the names of all of the colors with green in the name with 

(define green-names (context-list-colors "green"))

d. Create a list of the RGB equivalents of all of those colors with 

(define greens (map color->rgb green-names))

e. Create a few lists of shades of grey as follows: 

(define greys-4
  (map (lambda (n) (rgb-new (* 64 n) (* 64 n) (* 64 n)))
       (list 4 3 2 1)))
(define greys-8
  (map (lambda (n) (rgb-new (* 32 n) (* 32 n) (* 32 n)))
       (list 8 7 6 5 4 3 2 1)))
(define greys-16
  (map (lambda (n) (rgb-new (* 16 n) (* 16 n) (* 16 n)))
       (list 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1)))

Exercises

Exercise 1: 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 list of lists as a parameter, joins the member lists together using append. 

> (lists-join (list (list 1 2 3)))
(1 2 3)
> (lists-join (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) (list 20 21)))
(1 2 3 10 11 12 20 21)
> (lists-join (list null (list 1 2 3)))
(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)

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

Exercise 2: Making Greys

In the preliminaries, we make three lists of grey values with remarkably similar code. Can we generalize that code? Well, we don't yet know how to make lists of numbers (don't worry, that's coming soon), but 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.

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.

Exercise 3: Folding

Here are possible answers for exercises 1 and 2. 

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

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

You'll notice that both do a similar thing: They take a two-parameter procedure (append or max) 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 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.

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.)

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.

For Those With Extra Time

Exercise 1: Making Points

You may want the following procedures in your library to do this exercise. 

;;; Procedure:
;;;   spot-new
;;; Parameters:
;;;   col, an integer
;;;   row, an integer
;;;   color, a color (name, RGB, etc.)
;;; Purpose:
;;;   Create a new spot.
;;; Produces:
;;;   spot, a spot
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (spot-col spot) = col
;;;   (spot-row spot) = row
;;;   (spot-color spot = color
(define spot-new
  (lambda (col row color)
    (list col row color)))

;;; Procedure:
;;;   spot-col
;;; Parameters:
;;;   spot, a spot
;;; Purpose:
;;;   Extract the col from a spot.
;;; Produces:
;;;   col, an integer
(define spot-col
  (lambda (spot)
    (car spot)))

;;; Procedure:
;;;   spot-row
;;; Parameters:
;;;   spot, a spot
;;; Purpose:
;;;   Extract the row from a spot.
;;; Produces:
;;;   row, an integer
(define spot-row
  (lambda (spot)
    (cadr spot)))

;;; Procedure:
;;;   spot-color
;;; Parameters:
;;;   spot, a spot
;;; Purpose:
;;;   Extract the color from a spot.
;;; Produces:
;;;   color, an integer
(define spot-color
  (lambda (spot)
    (caddr spot)))

;;; Procedure:
;;;   image-get-spot
;;; Parameters:
;;;   image, an image
;;;   position, a position represented as a list of the form (col row)
;;; Purpose:
;;;   Get a spot from the image
;;; Produces:
;;;   spot, a spot
;;; Preconditions:
;;;   col and row are integers.
;;;   0 <= col < (image-width image)
;;;   0 <= row < (image-height image)
;;; Postconditions:
;;;   (spot-col spot) = col
;;;   (spot-row spot) = row
;;;   (spot-color spot) = (image-get-pixel image col row)
(define image-get-spot
  (lambda (image position)
    (let ((col (car position))
          (row (cadr position)))
      (spot-new col row (image-get-pixel image col row)))))

;;; Procedure:
;;;   image-render-spot!
;;; Parameters:
;;;   image, an image
;;;   spot, a spot
;;; Purpose:
;;    Draw the spot on the image.
;;; Produces:
;;;   [Nothing; Called for the side effect]
(define image-render-spot!
  (lambda (image spot)
    (image-set-pixel! image 
                      (spot-col spot) (spot-row spot)
                      (spot-color spot))))

Remember that we sometimes represent a position as a list of two values (a column and a row). How might we get a grid of such positions?

a. Write a procedure, (first-ten-points row), that returns a list of the first ten points in the specified row. (Note that you probably want to use map in defining this procedure.) 

> (first-ten-points 5)
((0 5) (1 5) (2 5) (3 5) (4 5) (5 5) (6 5) (7 5) (8 5) (9 5))
> (first-ten-points 2)
((0 2) (1 2) (2 2) (3 2) (4 2) (5 2) (6 2) (7 2) (8 2) (9 2))

b. What result do you expect the following expression to produce? 

> (map first-ten-points (list 0 1 2 3 4 5 6 7 8 9))

c. Check your answer experimentally.

d. You should have observed that the result of the expression in step b is a list of lists. What if we want a single list? We can use lists-join. Confirm that the following expression creates a list of 100 points. 

> (lists-join (map first-ten-points (list 0 1 2 3 4 5 6 7 8 9)))

e. Now, let's generalize what we just did. Write a procedure, (ten-by-ten col row) that creates a list that describes a ten-by-ten grid of position, with (col,row) as the upper-left position.

f. Confirm that we can use this procedure to grab a grid of spots from an image with an expression like 

> (define spots (map (lambda (position) (image-get-spot picture position)) (ten-by-ten 0 0)))

g. Render the spots you've just generated.

Jerod Weinman