Other Structures

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.

1Adapted from The Matrix (http://us.imdb.com/Quotes?0133093)

2**CONS** was originally short for the verb construct.

3When the place given to **SETF** is a **CAR** or **CDR**, it expands into a call to the function **RPLACA** or **RPLACD**; some old-school Lispers—the same ones who still use **SETQ**--will still use **RPLACA** and **RPLACD** directly, but modern style is to use **SETF** of **CAR** or **CDR**.

4Typically, simple objects such as numbers are drawn within the appropriate box, and more complex objects will be drawn outside the box with an arrow from the box indicating the reference. This actually corresponds well with how many Common Lisp implementations work—although all objects are conceptually stored by reference, certain simple immutable objects can be stored directly in a cons cell.

5The phrase for-side-effect is used in the language standard, but recycling is my own invention; most Lisp literature simply uses the term destructive for both kinds of operations, leading to the confusion I’m trying to dispel.

6The string functions **NSTRING-CAPITALIZE**, **NSTRING-DOWNCASE**, and **NSTRING-UPCASE** are similar—they return the same results as their N-less counterparts but are specified to modify their string argument in place.

7For example, in an examination of all uses of recycling functions in the Common Lisp Open Code Collection (CLOCC), a diverse set of libraries written by various authors, instances of the **PUSH**/**NREVERSE** idiom accounted for nearly half of all uses of recycling functions.

8There are, of course, other ways to do this same thing. The extended **LOOP** macro, for instance, makes it particularly easy and likely generates code that’s even more efficient than the **PUSH**/ **NREVERSE** version.

9This idiom accounts for 30 percent of uses of recycling in the CLOCC code base.

10**SORT** and **STABLE-SORT** can be used as for-side-effect operations on vectors, but since they still return the sorted vector, you should ignore that fact and use them for return values for the sake of consistency.

11**NTH** is roughly equivalent to the sequence function **ELT** but works only with lists. Also, confusingly, **NTH** takes the index as the first argument, the opposite of **ELT**. Another difference is that **ELT** will signal an error if you try to access an element at an index greater than or equal to the length of the list, but **NTH** will return **NIL**.

12In particular, they used to be used to extract the various parts of expressions passed to macros before the invention of destructuring parameter lists. For example, you could take apart the following expression:

(when (> x 10) (print x))

Like this:

;; the condition
(cadr '(when (> x 10) (print x))) ==> (> X 10)

;; the body, as a list
(cddr '(when (> x 10) (print x))) ==> ((PRINT X))

13Thus, **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**.

14In 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)