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.
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 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))
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)
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:
NIL in place of each input we wish to
exclude from the output.
? (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)
WHENreturnsNILif the condition isNIL. 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.
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.
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.
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
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).