Suppose that we are writing a program where we need to take a list of numbers and produce a corresponding lists with numbers ten times as big.
Notice that we already have a procedure, map, that can iterate
over a list, apply a function to each item, and return the list of function
values. We also have a multiplication procedure, * that can
multiply numbers by any value we want.
We can't just write (map * some-list), though, because when
map iterates over a single list, it expects a procedure that
takes exactly one argument, and * takes two arguments.
Somehow, we need to supply the argument 10 to each of the
calls map makes to *.
What we need is a one-argument function that multiplies its argument
by ten. We could define our own multiplication-by-ten procedure,
*10, and then use map to apply it to the elements of
some-list.
(define (*10 number) (* 10 number)) (map *10 some-list)
Here we've specialized * to create *10---we've taken a
function with some number of arguments, and produced a function
with fewer arguments, which is equivalent to calling the original
procedure with the missing argument always the same.
If *10 is only used in one place, there's really no need
to create a named procedure--we can just use a lambda
expression to create the procedure where we need it, at the
call to map:
(map (lambda (number)
(* 10 number))
some-list)
Here we create an anonymous procedure that multiplies its argument by
10, and pass that procedure and a list to map, which will
map the procedure over the list and return the corresponding list
of results.
It is often a good idea to design procedures with specialization in mind.
Consider assoc, which has variants assq and assv;
the only difference between them is what comparison operator they
use.
Likewise, member has variants memq and memv.
Consider the similarities between member, memv, and
memq. All of them do almost the same thing, with the
difference being which equality test they use during a search.
We can define a general procedure, mem, which expresses
the similarities between these procedures, and then specialize
that procedure. That is, in writing mem, we'll leave a
"hole" for the comparison operator. That hole is just an
argument.
Our general procedure will look like member, except that
it will take an argument saying which test to use. In Scheme,
this is easy--we can simply hand it a first-class procedure
like equal? or eq?, or any other test we want
to use, and have it call that procedure to perform the test.
(define (mem test-proc thing lis)
(if (null? lis)
#f
(if (test-proc (car lis) thing)
lis
(mem test-proc thing (cdr lis)))))
To get the effect of (member some-key some-list), we can
write (mem equal? some-key some-list).
Note that here we're not calling equal? directly--we're just
passing the value of the variable equal? (i.e., the procedure
first-class procedure object equal?) to mem.
mem receives this value when the argument variable
test-proc is bound, and can call it by that name.
(In the *10 example, we specialized * with data--the
number 10---but here we're specializing mem with
a procedure. The same technique works, because procedures are
data objects, and can be passed as arguments like any other data,
then called as procedures.)
If Scheme didn't provide member, we could easily define it by
specializing mem---we simply define member to call
mem, but always pass equal? as the first argument:
(define (member thing lis) (mem equal? thing lis))
Likewise, we could define memq and memv by specializing
mem with eq? and eqv?, respectively.
This kind of function specialization is particularly useful when you have a pattern for a procedure, but may need arbitrary variants of it in the future.
For example, suppose you want to search a list of lists, and you want your search routine to return the first sublist whose first two elements match a particular two-element list. (This might be an ordered list of birthdays, and you could be searching for the part of the list that starts with a particular month of a particular year.)
You might search the list for any list whose first elements are
1964 and December, by handing it a target list
(1964 December), like this:
(mem-first-two? '(1964 December)
'((1961 January 15 "Susan")
(1964 March 28 "Edward")
(1964 March 29 "Selena")
(1964 December 31 "Anton")
(1965 January 8 "Booker"))))
and get back the result
((1964 December 31 "Anton") (1965 January 8 "Booker"))))
member, memq, and memv are useless for this,
but it's pretty easy with mem. First we define a match
predicate for our purpose:
(define (first-two-eqv? target thing)
(and (eqv? (car target) (car thing))
(eqv? (cadr target) (cadr thing))))
Then we curry mem with that predicate to create our search
procedure:
(define (mem-first-two? thing lis) (mem first-two-eqv? thing lis))
If first-two-eqv? is only likely to be used in mem-first-two,
we can put it inside mem-first-two, as a local procedure, instead
of leaving it hanging out where it can be called from other procedures.
This is a good idea for a procedure that is so specialized that it's unlikely
to be useful in any other way--especially if you're sure it works for
what you designed it for, but think it may be tricky to use for slightly
different purposes. (For example, we've chosen to use the eqv? test
for matching list elements, but for some purposes this might be the
wrong choice.)
(define (mem-first-two thing lis)
(let ((first-two-eqv? (lambda (target thing)
(and (eqv? (car target) (car thing))
(eqv? (cadr target) (cadr thing))))))
(mem first-two-eqv? thing lis)))
In this routine, first-two-eqv? is only called from one place--the
call to mem. Rather than defining it as a named procedure,
using letrec and lambda, we can simply use the lambda
expression at the one place the procedure is needed:
(define (mem-first-two thing lis)
(mem (lambda (target thing)
(and (eqv? (car target) (car thing))
(eqv? (cadr target) (cadr thing))))
target
lis))
This idiom is very common in situations where you need a small procedure in exactly one place.
Likewise, if mem-first-two itself is only useful in one place,
it would be reasonable to avoid making it a procedure at all, and
instead to simply call mem from that place:
...
(mem (lambda (target thing)
(and (eqv? (car target) (car thing))
(eqv? (cadr target) (cadr thing))))
target
lis)
...