# Higher-Order Procedures

## Exercises

Start DrScheme

### Exercise 1: Using `map`

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

a. Use `map` to compute the successors to the squares of the integers between 1 and 10. Your result should be the list `(2 5 10 17 26 37 50 65 82 101)`.

b. 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, given `((1 2 3) (4 5 6) (7 8 9 10) (11 12))` as input, you should produce the list `(3 6 10 12)`.

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

Note that you may have written a similar expression for another lab. Your goal here is to see whether you can solve the problem more concisely.

### Exercise 2: Map with Multiple Lists

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 and the remaining parameters are lists.

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

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

e. What do you think Scheme will do when evaluating the following expression?
`(map list (list 1 2 3) (list 4 5))`

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

### Exercise 3: Dot-Product

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
; ... because (1 x 11) + (2 x 5) + (4 x 7) + (8 x 3) = 11 + 10 + 28 + 24 = 73

> (dot-product null null)
0
; ... because in this case there are no products to add
```

### Exercise 4: Why Apply?

Sarah and Steven Schemer suggest that `apply` is irrelevant. After all, they say, when you write `(apply proc (arg1 ... argn))` you're just doing the same thing as `(proc arg1 arg2 ... argn)`.

Given your experience in the previous exercise, are they correct? Why or why not?

### Exercise 5: Tallying

a. Document and write a procedure, ```(tally predicate list)```, 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 integers.

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

### Exercise 6: Making Talliers

Document and write a procedure, `(make-tallier predicate)`, that builds a procedure that takes a list as a parameter and tallies the values in the list for which the predicate holds. For example

```> (define count-odds (make-tallier odd?))
> (count-odds (list 1 2 3 4 5))
3
```

You can assume that `tally` already exists for the purpose of this problem.

### Exercise 7: Removing Elements

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

For example, ``` > (define remove-whitespace (make-remover char-whitespace?)) > (remove-whitespace (list #\a #\space #\b #\c)) (#\a #\b #\c) > ((make-remover odd?) (list 1 2 3 4 5)) (2 4) ```

## If You Have Extra Time

### Extra 1: `make-tallier`, revisited

Rewrite `make-tallier` so that it doesn't call `tally` and so that it doesn't call itself. (You'll have to create a local recursive procedure and then return it.)

### Extra 2: Vector Mapping

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

## History

Thursday, 2 November 2000 [Samuel A. Rebelsky]

Wednesday, 14 February 2001 [Samuel A. Rebelsky]

• Moved many problems into a new lab so that there are now two higher-order procedures labs.
• Added new problems (1, 4, and 5).
• Removed unused notes section.

Sunday, 8 April 2001 [Samuel A. Rebelsky]

Tuesday, 15 October 2002 [Samuel A. Rebelsky]

• Reformatted slightly.
• Added some introductory notes.

Wednesday, 16 October 2002 [Samuel A. Rebelsky]

Sunday, 16 February 2003 [Samuel A. Rebelsky]

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Tue May 6 09:19:49 2003.
The source to the document was last modified on Sun Feb 16 20:43:17 2003.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2003S/Labs/higher-order.html`.

Samuel A. Rebelsky, rebelsky@grinnell.edu