Common Lisp the Language, 2nd Edition


next up previous contents index
Next: The ``Program Feature'' Up: Iteration Previous: Simple Iteration Constructs

7.8.4. Mapping

Mapping is a type of iteration in which a function is successively applied to pieces of one or more sequences. The result of the iteration is a sequence containing the respective results of the function applications. There are several options for the way in which the pieces of the list are chosen and for what is done with the results returned by the applications of the function.

The function map may be used to map over any kind of sequence. The following functions operate only on lists.


[Function]

mapcar function list &rest more-lists 
maplist function list &rest more-lists 
mapc function list &rest more-lists 
mapl function list &rest more-lists 
mapcan function list &rest more-lists 
mapcon function list &rest more-lists

For each of these mapping functions, the first argument is a function and the rest must be lists. The function must take as many arguments as there are lists.

mapcar operates on successive elements of the lists. First the function is applied to the car of each list, then to the cadr of each list, and so on. (Ideally all the lists are the same length; if not, the iteration terminates when the shortest list runs out, and excess elements in other lists are ignored.) The value returned by mapcar is a list of the results of the successive calls to the function. For example:

(mapcar #'abs '(3 -4 2 -5 -6)) => (3 4 2 5 6) 
(mapcar #'cons '(a b c) '(1 2 3)) => ((a . 1) (b . 2) (c . 3))

maplist is like mapcar except that the function is applied to the lists and successive cdr's of those lists rather than to successive elements of the lists. For example:

(maplist #'(lambda (x) (cons 'foo x)) 
         '(a b c d)) 
   => ((foo a b c d) (foo b c d) (foo c d) (foo d))

(maplist #'(lambda (x) (if (member (car x) (cdr x)) 0 1))) 
         '(a b a c d b c)) 
   => (0 0 1 0 1 1 1) 
   ;An entry is 1 if the corresponding element of the input 
   ; list was the last instance of that element in the input list.

mapl and mapc are like maplist and mapcar, respectively, except that they do not accumulate the results of calling the function.


Compatibility note: In all Lisp systems since Lisp 1.5, mapl has been called map. In the chapter on sequences it is explained why this was a bad choice. Here the name map is used for the far more useful generic sequence mapper, in closer accordance with the computer science literature, especially the growing body of papers on functional programming. Note that this remark, predating the design of the Common Lisp Object System, uses the term ``generic'' in a generic sense and not necessarily in the technical sense used by CLOS (see chapter 2).

These functions are used when the function is being called merely for its side effects rather than for its returned values. The value returned by mapl or mapc is the second argument, that is, the first sequence argument.

mapcan and mapcon are like mapcar and maplist, respectively, except that they combine the results of the function using nconc instead of list. That is,

(mapcon f x1 ... xn) 
   == (apply #'nconc (maplist f x1 ... xn))

and similarly for the relationship between mapcan and mapcar. Conceptually, these functions allow the mapped function to return a variable number of items to be put into the output list. This is particularly useful for effectively returning zero or one item:

(mapcan #'(lambda (x) (and (numberp x) (list x))) 
        '(a 1 b c 3 4 d 5)) 
   => (1 3 4 5)

In this case the function serves as a filter; this is a standard Lisp idiom using mapcan. (The function remove-if-not might have been useful in this particular context, however.) Remember that nconc is a destructive operation, and therefore so are mapcan and mapcon; the lists returned by the function are altered in order to concatenate them.

Sometimes a do or a straightforward recursion is preferable to a mapping operation; however, the mapping functions should be used wherever they naturally apply because this increases the clarity of the code.

The functional argument to a mapping function must be acceptable to apply; it cannot be a macro or the name of a special form. Of course, there is nothing wrong with using a function that has &optional and &rest parameters as the functional argument.

change_begin
X3J13 voted in June 1988 (FUNCTION-TYPE)   to allow the function to be only of type symbol or function; a lambda-expression is no longer acceptable as a functional argument. One must use the function special form or the abbreviation #' before a lambda-expression that appears as an explicit argument form.

X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict user side effects; see section 7.9.
change_end



next up previous contents index
Next: The ``Program Feature'' Up: Iteration Previous: Simple Iteration Constructs


AI.Repository@cs.cmu.edu