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 this reading, we explore the so-called higher-order procedures, procedures that take procedures as parameters or return procedures as results. In effect we are considering what happens when we allow procedures to serve as values.
One mark of successful programmers is that they identify and remember common techniques for solving problems. Such abstractions of common structures for solving problems are often called patterns or design patterns. You should already have begun to identify some patterns. For example, you know that procedures almost always have the form
(defineprocname
(lambda (parameters
)body
))
You may also have a pattern in mind for the typical recursive procedure over lists:
(defineprocname
(lambda (lst) (if (null? lst)base-case
(do-something
(car lst) (procname
(cdr lst))))))
In some languages, these patterns are simply guides to programmers as they design new solutions. In other languages, such as Scheme, you can often encapsulate a design pattern in a separate procedure.
Let's begin with a simple problem: Suppose we have a list of colors
and we want to create three new lists: one that contains the red
component of each color, one that contains the largest component of
each color, and one that contains the average of the three components.
Suppose also that your first inclination is to use recursion to create
each list, perhaps because you've forgotten about map
.
After some reflection, you might write something like the following
;;; Procedure: ;;; extract-red-components ;;; Parameters: ;;; colors, a list ;;; Purpose: ;;; Get the red component from each color in colors. ;;; Produces: ;;; reds, a list ;;; Preconditions: ;;; Every value in colors is an RGB color. ;;; Postconditions: ;;; Every value in reds is an integer between 0 and 255, inclusive. ;;; (length reds) = (length colors) ;;; For each i, 0 <= i < (length colors) ;;; (list-ref reds i) = (rgb-red (list-ref colors i)) (define extract-red-components (lambda (colors) (if (null? colors) ; If no colors remain, there's nothing left to work with, ; so use the empty list. null ; Otherwise, get the red component of the first color, get the ; red component of the remaining colors, and shove everything ; back together. (cons (rgb-red (car colors)) (extract-red-components (cdr colors)))))) ;;; Procedure: ;;; extract-max-components ;;; Parameters: ;;; colors, a list ;;; Purpose: ;;; Get the maximum (largest) component from each color in colors. ;;; Produces: ;;; maxs, a list ;;; Preconditions: ;;; Every value in colors is an RGB color. ;;; Postconditions: ;;; Every value in maxs is an integer between 0 and 255, inclusive. ;;; (length maxs) = (length colors) ;;; For each i, 0 <= i < (length colors) ;;; (list-ref maxs i) = the maximum component of (list-ref colors i) (define extract-max-components (lambda (colors) (if (null? colors) ; If no colors remain, there's nothing left to work with, ; so use the empty list. null ; Otherwise, get the maximum component of the first color, get ; the maximum component of each remaining color, and shove ; everything back together. (cons (max (rgb-red (car colors)) (rgb-green (car colors)) (rgb-blue (car colors))) (extract-max-components (cdr colors)))))) ;;; Procedure: ;;; extract-ave-components ;;; Parameters: ;;; colors, a list ;;; Purpose: ;;; Get the average component from each color in colors. ;;; Produces: ;;; averages, a list ;;; Preconditions: ;;; Every value in colors is an RGB color. ;;; Postconditions: ;;; Every value in averages is an integer between 0 and 255, inclusive. ;;; (length averages) = (length colors) ;;; For each i, 0 <= i < (length colors) ;;; (list-ref averages i) = the average component of (list-ref colors i) (define extract-ave-components (let ([ave (lambda (c) (round (/ (+ (rgb-red c) (rgb-green c) (rgb-blue c)) 3)))]) (lambda (colors) (if (null? colors) ; If no colors remain, there's nothing left to work with, ; so use the empty list. null ; Otherwise, get the average component of the first color, get ; the average component of each remaining color, and shove ; everything back together. (cons (ave (car colors)) (extract-ave-components (cdr colors)))))))
Here's how each works on the colors in the rainbow.
>
(extract-red-components colors-rainbow)
(255 255 255 0 0 75 238)
>
(extract-max-components colors-rainbow)
(255 255 255 128 255 130 238)
>
(extract-ave-components colors-rainbow)
(85 140 170 43 85 68 202)
What do these three procedures have in common? Most of the documentation, not only the six P's, but also the internal documentation. All return null when given the null list. More importantly, all three do something to the car of the list, recurse on the cdr of the list, and then cons the two results together.
Hence, it is natural to design a general pattern for apply a procedure to every value in a list.
(defineprocname
(lambda (lst
) (if (null?lst
) null (cons (modify
(car lst)) (procname
(cdr lst))))))
Now, here's the cool part. We can even turn this pattern into a procedure.
;;; Procedure: ;;; colors-transform-v0 ;;; Parameters: ;;; colors, a list of colors. ;;; Purpose: ;;; Applies TRANSFORM to each color in a list. ;;; Returns: ;;; transformed, a list of colors. ;;; Preconditions: ;;; lst contains only RGB colors. [Unverified] ;;; TRANSFORM is defined, takes one color as a parameter ;;; and returns a color. [Unverified] ;;; Postconditions: ;;; transformed contains only RGB colors. ;;; (length transformed) = (length colors) ;;; For each i, 0 <= i < (length transformed) ;;; (list-ref transformed i) = (TRANSFORM (list-ref colors i)) (define colors-transform-v0 (lambda (colors) ; If no elements remain, we have nothing to apply TRANSFORM to, ; so stick with the empty list. (if (null? colors) null ; Otherwise, transform the first value, transform the remaining ; values, and put the stuff back together into a list. (cons (TRANSFORM (car colors)) (colors-transform-v0 (cdr colors))))))
Where does TRANSFORM
come from? We could define it first
(as the preconditions suggest). For example, here's an application of
colors-transform
in which we get just the red
component of a color.
>
(define TRANSFORM rgb-red)
>
(colors-transform-v0 colors-rainbow)
(255 255 255 0 0 75 238)
Similarly, we can get the average component by defining
TRANSFORM
as extract-ave-components
.
>
(define TRANSFORM (lambda (c) (round (/ (+ (rgb-red c) (rgb-green c) (rgb-blue c)) 3))))
>
(colors-transform-v0 colors-rainbow)
(85 140 170 43 85 68 202)
You may find this strategy of defining TRANSFORM
first
inelegant. We certainly do. It also won't work for all cases.
For example, what if we want to get the red components of all the
colors in one list and then get the average components of all the
colors in another list? We'd have to redefine TRANSFORM
right in the middle of the code. Ugly.
As importantly, we can't use local bindings to define
TRANSFORM
. For example, consider the following
code.
>
(define TRANSFORM rgb-complement)
>
(map rgb->string (colors-transform-v0 colors-rainbow))
("0/255/255" "0/90/255" "0/0/255" "255/127/255" "255/255/0" "180/255/125" "17/125/17")
>
(define TRANSFORM rgb-darker)
>
(map rgb->string (colors-transform-v0 colors-rainbow))
("239/0/0" "239/149/0" "239/239/0" "0/112/0" "0/0/239" "59/0/114" "222/114/222")
>
(let ((TRANSFORM rgb-lighter)) (map rgb->string (colors-transform-v0 colors-rainbow)))
("239/0/0" "239/149/0" "239/239/0" "0/112/0" "0/0/239" "59/0/114" "222/114/222")
So, we're stuck with redefining TRANSFORM
using
define
in the middle of our code, and that is unlikely
to be clear or convenient.
Is there a better solution? Yes! Instead of forcing
TRANSFORM
to be defined before we call
colors-transform
, we can make the
TRANSFORM
procedure a parameter to the
colors-transform
pattern. For example, here's a new
version of colors-transform
that takes the
extra parameter.
;;; Procedure: ;;; colors-transform ;;; Parameters: ;;; colors, a list of colors. ;;; trans, a procedure ;;; Purpose: ;;; Applies trans to each color in a list. ;;; Returns: ;;; transformed, a list of colors. ;;; Preconditions: ;;; lst contains only RGB colors. [Unverified] ;;; trans takes one color as a parameter and returns a color. [Unverified] ;;; Postconditions: ;;; transformed contains only RGB colors. ;;; (length transformed) = (length colors) ;;; For each i, 0 <= i < (length transformed) ;;; (list-ref transformed i) = (trans (list-ref colors i)) (define colors-transform (lambda (colors trans) ; If no elements remain, we have nothing to apply transform to, ; so stick with the empty list. (if (null? colors) null ; Otherwise, transform the first value, transform the remaining ; values, and put the stuff back together into a list. (cons (trans (car colors)) (colors-transform (cdr colors) trans)))))
If we plug in procedures (either previously-named procedures or newly named procedures), we get the results we expect.
>
(map rgb->string colors-rainbow)
("255/0/0" "255/165/0" "255/255/0" "0/128/0" "0/0/255" "75/0/130" "238/130/238")
>
(map rgb->string (colors-transform colors-rainbow rgb-complement))
("0/255/255" "0/90/255" "0/0/255" "255/127/255" "255/255/0" "180/255/125" "17/125/17")
>
(map rgb->string (colors-transform colors-rainbow rgb-darker))
("239/0/0" "239/149/0" "239/239/0" "0/112/0" "0/0/239" "59/0/114" "222/114/222")
>
(map rgb->string (colors-transform colors-rainbow rgb-lighter))
("255/16/16" "255/181/16" "255/255/16" "16/144/16" "16/16/255" "91/16/146" "254/146/254")
>
(map rgb->string (colors-transform colors-rainbow rgb-darker))
("239/0/0" "239/149/0" "239/239/0" "0/112/0" "0/0/239" "59/0/114" "222/114/222")
Thus, as you've seen before in this class, you can write your own procedures that take procedures as parameters. We call procedures that take other procedures as parameters higher-order procedures.
Of course, the idea of passing a procedure as a parameter should
be comfortable if you've been using map
,
image-variant
, foreach!
,
and similar functions. In fact, map
is likely
to be defined much like colors-transform
(except
that officially, the order in which map
builds
the result list is up to the implementer). We could even define our
own version (and you may even have already done so yourself).
;;; Procedure: ;;; proc-map ;;; Parameters: ;;; proc, a procedure ;;; lst, a list ;;; Purpose: ;;; Applies proc to each value in a list. ;;; Returns: ;;; newlst, a list ;;; Preconditions: ;;; proc can successfully be applied to each value in lst. ;;; Postconditions: ;;; newlst is the same length as lst ;;; For each i, 0 <= i < (length newlst) ;;; (list-ref newlst i) = (proc (list-ref lst i)) (define proc-map (lambda (proc lst) ; If no elements remain, we can't apply anything else, ; so produce the empty list. (if (null? lst) null ; Otherwise, apply the procedure to the first value, ; apply the procedure to the remaining values, and ; put the results back together into a list. (cons (proc (car lst)) (proc-map proc (cdr lst))))))
Let us now return to the starting problems. What if we want
to get the red component of every color in a list? We map
irgb-red
onto the list.
>
(proc-map irgb-red colors-rainbow)
(255 255 255 0 0 102 79)
What if we want the average component? We might use
let
to name the ave
helper,
and then use map with that.
>
(let ((ave (lambda (c) (round (/ (+ (irgb-red c) (irgb-green c) (irgb-blue c)) 3))))) (proc-map ave colors-rainbow))
(85 125 170 85 85 119 68)
Since we can write expressions like that, we would no longer need to write
extract-ave-components
. We probably wouldn't even need
to write extract-red-components
or
extract-max-components
.
That observation suggests a second important moral: Once
you've defined a few higher-order procedures, like
map
, you can often avoid writing other
procedures, since the higher-order procedures let you write more
general expressions.
For example, if we have a list of colors, and we want to compute a
lighter version of each
color in the list, we can use colors-transform
,
proc-map
, or even map
.
>
(define lighter-rainbow (proc-map irgb-lighter colors-rainbow))
There are many advantages to encoding design patterns in higher-order
procedures. An important one is that it stops us from tediously writing
the same thing over and over and over again. Think about writing the
predicates all-integer?
, all-irgb?
,
all-spot?
, and so on and so forth. We've done so
many times. However, as our colleague, John Stone, says (in reference
to writing a sequence of similar procedures),
Writing and testing one of these definitions is an interesting and instructive exercise for the beginning Scheme programmer. Writing and testing another one is good practice. Writing and testing the third one is, frankly, a little tedious. If we then move on to [others], eventually programming is reduced to typing.
So, how do we avoid the repetitious typing? We begin with one of the procedures.
;;; Procedure: ;;; all-int? ;;; Parameters: ;;; lst, a list ;;; Purpose: ;;; Determine if all of the values in lst are integers. ;;; Produces: ;;; ok?, a Boolean ;;; Preconditions: ;;; [Standard] ;;; Postconditions: ;;; If there is an i such that (integer? (list-ref lst i)) ;;; fails to hold, then ok? is false. ;;; Otherwise, ok? is true. (define all-int? (lambda (lst) (or (null? lst) (and (integer? (car lst)) (all-int? (cdr lst))))))
Next, we identify the parts of the procedure that depend on our current type (i.e., that everything is a list).
(define all-WHATEVER
? (lambda (val) (or (null? val) (and (WHATEVER
? (car val)) (all-WHATEVER
? (cdr val))))))
Finally, we remove the dependent part or parts from the procedure name and make them parameters to the modified procedure.
;;; Procedure: ;;; all ;;; Parameters: ;;; pred?, a unary predicate ;;; lst, a list ;;; Purpose: ;;; Determine if pred? holds for all the values in lst. ;;; Produces: ;;; ok?, a Boolean ;;; Preconditions: ;;; [Standard] ;;; Postconditions: ;;; If there is an i such that (pred? (list-ref lst i)) ;;; fails to hold, then ok? is false. ;;; Otherwise, ok? is true. (define all (lambda (pred? lst) (or (null? lst) (and (pred? (car lst)) (all pred? (cdr lst))))))
Here's how we might test whether something is a list of numbers.
>
(all integer? (list 1 2 3))
#t
>
(all integer? (list 1 "two" 3))
#f
We can also define all-int?
using
the all
procedure.
(define all-int? (lambda (lst) (all integer? lst)))
The results are the same.
>
(all-int? (list 1 2 3))
#t
>
(all-int? (list 1 "two" 3))
#f
We have seen that it is possible to write our own higher-order procedures. Scheme also includes a number of built-in higher-order procedures. You can read about many of them in section 6.4 of the Scheme report (r5rs), which is available through the DrRacket Help Desk. Here are some of the more popular ones.
map
Procedure
You already know about the basic use of the map
procedure. You also know how one might
implement it. It turns out that map
has some
additional capabilities. For example, you can apply a procedure to
multiple lists (in which case it takes the corresponding value from
each list).
>
(map + (list 1 2 3) (list .5 .6 .7))
(1.5 2.6 3.7)
>
(define aardvark-grades (list 98 75 90 80 100))
aardvark-grades
>
(define baboon-grades (list 80 82 84 86 88))
baboon-grades
>
(define cheetah-grades (list 50 95 50 95 50))
cheetah-grades
>
(define best-grades (map max aardvark-grades baboon-grades cheetah-grades))
best-grades
>
best-grades
(98 95 90 95 100)
>
(define aardvark-scaled (map (lambda (x) (* 100 x)) (map / aardvark-grades best-grades)))
aardvark-scaled
>
aardvark-scaled
(100 78.94736842 100 84.21052632 100)
apply
Procedure
One of the most important built-in higher-order procedures is
apply
, which takes a procedure and a list as
arguments and invokes the procedure, giving it the elements of the list
as its arguments:
>
(apply string=? (list "foo" "foo"))
#t
>
(apply * (list 3 4 5 6))
360
>
(apply append (list (list 'a 'b 'c) (list 'd) (list 'e 'f) null (list 'g 'h 'i)))
(a b c d e f g h i)
Unfortunately, since and
and
or
are not procedures but
keywords with their own evaluation rules,
we can't use them with apply
.
>
(map string? (list "alpha" 'beta "gamma"))
(#t #f #t)
>
(and #t #f #t)
#f
>
(apply and (map string? (list "alpha" 'beta "gamma")))
Error: eval: unbound variable: and
It might seem odd to write a call to apply
with
these manually constructed lists when we could instead just call the
requested function with the parameters directly. If that is the
case, why have apply
at all? The answer is,
sometimes parameter lists themselves are not known at the time we
write the program and are built on-the-fly, or else it is just plain
easier to build-them on the fly.
As an example, consider the termial
function
from the reading on numeric recursion.
;;; Procedure: ;;; termial ;;; Parameters: ;;; number, a natural number ;;; Purpose: ;;; Compute the sum of natural numbers not greater than a given ;;; natural number ;;; Produces: ;;; sum, a natural number ;;; Preconditions: ;;; number is a number, exact, an integer, and non-negative. ;;; The sum is not larger than the largest integer the language ;;; permits. ;;; Postconditions: ;;; sum is the sum of natural numbers not greater than number. ;;; That is, sum = 0 + 1 + 2 + ... + number (define termial (lambda (number) (if (zero? number) 0 (+ number (termial (- number 1))))))
As the documentation plainly tells us, the result is the sum
1 + 2 + 3 + ... + number
As it turns out, we have a concise way
to generate the list of these numbers by using
iota
. We therefore might just have well as used
apply
and iota
to write
termial
, as follows.
(define termial (lambda (number) (apply + (iota (+ 1 number)))))
Just as it is possible for procedures to take procedures as their parameters, it is also possible for procedures to produce new procedures as their return values. For example, here is a procedure that takes one parameter, a number, and creates a procedure that multiplies its parameters by that number.
;;; Procedure: ;;; make-multiplier ;;; Parameters: ;;; n, a number ;;; Purpose: ;;; Creates a new procedure which multiplies its parameter by n. ;;; Produces: ;;; multiplier, a procedure of one parameter ;;; Preconditions: ;;; n must be a number ;;; Postconditions: ;;; (multiplier v) = n * v (define make-multiplier (lambda (n) ; n is the parameter to make-multiplier ; Return value: A procedure (lambda (v) (* n v))))
Let's test it out.
>
(make-multiplier 5)
#<procedure>
>
(define timesfive (make-multiplier 5))
>
(timesfive 4)
20
>
(timesfive 101)
505
>
(map (make-multiplier 3) (list 1 2 3))
(3 6 9)
We can use the same technique to build the legendary
compose operation that, given two functions,
f
and g
,
builds a function that applies g
and then f
.
;;; Procedure: ;;; compose ;;; Parameters: ;;; f, a unary function ;;; g, a unary function ;;; Purpose: ;;; Functionally compose f and g. ;;; Produces: ;;; fun, a unary function. ;;; Preconditions: ;;; f can be applied to any values g generates. ;;; Postconditions: ;;; fun can be applied to any values g can be applied to. ;;; fun generates values of the type that f generates. ;;; (fun x) = (f (g x)) (define compose (lambda (f g) ; f and g are the parameters to compose ; compose returns a procedure of one parameter (lambda (x) ; that procedure applies g, and then applies f. (f (g x)))))
Here are some tests of that procedure.
>
(define add2 (lambda (x) (+ 2 x)))
>
(define mul5 (lambda (x) (* 5 x)))
>
(define fun1 (compose add2 mul5))
>
(fun1 5)
27
>
(fun1 3)
17
>
(define fun2 (compose mul5 add2))
>
(fun2 5)
35
>
(fun2 3)
25
Especially when using map
, we often write anonymous
procedures that look something like the following.
(lambda (num) (* 2 num))
Even make-multiplier
is actually something we
might want to generalize. You'll note that in that procedure, we
filled in one parameter (n
) of a
two-parameter procedure (*
). In pattern
form, we might write
(lambda (val) (BINARY-PROC ARG1 val))
Let's think about how we might turn that into procedures.
(
creates a new procedure
by filling in the first argument of a binary procedure.
left-section
binary-proc
arg1
)(
creates a new procedure by filling in
the second argument of a binary procedure. We often abbreviate these
two procedures as right-section
binary-proc
arg2
)l-s
and r-s
.
In the following example, we define procedures that multiply their parameter by 2 or subtract 3 from their parameter, or some combination thereof.
>
(define mul2 (left-section * 2))
mul2
>
(define sub3 (right-section - 3))
sub3
>
(map mul2 (list 1 2 3 4 5))
(2 4 6 8 10)
>
(map sub3 (list 1 2 3 4 5))
(-2 -1 0 1 2)
>
(map (compose mul2 sub3) (list 1 2 3 4 5))
(-4 -2 0 2 4)
>
(map (compose sub3 mul2) (list 1 2 3 4 5))
(-1 1 3 5 7)
>
(map (compose (l-s * 2) (r-s - 3)) (list 1 2 3 4 5))
(-4 -2 0 2 4)
>
(map (compose (l-s * 2) (l-s - 3)) (list 1 2 3 4 5))
(4 2 0 -2 -4)
Okay, what does left-section
look like? The definition
is fairly straightforward.
;;; Procedures: ;;; left-section ;;; l-s ;;; Parameters: ;;; binproc, a two-parameter procedure ;;; left, a value ;;; Purpose: ;;; Creates a one-parameter procedure by filling in the first parameter ;; of binproc. ;;; Produces: ;;; unproc, a one-parameter procedure ;;; Preconditions: ;;; left is a valid first parameter for binproc. ;;; Postconditions: ;;; (unproc right) = (binproc left right) (define left-section (lambda (binproc arg1) ; Build a new procedure of one argument (lambda (arg2) ; That calls binproc on the appropriate arguments (binproc arg1 arg2)))) (define l-s left-section)
How is right-section
defined? We leave that as
an exercise for the reader.
Experienced Scheme programmers regularly use left-section
and right-section
, not only in calls to
map
and other higher-order procedures, but also
in defining new procedures. For example, consider the
all-int?
procedure that we previously defined as
(define all-int? (lambda (lst) (all integer? lst)))
Here is an even more concise definition that takes advantage of
l-s
.
(define all-int? (l-s all integer?))
a. What is the definition of a higher-order procedure?
b. Despite its length, this reading only introduced one new built-in Scheme higher-order procedure. What is it?
c. Why is apply
considered a higher-order procedure?
apply
a. The reading gives two versions of
termial
. Which do you prefer? Why?
b. Use a strategy similar to the updated
termial
to rewrite the procedure sum
,
which sums a list of numbers, using apply
,
rather than recursion.
c. If you got the previous check, you might now notice that you've
written a procedure (sum
) that merely calls
another procedure (apply
) with its first
parameter fixed, a pattern that suggests we use sectioning for
further abbreviation. See if you can rewrite
sum
once again so that it uses
l-s
(left-section
) rather
than lambda
to define the procedure.
Hint: Here is another example of using this pattern to abbreviate a procedure definition.
(define double (lambda (number) (* 2 number))) (define double (l-s * 2))