Chapter 12 - Mapping Instead of Iteration

In this chapter we'll survey of a group of functions collectively known as mapping functions. You can think of a mapping function as a kind of special purpose iterator. Every mapping function expects you to supply a function. A typical mapping function applies your function to every element of the supplied list(s). One variation on this theme applies your function to successive sublists.

A sequence is a generalization of the list data type. Vectors (one-dimensional arrays) and lists are specializations of the sequence data type. Some mapping functions work only with lists as inputs, while others accept sequences.

MAPCAR, MAPC, and MAPCAN process successive list elements

The first group of mapping functions processes successive elements of lists. The mapping functions in this group differ in how they construct a return value.

MAPCAR processes successive elements of one or more supplied lists. You must supply a function that accepts as many arguments as the number of lists you supply to MAPCAR, which applies your function to successive elements and combines the function's results into a freshly constructed list. The mapping stops upon reaching the end of the shortest list; MAPCAR's result has as many elements as the shortest input list.

MAPC does not combine the results of applying your function to successive elements of the input list(s). Instead, it processes the inputs just for effect, and returns the first input list as the result of MAPC.

MAPCAN combines results using the destructive function NCONC. Since NCONC -- like its nondestructive counterpart APPEND -- expects its arguments to be lists, the function you supply to MAPCAN must always return a list.

