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:
In using
with lists, we often
found ourself writing procedures that were only used once, and that
had somewhat predictable form. In this reading, we explore how
Scheme permits us to write and use anonymous
procedures, procedures that can be called without being named.
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) (modulo 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 modulo
, 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 .....
a. What type do the functions
and l-s
take as their first
parameter?
r-s
b. What type do the functions
and compose
take as parameters?
o
c. What types do all four of these functions produce?
d. What type does the function
take as its first parameter?
map
a. What is the difference between (l-s + 2)
and
(r-s + 2)
? Do the resulting procedures produce the same
results?
b. What is the difference between (l-s - 2)
and
(r-s - 2)
? Do the resulting procedures produce the same
results?
c. What is the difference between (o increment sqrt)
and (o sqrt increment)
? Do the resulting procedures
produce the same results?