Iterating Over Lists

Summary: We examine techniques for doing computation using each element of a list.

Introduction

As you may recall from our initial discussions of algorithms, there are four primary kinds of control that help us write algorithms: We sequence operations, we choose between operations, we encapsulate groups of operations into functions, and we repeat operations. At this point, you've learned mechanisms for sequencing operations (by listing one after another or by nesting them), for choosing (with `cond`, `if`, and `when`), and for grouping operations (as procedures).

You've also seen some very specific mechanisms for repeating operations. `image-variant` and `image-transform!` apply a procedure to each pixel in an image, and `image-compute` (and its variants) build pixels by applying a function to the column/row of a position.

However, you have not learned a general mechanism for repeating operations. It is time to remedy that situation. We will start by looking at how you iterate over the values in a list.

What if we want to iterate over other kinds of values? Very soon, you'll learn about recursion, Scheme's most general mechanism for repeating actions.

From Spots to Stamps

To ground our explorations of repetition, we will consider the ways in which these techniques might be useful for working with stamps (lists of spots), a type we considered in a previous reading.

In case you've forgotten, a spot represents one pixel in an image or stamp. There are three components to a spot: its column, its row, and its color. We create spots with `spot-new` and extract the three components with `spot-col`, `spot-row`, and `spot-color`. We can render a spot on an image with `image-render-spot!` or `image-scaled-render-spot!` or anything else we decide to write.

A stamp is a small image that we might place on another image. Although we can place stamps at their base position, more frequently we want to place them elsewhere in the image. We may also want to scale them.

When we first explored spots and stamps, we decided to represent each spot as a three element list, with the column as the first element, the row as the second, and the color as the third. We also decided to represent stamps as lists of spots.

Here are two sample stamps. The first is the spiral-like stamp from the the reading on spots. The second is a bit more abstract.

```(define stamp-01
(list (spot-new 2 2 "black")
(spot-new 3 3 "black")
(spot-new 2 4 "black") (spot-new 1 4 "black")
(spot-new 0 3 "black") (spot-new 0 2 "black") (spot-new 0 1 "black")
(spot-new 1 0 "black") (spot-new 2 0 "black") (spot-new 3 0 "black")
(spot-new 4 1 "black")
(spot-new 5 2 "black") (spot-new 5 3 "black") (spot-new 5 4 "black")
(spot-new 4 5 "black")))
```
```(define stamp-02
(list (spot-new 0 0 "black") (spot-new 1 0 "black")
(spot-new 0 1 "black")
(spot-new 3 0 "black") (spot-new 4 0 "black")
(spot-new 3 1 "black")
(spot-new 2 2 "black") (spot-new 2 3 "black")
(spot-new 0 3 "black") (spot-new 4 3 "black")
(spot-new 0 4 "black") (spot-new 4 4 "black")
(spot-new 1 5 "black") (spot-new 2 5 "black") (spot-new 3 5 "black")))```

`stamp-01`

`stamp-02`

While it was straightforward to implement all of the individual spot procedures, we have not yet explored how to render, scale, or shift stamps. Why not? Because to do so, we'll need to do something with each element in a list, which clearly requires some form of repetition. For example, rendering a stamp essentially requires rendering each spot in the stamp. Similarly, shifting a stamp right requires that we shift each spot right. So, let's start to consider ways to work with element of a list.

`map` - Building New Lists from Old

Scheme provides one standard procedure for doing something with each element of a list, `map`. In particular, ```(map func lst)``` creates a new list of the same length as `lst` by applying the function `func` to each element of `lst`.

For example, we can add 1 to every number in a list of numbers with

```(define increment (lambda (num) (+ 1 num)))
(map increment numbers)
```

Let's see that code in a sample sequence from the interactions pane.

````>` `(define numbers (list 11 2 1 8 16))`
`>` `numbers`
`(11 2 1 8 16)`
`>` `(define increment (lambda (num) (+ 1 num)))`
`>` `(map increment numbers)`
`(12 3 2 9 17)`
`>` `numbers`
`(11 2 1 8 16)`
```

As the last command suggests, `map` is pure: Even after we've applied `map`, `numbers` remains unchanged.

Note that like `image-compute` and `image-variant`, `map` is a higher-order procedure. That is, like those procedures, `map` takes a procedure as one of its parameters. In contrast, `map` is more general: where `image-compute` expects a function from col/row to colors and `image-variant` expects a function from colors to colors, `map` can take a variety of kinds of procedures, provided the parameters match the types of the values in the list.

To shift a stamp down, we must shift each spot down. First, we need a procedure to shift spots down, which you may recall.

```(define spot-nudge-down
(lambda (spot)
(spot-new (spot-col spot) (+ (spot-row spot) 1) (spot-color spot))))
```

Now, we can use `map` to shift a stamp down.

`(map spot-nudge-down stamp-01)`

`(map spot-nudge-down stamp-02)`

Detour: Anonymous Procedures

You may recall that when we first worked with `image-variant`, we began to explore the notion of anonymous procedures, procedures which have no names. Scheme programmers regularly use anonymous procedures with `map`.

Let's return to our first example of `map`.

```(define numbers (list 11 2 1 8 16))
(define increment (lambda (num) (+ 1 num)))
(map increment numbers)
```

