Iteration

As you may recall, there are a variety of building blocks we use for algorithms. We need to start with a collection of kinds of values and operations on those values. We also need techniques for (a) naming values, (b) sequencing operations, (c) grouping and parameterizing sequences of operations, (d) choosing between operations and groups of operations; and (e) repeating operations.

In this topic, we consider one of Scheme's form of repetition. We've already seen two basic forms of repetition: You can use map to make a new value from each value in an original list, and you can use repeat to repeat a particular action multiple times.

Each technique has its own advantage. In the case of map, we are able to apply a procedure to a wide variety of values. However, we are limited primarily to pure procedures, procedures that create a new value from an old value. In the case of repeat, we are able to work with procedures that have a side-effect, such as turtle-forward!.

In each case we were able to produce some interesting images. For the case of map, we could build a list of some basic shape and then systematically transform each copy. In the case of repeat, we could create a basic action and then repeat that action multiple times.

But what if we want to do both? That is, what if we have a side-effecting operation and we want to vary some aspect of our work as an aspect of the repetition? For example, in each step, we might want to move our turtle a different amount or to turn it a different amount. For example, here are two figures. We get the first by moving the turtle forward one unit, then two, then three, and so on and so forth, turning fifteen degrees between turns. We get the second by always moving the turtle forward five units, but turning it one degree, then two, then three, and so on and so forth.

Fortunately, Scheme provides an alternate version of map that is intended for operations with side effects. In particular, (for-each action! lst) applies action! to each element of lst in turn. Unlike map, which then returns a list, for-each return nothing. That is, the intent of calling for-each is not to build a list, but to create a sequence of effects.

> (for-each (lambda (distance)
             (turtle-forward! tommy distance)
             (turtle-turn! tommy 23))
           (list-drop (iota 21) 1))
> (for-each (lambda (angle)
             (turtle-forward! tommy 5)
             (turtle-turn! tommy angle))
           (list-drop (iota 21) 1))

In this case, we've used a lambda form to work with a particular turtle. However, as we noted in our first exploration of turtles, it can also be useful to name procedures that group basic operations so that we can use them in various combinations.

(define turtle-action-01!
  (lambda (turtle distance)
    (turtle-forward! turtle distance)
    (turtle-turn! turtle 23)))

(define turtle-action-02!
  (lambda (turtle angle)
    (turtle-forward! turtle 5)
    (turtle-turn! turtle angle)))

We can then use these in somewhat simpler (although perhaps less obvious) commands.

> (for-each (l-s turtle-action-01! tommy) (list-drop (iota 21) 1))
> (for-each (l-s turtle-action-02! tommy) (list-drop (iota 21) 1))

As you may be able to predict, each of these actions, if repeated with enough numbers, will produce something like a spiral. (The first action spirals outward, the second inward.) We might therefore want to build a procedure that builds one of these spirals with a certain number of steps.

(define turtle-spiral!
  (lambda (turtle steps)
    (for-each (l-s turtle-action-02! turtle)
              (list-drop (iota (+ 1 steps)) 1))))

In the examples above, we iterated over a list of distances (the first example) or angles (the second example). Are there other lists that make sense to iterate over was we work with turtles? Certainly. We could build a list of turtles, and have each perform the same action. Of course, that won't be very interesting unless the turtles are in different positions.

Let's start by making a list of four turtles, each at a separate position. We can make the turtles in our list “by hand”, as it were, creating each in turn and then moving it to the proper location or orientation. For example,

(define world (image-show (image-new 100 100)))
(define t1 (turtle-new world))
(turtle-teleport! t1 10 10)
(define t2 (turtle-new world))
(turtle-teleport! t2 20 20)
(define t3 (turtle-new world))
(turtle-teleport! t3 30 30)
(define t4 (turtle-new world))
(turtle-teleport! t4 40 40)
(define turtles (list t1 t2 t3 t4))

Now, we can make each turtle draw a spiral (or part thereof).

> (for-each (r-s turtle-spiral 20) turtles)

Of course, given our past experience with map it seems like we should have been able to better automate the construction of the list of turtles. (Clearly, it would take a lot of manual effort to build a dozen or a hundred turtles.)

Fortunately, for-each, like map, permits us to use multiple lists as parameters. Hence, we can move the turtles in our list systematically by building lists of horizontal and vertical offsets and then using turtle-teleport! to move them.

> (define turtles (map turtle-new (make-list 20 world)))
> (for-each turtle-teleport!
            turtles
            (map (l-s * 10) (iota 20))
            (map (l-s * 5) (iota 20)))
> (for-each (r-s turtle-spiral! 30) turtles)

We can also have the circles start their drawing from the same point.

> (define yertle (turtle-new world))
> (define turtles (map turtle-clone (make-list 6 yertle)))
> (for-each turtle-turn! turtles (map (l-s * 60) (iota 6)))
> (for-each (r-s turtle-spiral! 50) turtles)