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: Interesting images are typically complex, composed of a variety of simpler components. The “drawings as values” library provides operations for making simple components and for composing them into more complex images. However, the uses of these procedures you've seen so far are relatively limited in the kinds of compound drawings they easily support.
In this reading, we explore some richer mechanisms for building groups of drawings, particularly Scheme's list structure and the procedures used with that structure.
In building a complex drawing, one needs to construct and group a number of simpler drawings. For example, as we saw in one might create a drawing of an eye by grouping a variety of ellipses.
Of course, the kinds of drawings we make using the “drawings as values” are rarely so representational. More frequently, we will build abstract figures by composing a large number of simple images.
Let's start with a simple procedure,
(
, that takes a positive number as a
parameter and creates a circle of diameter drawing-centered-circle
n
)n
,
centered at (n
,n
).
;;; Procedure: ;;; drawing-centered-circle ;;; Parameters: ;;; n, a positive number ;;; Purpose: ;;; Create a circle of diameter n, centered at (n,n) ;;; Produces: ;;; circle, a drawing ;;; Preconditions: ;;; n > 0 ;;; Postconditions: ;;; [No additional] (define drawing-centered-circle (lambda (n) (hshift-drawing n (vshift-drawing n (scale-drawing n drawing-unit-circle)))))
(drawing-centered-circle 8)
(drawing-centered-circle 16)
Now, suppose we want to make a series of eight of these circles, using
values of n
from 1 to 8. We might write the
following.
(define eight-circles (drawing-group (drawing-centered-circle 1) (drawing-centered-circle 2) (drawing-centered-circle 3) (drawing-centered-circle 4) (drawing-centered-circle 5) (drawing-centered-circle 6) (drawing-centered-circle 7) (drawing-centered-circle 8)))
eight-circles
But that's a lot of code to write. And it's likely to be worse. Suppose we wanted to make more than eight circles. Say, what if we wanted to make 100 circles? It doesn't seem worth the effort, even with cutting and pasting. Since programming is supposed to ease the need for tedious, repetitive tasks, there must be something better.
Fortunately, there is. In this reading, we will consider Scheme's list data type, which is used to group values, as well as a variety of procedures to build and manipulate lists.
In Scheme, a list is an ordered collection of values. Once you've created a list, the Scheme interpreter shows lists in a fairly simple format:
For example, the Scheme interpreter would show a list of the numbers
2, 3, 5, 7 as (2 3 5 7)
, a list of strings giving the
English names of those numbers as ("two" "three" "five" "seven")
,
and a list of symbols giving the English names of those numbers as
(two three five seven)
.
You may have noted something a bit strange about lists ... they look a lot like procedure calls. (Recall that a procedure call has an open parenthesis, a procedure name, a sequence of parameters separated by spaces, and a close parenthesis.) So, how do we know when we have a procedure call and when we have a list? It depends on the context. Typically, the interpreter assumes that things you type that start with open parentheses are procedure calls (or something similar) and the things that it types that start with open parentheses are lists.
There are a number of ways to create lists, but the easiest is the
list
procedure. This procedure takes as many
parameters values you want to give it, and creates a list containing
those values.
>
(list 2 3 5 7)
'(2 3 5 7)
>
(list "two" "three" "five" "seven")
'("two" "three" "five" "seven")
>
(list 'two 'three 'five 'seven)
'(two three five seven)
Another relatively simple way to make lists is the
(
procedure, which makes a list of
make-list
n
val
)n
copies of val
.
>
(make-list 5 'hello)
'(hello hello hello hello hello)
>
(make-list 7 1)
'(1 1 1 1 1 1 1)
>
(make-list 3 "goodbye")
'("goodbye" "goodbye" "goodbye")
Why would we want a list of multiple copies of the same value? We'll see why in a bit.
map
Procedure
So, what can you do with lists once you've created them? Build other
lists, of course. The first way we'll build lists from lists is with
the (
procedure, which creates a new list
by applying the procedure map
proc
lst
)proc
to each element of
the list lst
.
For example, if we want a list of the squares of the first ten positive
integers (and we're too lazy to compute them by hand), we can use
map
to apply the square
procedure
to each element of the list of the first ten positive integers.
>
(map square (list 1 2 3 4 5 6 7 8 9 10))
'(1 4 9 16 25 36 49 64 81 100)
We can also find out the square roots of those same ten numbers.
>
(map sqrt (list 1 2 3 4 5 6 7 8 9 10))
'(1 1.4142135623730951 1.7320508075688772
2 2.23606797749979 2.449489742783178
2.6457513110645907 2.8284271247461903 3
We can check those results by squaring them again.
>
(map square (map sqrt (list 1 2 3 4 5 6 7 8 9 10)))
'(1 2.0000000000000004 2.9999999999999996
4 5.000000000000001 5.999999999999999
7.000000000000001 8.000000000000002 9
10.000000000000002)
We can also apply a user-defined function to each value in the list.
>
(define f (lambda (x) (+ 1 (* 2 x))))
>
(map f (list 1 2 3 4 5 6 7 8 9 10))
'(3 5 7 9 11 13 15 17 19 21)
What does any of this have to do with building complex
drawings? Well, the drawings as values library includes a
convenient procedure, (
, which, given a list
of drawings, builds a new drawing by combining them together.
drawing-compose
list-of-drawings
)
That means we can return to our original problem of building eight circles of radii 1, 2, 3, 4, 5, 6, 7, and 8 as follows.
map
with
drawing-centered-circle
to convert that list
to a list of drawings.
drawing-compose
to group that list into a
drawing.
In Scheme,
>
(define eight-circles (drawing-compose (map drawing-centered-circle (list 1 2 3 4 5 6 7 8))))
If that's all we care about in our drawing, we can build an image
with drawing->image
. We can also use that
drawing in other ways (e.g., shift it, add a shadow).
Because of the power of map
, it is easy to
make some interesting variations. For example, instead of the numbers
from 1 to 8, we can use the squares of those numbers to get a
different effect.
>
(define another-eight-circles (drawing-compose (map drawing-centered-circle (map square (list 1 2 3 4 5 6 7 8)))))
iota
The instructions above are much more concise than our original instructions for building a collection of eight circles. But it will still take a bit of effort to get one hundred circles. Does Scheme provide other tools that will help? Of course!
The (
procedure creates a list of all the non-negative integers less than
iota
n
)n
, arranged in increasing order.
>
(iota 5)
'(0 1 2 3 4)
>
(map increment (iota 5))
'(1 2 3 4 5)
As this example suggests, when you want the numbers to start at 1
and go through n
, you simply need to increment
each value in the original list.
We now have the tools to create a picture of 100 circles.
First, we build the numbers from 1 to 100.
>
(define nums-to-100 (map increment (iota 100)))
Next, we build circles from each of those numbers.
>
(define circles (map drawing-centered-circle nums-to-100))
We turn that list of circles into a drawing.
>
(define one-hundred-circles (drawing-compose circles))
And, optionally, we render the drawing.
>
(image-show (drawing->image one-hundred-circles 200 100))
Of course, we need not use all those intermediate definitions. We could, just as easily, write
>
(define one-hundred-circles (drawing-compose (map drawing-centered-circle (map increment (iota 100)))))
one-hundred-circles
We also have the tools to make other interesting combinations of circles, such as circles shifted by 1, 4, 9, 16, ..., 100, or by 10, 20, 30, ..., 100.
>
(define quadratic-circles (drawing-compose (map drawing-centered-circle (map square (map increment (iota 10))))))
>
(define times10 (lambda (x) (* 10 x)))
>
(define circles-by-ten (drawing-compose (map drawing-centered-circle (map times10 (map increment (iota 10))))))
quadratic-circles
circles-by-ten
How do these work? Let's look at the lists the subexpressions compute.
>
(iota 10)
'(0 1 2 3 4 5 6 7 8 9)
>
(map increment (iota 10))
'(1 2 3 4 5 6 7 8 9 10)
>
(map square (map increment (iota 10)))
'(1 4 9 16 25 36 49 64 81 100)
>
(map times10 (map increment (iota 10)))
'(10 20 30 40 50 60 70 80 90 100)
Why don't we bother to name the intermediate lists, rather than doing such deep nesting? Because we're only planning to use these lists once (as we experiment with building the drawing) and we try to avoid naming things we may not need again. (Okay, sometimes it's just that we're too lazy to come up with a name.)
map
with multiple listsThese drawings, while potentially interesting, are clearly getting just a bit too similar. One problem we're encountering is that each individual circle depends on just one number, and then we use that number for the horizontal shift, the vertical shift, and the diameter. We'd really like to be able to set the three parameters separately for each drawing.
Fortunately, the map
procedure allows you to provide
not just one list, but as many as you'd like. It then builds a new list
by applying the procedure to the corresponding elements of all the lists.
For example,
>
(map * (list 1 2 3) (list 4 5 6))
'(4 10 18)
>
(map + (list 1 2) (list 3 4) (list 5 6))
'(9 12)
>
(map list (iota 10) (map increment (iota 10)) (map square (iota 10)))
'((0 1 0) (1 2 1) (2 3 4) (3 4 9) (4 5 16) (5 6 25) (6 7 36) (7 8 49) (8 9 64) (9 10 81))
>
(define first-names (list "Addison" "Bailey" "Casey" "Devon" "Emerson"))
>
(define last-names (list "Smith" "Jones" "Smyth" "Johnson" "Doe"))
>
(map string-append first-names (make-list 5 " ") last-names)
'("Addison Smith" "Bailey Jones" "Casey Smyth" "Devon Johnson" "Emerson Doe")
>
(map string-append last-names (make-list 5 ", ") first-names)
'("Smith, Addison" "Jones, Bailey" "Smyth, Casey" "Johnson, Devon" "Doe, Emerson")
How is that helpful? Well, we can start with a drawing of our choice,
use make-list
to make multiple copies, and use
map
with some combination of the drawing procedures
(e.g., hshift-drawing
or
scale-drawing
).
Here's a list of circles, all of diameter five, with quadratic spacing along the horizontal axis.
(define basic-circle (vshift-drawing 50 (scale-drawing 5 drawing-unit-circle))) (define circles01 (map hshift-drawing (map square (iota 10)) (make-list 10 basic-circle)))
(drawing-compose circles01)
Here's the same set of circles, spaced out a little bit more along the vertical axis.
(define circles02 (map vshift-drawing (map times10 (iota 10)) (map hshift-drawing (map square (iota 10)) (make-list 10 (drawing-scale 5 drawing-unit-circle)))))
(drawing-compose circles02)
For those who don't like such deep nesting, here's a version that shows the step-by-step breakdown.
(define circles02-vshifts (map times10 (iota 10))) (define circles02-hshifts (map square (iota 10))) (define circles02 (map vshift-drawing circles02-vshifts (map hshift-drawing circles02-hshifts (make-list 10 (drawing-scale 5 drawing-unit-circle)))))
Here's a set of one hundred circles, spaced equally horizontally, with vertical shift varying from 0 to 19.
(define mod20 (lambda (y) (mod y 20))) (define circles03 (map vshift-drawing (map mod20 (iota 100)) (map drawing-hshift (iota 100) (make-list 100 (drawing-scale 5 drawing-unit-circle)))))
(drawing-compose circles03)
What's happening here? The modulo
procedure takes our
list of integers between 0 and 99, and makes them wrap around to
0 every twenty steps.
>
(map mod20 (iota 100))
'(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19)
We can see the effect a bit better if we space things out.
(define mod10 (lambda (y) (mod y 10))) (define times5 (lambda (x) (* 5 x))) (define circles04 (map vshift-drawing (map times10 (map mod10 (iota 40))) (map hshift-drawing (map times5 (iota 40)) (make-list 40 (scale-drawing 5 drawing-unit-circle)))))
(drawing-compose circles04)
We can use the same technique to modify the radii of the circles.
(define mod5 (lambda (y) (mod y 5))) (define circles05 (map vshift-drawing (map times10 (map mod10 (iota 40))) (map hshift-drawing (map times5 (iota 40)) (map scale-drawing (map increment (map mod5 (iota 40))) (make-list 40 drawing-unit-circle)))))
(drawing-compose circles05)
(define mod7 (lambda (y) (mod y 7))) (define circles06 (map vshift-drawing (map times10 (map mod10 (iota 40))) (map hshift-drawing (map times5 (iota 40)) (map scale-drawing (map increment (map mod7 (iota 40))) (make-list 40 drawing-unit-circle)))))
(drawing-compose circles06)
This last one is complex enough that it's worth looking at the components. Note that we start by scaling the circles (using a computed list of values) and then horizontally and vertically shift those circles. Let's see what the lists we use for scaling, horizontal shifting, and vertical shifting look like.
>
(map increment (map mod7 (iota 40)))
'(1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 .....
>
(map times5 (iota 40))
'(0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 1 .....
>
(map times10 (map mod10 (iota 40)))
'(0 10 20 30 40 50 60 70 80 90 0 10 20 30 40 50 60 70 80 90 0 10 20 30 40 50 60 7 .....
Because the cycle of the radius and the cycle of the vertical shifts
are of different lengths, we get somewhat more complex variation
in circles06
than in circles05
. We can
also get an interesting effect by combining the two drawings.
(define combined-circles (drawing-group (drawing-compose circles05) (hshift-drawing 10 (drawing-compose circles06))))
combined-circles
There are a wide variety of procedures that you can use to manipulate lists. Here are some of the ones you may find useful as you use lists to build compound drawings.
The (
procedure creates a new list, consisting of the elements of
reverse
lst
)lst
, but in the opposite order.
>
(reverse (iota 10))
'(9 8 7 6 5 4 3 2 1 0)
>
(reverse (list 'alpha 'beta 'gamma 'delta 'epsilon))
'(epsilon delta gamma beta alpha)
The (
builds a new list by joining
two lists together.
append
lst1
lst2
)
>
(append (iota 5) (iota 5))
'(0 1 2 3 4 0 1 2 3 4)
>
(append (make-list 3 'alpha) (make-list 4 'beta))
'(alpha alpha alpha beta beta beta beta)
The (
procedure builds a new list
consisting of the first list-take
lst
n
)n
elements of
lst
.
>
(list-take (reverse (iota 10)) 7)
'(9 8 7 6 5 4 3)
The (
procedure builds a new list
consisting of all but the first list-drop
lst
n
)n
elements of
lst
.
>
(list-drop (iota 10) 3)
'(3 4 5 6 7 8 9)
Why do two of these procedures (list-take
and list-drop
) include “list”
in their name and two of them (reverse
and
append
) not? Well ... the ones without
“list” are part of standard Scheme, and were added
to the language when lists were the only collection type.
The other two were added as part of MediaScript, and we make it a
point to name our procedures with the type they work with. (There
are variants of Scheme that simply provide take
and drop
, often with the parameters in the
opposite order.
Rewrite the definition of eight-circles
given in the
definition using a combination of
,
map
, and
iota
.
increment
Predict the results of evaluating each of the following expressions.
(list 2 1) (make-list 1 2) (make-list -1 2) (map - (iota 2)) (map - (iota 2) (list 2 1)) (map iota (list 2 1))
You may verify your predictions with DrRacket.