Peter Siebel - Practical Common Lisp

(mapcar #'(lambda (x) (* 2 x)) (list 1 2 3)) ==> (2 4 6)

(mapcar #'+ (list 1 2 3) (list 10 20 30)) ==> (11 22 33)

MAPLIST is just like MAPCAR except instead of passing the elements of the list to the function, it passes the actual cons cells. [143] Thus, MAPLIST is the more primitive of the two functions—if you had only MAPLIST , you could build MAPCAR on top of it, but you couldn't build MAPLIST on top of MAPCAR . Thus, the function has access not only to the value of each element of the list (via the CAR of the cons cell) but also to the rest of the list (via the CDR ).

MAPCAN and MAPCON work like MAPCAR and MAPLIST except for the way they build up their result. While MAPCAR and MAPLIST build a completely new list to hold the results of the function calls, MAPCAN and MAPCON build their result by splicing together the results—which must be lists—as if by NCONC . Thus, each function invocation can provide any number of elements to be included in the result. [144] In Lisp dialects that didn't have filtering functions like REMOVE , the idiomatic way to filter a list was with MAPCAN . (mapcan #'(lambda (x) (if (= x 10) nil (list x))) list) === (remove 10 list) MAPCAN , like MAPCAR , passes the elements of the list to the mapped function while MAPCON , like MAPLIST , passes the cons cells.

Finally, the functions MAPC and MAPL are control constructs disguised as functions—they simply return their first list argument, so they're useful only when the side effects of the mapped function do something interesting. MAPC is the cousin of MAPCAR and MAPCAN while MAPL is in the MAPLIST / MAPCON family.

While cons cells and lists are typically considered to be synonymous, that's not quite right—as I mentioned earlier, you can use lists of lists to represent trees. Just as the functions discussed in this chapter allow you to treat structures built out of cons cells as lists, other functions allow you to use cons cells to represent trees, sets, and two kinds of key/value maps. I'll discuss some of those functions in the next chapter.

As you saw in the previous chapter, the list data type is an illusion created by a set of functions that manipulate cons cells. Common Lisp also provides functions that let you treat data structures built out of cons cells as trees, sets, and lookup tables. In this chapter I'll give you a quick tour of some of these other data structures and the functions for manipulating them. As with the list-manipulation functions, many of these functions will be useful when you start writing more complicated macros and need to manipulate Lisp code as data.

Treating structures built from cons cells as trees is just about as natural as treating them as lists. What is a list of lists, after all, but another way of thinking of a tree? The difference between a function that treats a bunch of cons cells as a list and a function that treats the same bunch of cons cells as a tree has to do with which cons cells the functions traverse to find the values of the list or tree. The cons cells traversed by a list function, called the list structure , are found by starting at the first cons cell and following CDR references until reaching a NIL . The elements of the list are the objects referenced by the CAR s of the cons cells in the list structure. If a cons cell in the list structure has a CAR that references another cons cell, the referenced cons cell is considered to be the head of a list that's an element of the outer list. [145] It's possible to build a chain of cons cells where the CDR of the last cons cell isn't NIL but some other atom. This is called a dotted list because the last cons is a dotted pair. Tree structure , on the other hand, is traversed by following both CAR and CDR references for as long as they point to other cons cells. The values in a tree are thus the atomic—non-cons-cell-values referenced by either the CAR s or the CDR s of the cons cells in the tree structure.

For instance, the following box-and-arrow diagram shows the cons cells that make up the list of lists: ((1 2) (3 4) (5 6)). The list structure includes only the three cons cells inside the dashed box while the tree structure includes all the cons cells.

To see the difference between a list function and a tree function, you can consider how the functions COPY-LIST and COPY-TREE will copy this bunch of cons cells. COPY-LIST , as a list function, copies the cons cells that make up the list structure. That is, it makes a new cons cell corresponding to each of the cons cells inside the dashed box. The CAR s of each of these new cons cells reference the same object as the CAR s of the original cons cells in the list structure. Thus, COPY-LIST doesn't copy the sublists (1 2), (3 4), or (5 6), as shown in this diagram:

COPY-TREE , on the other hand, makes a new cons cell for each of the cons cells in the diagram and links them together in the same structure, as shown in this diagram:

Where a cons cell in the original referenced an atomic value, the corresponding cons cell in the copy will reference the same value. Thus, the only objects referenced in common by the original tree and the copy produced by COPY-TREE are the numbers 5, 6, and the symbol NIL .

Another function that walks both the CAR s and the CDR s of a tree of cons cells is TREE-EQUAL , which compares two trees, considering them equal if the tree structure is the same shape and if the leaves are EQL (or if they satisfy the test supplied with the :testkeyword argument).

Some other tree-centric functions are the tree analogs to the SUBSTITUTE and NSUBSTITUTE sequence functions and their -IFand -IF-NOTvariants. The function SUBST , like SUBSTITUTE , takes a new item, an old item, and a tree (as opposed to a sequence), along with :keyand :testkeyword arguments, and it returns a new tree with the same shape as the original tree but with all instances of the old item replaced with the new item. For example: