Go to the first, previous, next, last section, table of contents.

Procedure Specialization

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)
...

Go to the first, previous, next, last section, table of contents.