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:

- makes a list of each result we wish to retain in the output, or
- returns
`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)

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

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

Copyright © 1995-2001, 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.