What happens when the Scheme interpreter evaluates these two lines? Well, the definitions add the following pairs to the names table:

Name Value
`numbers` `(11 2 1 8 6)`
`increment` `(lambda (num) (+ 1 num))`

Next, the interpreter evaluates the call to `map`. In order to evaluate the call to `map`, the interpreter needs to evaluate all the parameters, which means that it replaces the names in the call with their values.

```(map (lambda (num) (+ num 1)) '(11 2 1 8 6))
```

Finally, it applies the procedure to each value. (How it does that is left as a mystery, at least for a little while longer.)

You know that we could just as easily have used a list we created on-the-fly for the second parameter to map.

```(map increment (list 1 2 3 4 5))
```

In this case, the Scheme interpreter needs to evaluate the second parameter, rather than just look it up in the table. It can still look up the value of `increment` though. After making those substitutions, we end up wtih

```(map (lambda (num) (+ num 1)) '(1 2 3 4 5))
```

By plugging in the list directly, we avoided the need for one definition. That is, we no longer need to define `numbers`. Here's an interesting thing: We can also manually write the lambda part of `increment`. That is, we can start by writing

```(map (lambda (num) (+ num 1)) (list 1 2 3 4 5))
```

No extra definitions are necessary!

A lambda-form without a corresponding `define` is called an anonymous procedure (because it has no name). Anonymous functions are regularly used along with procedures like `map` to quickly string together actions. For example, suppose we start with a list of numbers and, for each, we want the maximum of 80 and that number. We can write

````>` `(map (lambda (val) (max 80 val)) (list 22 88 23 66 100 90))`
`(80 88 80 80 100 90)`
```

Using `map` with Stamps

The `map` procedure can be quite useful with lists of spots. For example, if we've created one list of spots, we can map a procedure onto that list to change the color of the spots, move the spots elsewhere, or even rotate the spots around some point.

For example, in the lab on lists of spots, you wrote a procedure that translated a spot horizontally. We can translate a whole list of spots horizontally by 5 units with

```(map (lambda (spot) (spot-htrans spot 5)) spots)
```

In effect, once you've designed a picture using lists of spots, you can use it as a kind of rubber stamp, drawing it again and again at different places in an image.

`(map (lambda (spot) (spot-nudge-right spot 5)) stamp-01)`

`(map (lambda (spot) (spot-nudge-right spot 5)) stamp-02)`

`for-each` - Doing Something with Each Element of a List

For `map` to be useful with lists of spots, we need a way to render all of the spots in a list, and not just one. And `map` provides a solution to that problem. We can draw all the spots with something like the following:

````>` `(map (lambda (spot) (image-render-spot! canvas spot)) spots)`
```

This solution will certainly work. However, it's also a bit awkward. While we are doing something with each element in the list, our goal is not to create a new list. The resulting list is not even particularly meaningful. In this case, and many others, we iterate through the list not to create a list, but to do things with the values in the list, with no goal of creating new values.

This technique of iterating a list for the side effect, and not to create a new list, is common enough that most Scheme programmers define a procedure for just that purpose. That procedure is common enough that it has a common name, `for-each`.

So, here's the typical way to define a procedure that draws each spot in a list of spots.

```;;; Procedure:
;;;   image-render-stamp!
;;; Parameters:
;;;   image, an image
;;;   stamp, a list of spots
;;; Purpose:
;;    Draw the stamp on the image.
;;; Produces:
;;;   image, the same image
(define image-render-stamp!
(lambda (image stamp)
(for-each (lambda (spot) (image-render-spot! image spot))  stamp)
image))
```

We can write a similar procedure to draw a bigger version of each spot.

```;;; Procedure:
;;;   image-render-big-stamp!
;;; Parameters:
;;;   image, an image id
;;;   stamp, a list of spots
;;; Purpose:
;;;   Render a stamp (a list of spots) "bigger".
;;; Produces:
;;;   image, the same image
;;; Preconditions:
;;;   Each scaled spot can be safely rendered.
(define image-render-big-stamp!
(lambda (image stamp)
(for-each (lambda (spot) (image-scaled-render-spot! image spot 20)) stamp)
image))
```

We can even make the scale a parameter to the procedure.

```;;; Procedure:
;;;   image-scaled-render-stamp!
;;; Parameters:
;;;   image, an image
;;;   stamp, a list of spots.
;;;   factor, a number
;;; Purpose:
;;    Draw all of the spots in the stamp on the image, with each spot
;;;   scaled by factor.
;;; Produces:
;;;   image, the same image
;;; Preconditions:
;;;   factor >= 1
;;;   The position of the scaled spot is within the bounds of the image.
;;; Postconditions:
;;;   The image now contains a rendering of each spot.
(define image-scaled-render-stamp!
(lambda (image stamp scale)
(for-each (lambda (spot) (image-scaled-render-spot! image spot scale))
stamp)
image))
```

Reference

```(for-each proc! lst)```
Standard Higher-Order List Procedure. Apply `proc!` to each element of the given list. Called primarily for side effects.
```(map func lst)```
Standard Higher-Order List Procedure. Create a new list, each of whose elements is computed by applying `func` to the corresponding element of `lst`.

Samuel A. Rebelsky, rebelsky@grinnell.edu

Copyright (c) 2007-2009 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.