? (mapcar #'atom (list 1 '(2) "foo" nil))
(T NIL T T)
? (mapcar #'+ (list 1 2 3) (list 4 5 6))
(5 7 9)
? (mapc #'(lambda (x y) (print (* x y))) (list 1 0 2) (list 3 4 5))

3
0
10
(1 0 2)
? (mapcan #'list (list 1 2 3) (list 4 5 6))
(1 4 2 5 3 6)
? (mapcan #'(lambda (a b) (list (cons a b))) (list 1 2 3) (list 4 5 6))
((1 . 4) (2 . 5) (3 . 6))

MAPLIST, MAPL, and MAPCON process successive sublists

MAPLIST processes successive sublists of one or more supplied lists. You must supply a function that accepts as many arguments as the number of lists you supply to MAPLIST, which applies your function to successive sublists and combines the function's results into a freshly constructed list. The mapping stops upon reaching the end of the shortest list; MAPLIST's result has as many elements as the shortest input list.

MAPL does not combine the results of applying your function to successive sublists of the input list(s). Instead, it processes the inputs just for effect, and returns the first input list as the result of MAPL.

MAPCON combines results using the destructive function NCONC. Since NCONC -- like its nondestructive counterpart APPEND -- expects its arguments to be lists, the function you supply to MAPCON must always return a list.

? (maplist #'list (list 1 2 3) (list 4 5 6))
(((1 2 3) (4 5 6)) ((2 3) (5 6)) ((3) (6)))
? (mapl #'(lambda (x y) (print (append x y))) (list 1 0 2) (list 3 4 5))

(1 0 2 3 4 5) 
(0 2 4 5) 
(2 5) 
(1 0 2)
? (mapcon #'list (list 1 2 3) (list 4 5 6))
((1 2 3) (4 5 6) (2 3) (5 6) (3) (6))

MAP and MAP-INTO work on sequences, not just lists

A sequence is either a list or a vector (a one-dimensional array). The previous group of mapping functions (MAPCAR et al) processes successive CARs or CDRs of their input lists. MAP and MAP-INTO process successive elements of their input sequences.

MAP requires that you specify the type of its result using one of the following designators:

Designator   Result
----------   ------
NIL          NIL
'LIST        a list
'VECTOR      a vector

Note that you can also specify subtypes of LIST or VECTOR -- your Lisp implementation may be able to optimize the storage of the result based on the type you specify.

? (map nil #'+ (list 1 2 3) (list 4 5 6))
NIL
? (map 'list #'+ (list 1 2 3) (list 4 5 6))
(5 7 9)
? (map 'vector #'+ (list 1 2 3) (list 4 5 6))
#(5 7 9)
? (map '(vector number 3) #'+ (list 1 2 3) (list 4 5 6))
#(5 7 9)

MAP-INTO is a destructive version of MAP. The first argument is a sequence that receives the results of the mapping. Mapping stops upon reaching the end of the result sequence or any of the input sequences. (Therefore, if you specify NIL as the result sequence, no mapping is performed since NIL is a list of length zero.) The input sequences are not modified. The modified result sequence is returned as the value of MAP-INTO.

? (let ((a (make-sequence 'list 3)))
    (print a)
    (map-into a #'+ (list 1 2 3) (list 4 5 6))
    a)

(NIL NIL NIL)
(5 7 9)
? (let ((a (make-sequence 'vector 3)))
    (print a)
    (map-into a #'+ (list 1 2 3) (list 4 5 6))
    a)

#(0 0 0)
#(5 7 9)

Your Lisp implementation may print different initial values for the unmodified sequences in the above examples. If you need to specify a certain initial value for MAKE-SEQUENCE, use the :INITIAL-ELEMENT keyword argument:

? (let ((a (make-sequence 'list 3 :initial-element 0)))
    (print a)
    (map-into a #'+ (list 1 2 3) (list 4 5 6))
    a)

(0 0 0)
(5 7 9)

Mapping functions are good for filtering

A filter passes some of its inputs through to its output, and drops others. We can use mapping functions to implement filters by taking note of the behavior of APPEND:

? (append '(1) nil '(3) '(4))
(1 3 4)

The NIL argument (which is equivalent to the empty list) simply "disappears" from the result. This is the key observation that we need to construct a filter. We'll use MAPCAN to map over our input list(s) and supply a mapping function that:

? (defun filter-even-numbers (numbers)
    (mapcan #'(lambda (n) (when (evenp n) (list n))) numbers))
FILTER-EVEN-NUMBERS
? (filter-even-numbers (list 1 2 3 4 5 6 7 8))
(2 4 6 8)
WHEN returns NIL if the condition is NIL. We could have written (if (evenp n) (list n) nil) instead.

Here's a slightly more complex filter that returns a list of evenly divisible pairs of numerators and denominators:

? (defun filter-evenly-divisible (numerators denominators)
    (mapcan #'(lambda (n d)
                (if (zerop (mod n d))
                  (list (list n d))
                  nil))
            numerators denominators))
? (filter-evenly-divisible (list 7 8 9 10 11 12)
                           (list 1 4 5  5  2  3))
((7 1) (8 4) (10 5) (12 3))

The functions REMOVE-IF and REMOVE-IF-NOT (and their destructive counterparts, DELETE-IF and DELETE-IF-NOT) filter a single sequence, but can't be used for multiple sequences (as in the example above). Use REMOVE-IF and the like if it will make your code clearer. See Chapter 13 for further details.

It's better to avoid mapping if you care about efficiency

Most Lisp systems will generate more efficient code to call a function that is known during compilation than a function that can change at run time. Mapping functions accept a functional argument, and most compilers will generate code that supports run time function binding -- even if you specify a "constant" function, such as #'+. Also, the run time call may incur extra overhead to generate a list of arguments for the function's application.

Therefore, if you are concerned about efficiency you should write map-like functions using iteration instead of mapping functions. But do this only when you are sure that efficiency is an issue for the portion of the program you intend to rewrite. See Chapter 28 for a discussion of profiling, which can help you find your program's performance bottlenecks.

Predicate mapping functions test sequences

Sometimes you may need to apply a test to some input sequences and return a truth value based upon what the test returned for all of the inputs. For example, you might want to know whether any number in a sequence is outside of a specified range, or whether every word is at least five letters long. You could construct these tests from the mapping functions described above, but that would be more verbose (and less efficient) than using the predicate mapping functions provided by Lisp.

SOME, EVERY, NOTANY, NOTEVERY

The built in predicate mapping functions expect you to supply a test function (a.k.a. predicate) and one or more input sequences. The predicate is applied to successive elements of the input sequences until the the result of the mapping function can be determined.

Function   Condition
--------   ---------
SOME       user-supplied predicate succeeds on at least one input
EVERY      user-supplied predicate succeeds on every input
NOTANY     complement of SOME
NOTEVERY   complement of EVERY

For example, SOME examines inputs so long as the predicate is false; the tests stop -- and SOME returns a true value -- as soon as the predicate is true for some input(s). If the predicate is false for every input, SOME returns a false value.

Similarly, EVERY examines inputs so long as the predicate is true; the tests stop -- and EVERY returns a false value -- as soon as the predicate is false for some input(s). If the predicate is true for every input, EVERY returns a true value.

? (some #'(lambda (n) (or (< n 0) (> n 100))) (list 0 1 99 100))
NIL
? (some #'(lambda (n) (or (< n 0) (> n 100))) (list -1 0 1 99 100))
T
? (every #'(lambda (w) (>= (length w) 5)) (list "bears" "bulls" "racoon"))
T
? (every #'(lambda (w) (>= (length w) 5)) (list "bears" "cat" "racoon"))
NIL

And of course, the predicate mapping functions handle multiple sequences as you'd expect.

? (some #'>> (list 0 1 2 3 4 5) (list 0 0 3 2 6))
T

REDUCE combines sequence elements

While we're on the subject of mapping, wouldn't it be nice to be able to combine all of the elements of a sequence using some function? REDUCE does just that, accepting a function (of two or zero arguments) and a sequence. If the sequence is longer than one element, REDUCE combines the results of applying the function to successive elements of the sequence. For example:

? (reduce #'* (list 1 2 3 4 5)) (* (* (* (* 1 2) 3) 4) 5) 
120
? (reduce #'- (list 10 2 3 1)) ; (- (- (- 10 2) 3) 1) 
4

If the sequence is of length one, REDUCE returns the sequence and the function is not applied. If the sequence is of length zero, REDUCE applies the function with no arguments and returns the value returned by the function. (In the case of arithmetic functions, this is the identity value for the operation.)

Various keyword arguments let you specify a subsequence for REDUCE, or that REDUCE should combine elements in a right-associative manner (i.e. from the end of the sequence, rather than from the beginning).


Contents | Cover
Chapter 11 | Chapter 13
Copyright © 1995-1999, David B. Lamkins
All Rights Reserved Worldwide

This book may not be reproduced without the written consent of its author. Online distribution is restricted to the author's site.