Functional Problem Solving (CSC 151 2014F) : Readings
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [FAQ] [Teaching & Learning] [Grading] [Rubric] - [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Setup] [VM] [Errors] - [Functions A-Z] [Functions By Topic] - [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Davis (2013F)] [Rebelsky (2014S)] [Weinman (2014F)]
Misc: [Submit Questions] - [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Issue Tracker (Course)]
Summary: We consider some new mechanisms for repeating procedures that are called primarily for their side effects.
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,
(
applies for-each
action!
lst
)action!
to each element of lst
in turn. Unlike
map
, which then produces a list,
for-each
produces nothing. That is, the intent
of calling for-each
is not to build a list, but
to cause a series 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))))
for-each
for Multiple TurtlesIn 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)
This check is designed to reinforce the distinctions between the
different functions available to do some form of
repetition. Complete the following sentences with one of
map
, repeat
or
for-each
.
a. Make a copy of iteration-lab.rkt
,
which contains some procedures from the reading.
b. The reading claims that by applying the
turtle-action-01!
procedure to the numbers from
1 to n, we can get one form of spiral. Check this claim using
something like the following code.
>
(define world1 (image-show (image-new 200 200)))
>
(define turtle1 (turtle-new world1))
>
(for-each (l-s turtle-action-01! turtle1) (list-drop (iota ___) 1))
c. The reading claims that by applying the
turtle-action-02!
procedure to the numbers from
1 to n, we can get another form of spiral. Check this claim using
similar code to that above.
d. Does it matter whether we start with 1 or 0 for the list of distances or angle? Check your answer experimentally.