Higher-Order Procedures

Recall that (map proc lst) builds a new list by applying proc to each element of lst in succession.

Recall also that (iota n) builds a list of integers from 0 to n-1.

a. (iota 10) computes a list of the integers between 0 and 9. Use map and iota to compute the list of integers between 1 and 10.

b. Use map to compute the successors to the squares of the integers between 1 and 10. (That is, for each value in the list, square it and then add 1.) Your result should be the list (2 5 10 17 26 37 50 65 82 101).

c. Use map to take the last element of each list in a list of lists. The result should be a list of the last elements. For example,

> (map _____ (list (list 1 2 3) (list 4 5 6) (list 7 8 9 10) (list 11 12)))
(3 6 10 12)

d. Use apply and map to sum the last elements of each list in a list of lists of numbers. The result should be a number.

> (apply _____ (map _____ (list (list 1 2 3) (list 4 5 6) (list 7 8 9 10) (list 11 12))))
31 ; 3 + 6 + 10 + 12

Hint: You already know how to get a list of the last elements of each member list, so think about how to add them.

Reminder: As you may recall, (apply proc lst) is another way to write (proc v1 v2 ... vn) given that lst is (v1 v2 ... vn).

a. Read through the code for image-render-colors! and be prepared to explain, in your own words, what this procedure does.

b. What effect do you expect the following instruction to have?

> (image-render-colors! canvas colors-rainbow)

c. What effect do you expect the following instruction to have?

> (image-render-colors! canvas (map rgb-complement colors-rainbow))

d. Check your answer experimentally.

e. Write an expression to render a darker version of the rainbow on canvas.

f. Write an expression to generate a list of colors that are a much darker version of colors-rainbow. (For each color, call rgb-darker three times.)

g. Here are four possible solutions to the previous problem. Which do you prefer? Why? Be prepared to discuss your reasons with the class.

> (map rgb-darker (map rgb-darker (map rgb-darker colors-rainbow)))

> (map (lambda (c) (rgb-darker (rgb-darker (rgb-darker c)))) colors-rainbow)

> (map (compose rgb-darker (compose rgb-darker rgb-darker)) colors-rainbow)

> (map (o rgb-darker rgb-darker rgb-darker) colors-rainbow)

As you may recall, the left-section (a.k.a. l-s) and right-section (a.k.a. r-s) procedures let you create a new procedure by filling in one of the two parameters of a two-parameter procedure.

a. Review the definitions of these procedures

b. Using left-section or l-s, define a procedure, (increment-nums lst), that takes a list of numbers and adds 1 to each number. Your definition is likely to also involve map.

c. Using left-section or l-s, write an expression that computes the reciprocals of the numbers between 1 and 10. (Recall that the reciprocal of x is 1/x.) Your expression is likely to also involve map, and possibly other procedures.

d. What do you think will happen if use right-section instead of left-section in the previous two exercises?

e. Check your answer experimentally.

Although we often use the map procedure with only two parameters (a procedure and a list), it can take more than two parameters, as long as the first parameter is a procedure, the remaining parameters are lists, and the procedure can legally take the corresponding parameters from each list. For example, if the procedure is +, each list must contain numbers.

a. What colors do you expect the following expression to produce?

> (map rgb-average colors-rainbow (make-list (length colors-rainbow) color-white))

b. Check your answer experimentally, by rendering the result on canvas, by converting each color to a string, or both.

c. What do you expect the following expression to produce?

> (map rgb-average colors-rainbow (make-list 5 color-white))

d. Check your answer experimentally.

e. What do you expect the following expression to produce?

> (map rgb-average colors-rainbow (map rgb-complement colors-rainbow))

f. Check your answer experimentally.

a. What do you think the value of the following expression will be?

> (map (lambda (x y) (+ x y)) (list 1 2 3) (list 4 5 6))

b. Check your answer through experimentation.

c. What do you think the value of the following expression will be?

> (map list (list 1 2 3) (list 4 5 6) (list 7 8 9))

d. Check your answer through experimentation.

e. What do you think Scheme will do when evaluating the following expression?

> (map (lambda (x y) (+ x y)) (list 1 2) (list 3 4) (list 5 6))

f. Check your answer through experimentation.

g. What do you think Scheme will do when evaluating the following expression?

> (map + (list 1 2 3) (list 4 5 6))

h. Check your answer through experimentation.

i. What do you think Scheme will do when evaluating the following expression?

> (map + (list 1 2) (list 3 4) (list 5 6))

j. Check your answer through experimentation.

k. What do you think Scheme will do when evaluating the following expression?

> (map + (list 1 2) (list 3 4) (list 5 6 7))

l. Check your answer through experimentation.

Use apply and map to concisely define a procedure, (dot-product list1 list2), that takes as arguments two lists of numbers, equal in length, and returns the sum of the products of corresponding elements of the arguments:

> (dot-product (list 1 2 4 8) (list 11 5 7 3))
73
> (dot-product null null)
0

Note that we get the first result because (1 x 11) + (2 x 5) + (4 x 7) + (8 x 3) = 11 + 10 + 28 + 24 = 73 and the second because there are no products to add.

The procedure (acronym strings) produces an acronym from a list of strings. For example,

> (acronym (list "GNU" "Image" "Manipulation" "Program"))
"GIMP"
> (acronym (list "International" "Business" "Machinery"))
"IBM"

Write acronym as concisely as possible. As a hint, you will want to use string-ref, list->string, map, and either l-s or r-s.

(Recall that (string-ref string i) produces the ith character in string. list->string takes a list of characters and turns it into a string.)

a. Document and write a procedure, (list-tally lst pred?), that counts the number of values in list for which predicate holds.

b. Demonstrate the procedure by tallying the number of odd values in the list of the first twenty non-negative integers. (Note that you can use (iota 20) to create that list.)

c. Demonstrate the procedure by tallying the number of multiples of three in the list of the first twenty non-negative integers.

Write a procedure, (list-filter list predicate), that creates a procedure that takes a list as a parameter and removes all elements for which predicate holds.

For example,

> (define filter-whitespace (lambda (lst) (list-filter lst char-whitespace?)))
> (filter-whitespace (list #\a #\space #\b #\c))
(#\a #\b #\c)
> (list->string (filter-whitespace (string->list "Hello, my name is Dr. Fu")))
"Hello,mynameisDr.Fu"

Write a procedure, (vector-map! proc vec), that replaces each element of vec with the result of applying proc to the original element.