Summary:
In using map
As we've recently learned, Scheme provides the list
as a basic data type. We've worked with lists in a variety of ways,
but often using map to transform an easily-computed
list into a somewhat more interesting one.
For example, to create a list that cycles through the values from 0 to
4 ten times, we wrote something like:
> (define mod5 (lambda (x) (mod x 5)))
> (map mod5 (iota 50))
(0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 .....
Similarly, we created a list of multiples of ten with something like:
> (define times10 (lambda (x) (* 10 x)))
> (map times10 (iota 50))
(0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 22 .....
We even combined ideas like this, such as in the following, in which we
compute a list that cycles through the values 0, 5, 10, 15, 20, and 25.
> (define mod6 (lambda (x) (modulo x 6)))
> (define times5 (lambda (x) (* 5 x)))
> (map times5 (map mod6 (iota 50)))
(0 5 10 15 20 25 0 5 10 15 20 25 0 5 10 15 20 25 0 5 10 15 20 25 0 5 10 15 20 25 .....
To the experienced functional programmer, it seems a bit odd that we're
defining procedures (like mod5 or
times10) that we're only using once. (From
a student perspective, if you have to document every procedure you
define, it's particularly painful to define procedures you use only
once.) In this reading, we consider a variety of ways to create
procedures that need not have names. Such procedures are often
referred to as anonymous procedures.
The simplest kind of anonymous procedures are lambda forms. In such
forms, you basically take just use (lambda (params) body)
from a procedure definition and do without the actual define.
For example, to the Scheme interpreter, the code
(lambda (x) (* 10 x))
represents “a procedure of one parameter, x,
that computes its value using (* 10 x)”.
So, if we want to multiply every element in a list by 10, instead
of defining times10 and then mapping it, we
can simply write
> (map (lambda (x) (* 10 x)) (iota 50))
(0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 .....
For our more complex calculations, we can use more complex lambda
forms, such as
> (map (lambda (x) (* 5 (modulo x 6))) (iota 50))
(0 5 10 15 20 25 0 5 10 15 20 25 0 5 10 15 20 25 0 5 10 15 20 25 0 5 10 15 20 25 .....
But lambda forms are not the only kind of anonymous procedure available
to Scheme programmers. Long ago, some clever Schemers noticed that we
often create new procedures that effectively fill in one parameter of a
two-parameter procedure. For example, when we created
mod6, we basically just filled in the second
parameter of mod, and when we created
times10, we basically just filled in the first
parameter of *.
In reflecting on situations like this, the Schemers said to
themselves (or perhaps each other), “Why not write procedures
that build one-parameter procedures by filling in one of the two
parameters of a two-parameter procedure?” (Okay, they probably
said it in different words.)
They called the results of their reflection
left-section, which fills in the first parameter,
as in times10,
and right-section, which fills in the second
parameter, as in mod5. We typically refer to
these procedures as l-s and r-s.
For example,
> (map (l-s * 3) (iota 10))
(0 3 6 9 12 15 18 21 24 27)
> (map (l-s + 4) (iota 10))
(4 5 6 7 8 9 10 11 12 13)
> (map (l-s - 5) (iota 10))
(5 4 3 2 1 0 -1 -2 -3 -4)
> (map (r-s - 5) (iota 10))
(-5 -4 -3 -2 -1 0 1 2 3 4)
> (map (r-s mod 3) (iota 10))
(0 1 2 0 1 2 0 1 2 0)
So, to compute that fifty-element list that cycles through the numbers
0 .. 4, we might skip writing mod5 and instead write
> (map (r-s mod 5) (iota 50))
(0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 .....
Similarly, to compute that list of multiples of ten, instead of
defining times10, we might just write
> (map (l-s * 10) (iota 50))
(0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 .....
You've noted that we often call map multiple
times, to transform a list and then transform a list again.
For example, to compute a list that cycles through 1 .. 5, we use
mod5 to make a list that cycles through 0 .. 4 and
then increment to add 1 to each of those values.
> (map increment (map mod5 (iota 50)))
(1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 .....
We can, of course, also use sectioned procedures in such situations.
Here's a sectioned version of a list from the introduction.
> (map (l-s * 5) (map (r-s mod 6) (iota 50)))
(0 5 10 15 20 25 0 5 10 15 20 25 0 5 10 15 20 25 0 5 10 15 20 25 0 5 10 15 20 25 .....
However, to many computer scientists, such nested call to
map are a bit wasteful, since they create
intermediate lists that we then immediately throw away.
Is there a solution to creating such intermediate lists? Yes!
We steal a good idea from the mathematical community and introduce
function composition. The composition of
two functions, f and g
is a new function that first applies g to
its argument and then applies f to that
result. In striving for brevity, we tend to write o for
compose. The o form also has
the advantage that it can compose more than two functions.
> (map (compose square increment) (iota 10))
(1 4 9 16 25 36 49 64 81 100)
> (map (compose increment square) (iota 10))
(1 2 5 10 17 26 37 50 65 82)
> (map (o square increment) (iota 10))
(1 4 9 16 25 36 49 64 81 100)
> (map (o increment square) (iota 10))
(1 2 5 10 17 26 37 50 65 82)
Why is composition useful? Well, as we've already noted, it avoids the
need to compute intermediate lists. (We still have to
compute intermediate values, but the typical Scheme interpreter
needs to spend extra effort building lists.) To many programmers,
compose is also clearer.
As you get more experienced with composition and sectioning, you'll
find that you define many temporary functions by combining the
ideas. For example, to cycle through the first seven odd numbers
(1, 3, 5, 7, 9, 11, 13), we might write
> (map (o increment (l-s * 2) (r-s mod 7)) (iota 50))
(1 3 5 7 9 11 13 1 3 5 7 9 11 13 1 3 5 7 9 11 13 1 3 5 7 9 11 13 1 3 5 7 9 11 13 .....
