Commit | Line | Data |
---|---|---|
73804d4b RS |
1 | @c -*-texinfo-*- |
2 | @c This is part of the GNU Emacs Lisp Reference Manual. | |
f9f59935 | 3 | @c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998 Free Software Foundation, Inc. |
73804d4b RS |
4 | @c See the file elisp.texi for copying conditions. |
5 | @setfilename ../info/lists | |
6 | @node Lists, Sequences Arrays Vectors, Strings and Characters, Top | |
7 | @chapter Lists | |
8 | @cindex list | |
9 | @cindex element (of list) | |
10 | ||
11 | A @dfn{list} represents a sequence of zero or more elements (which may | |
12 | be any Lisp objects). The important difference between lists and | |
13 | vectors is that two or more lists can share part of their structure; in | |
14 | addition, you can insert or delete elements in a list without copying | |
15 | the whole list. | |
16 | ||
17 | @menu | |
18 | * Cons Cells:: How lists are made out of cons cells. | |
19 | * Lists as Boxes:: Graphical notation to explain lists. | |
20 | * List-related Predicates:: Is this object a list? Comparing two lists. | |
21 | * List Elements:: Extracting the pieces of a list. | |
22 | * Building Lists:: Creating list structure. | |
23 | * Modifying Lists:: Storing new pieces into an existing list. | |
24 | * Sets And Lists:: A list can represent a finite mathematical set. | |
25 | * Association Lists:: A list can represent a finite relation or mapping. | |
26 | @end menu | |
27 | ||
28 | @node Cons Cells | |
29 | @section Lists and Cons Cells | |
30 | @cindex lists and cons cells | |
31 | @cindex @code{nil} and lists | |
32 | ||
33 | Lists in Lisp are not a primitive data type; they are built up from | |
2b3fc6c3 RS |
34 | @dfn{cons cells}. A cons cell is a data object that represents an |
35 | ordered pair. It records two Lisp objects, one labeled as the @sc{car}, | |
36 | and the other labeled as the @sc{cdr}. These names are traditional; see | |
37 | @ref{Cons Cell Type}. @sc{cdr} is pronounced ``could-er.'' | |
73804d4b RS |
38 | |
39 | A list is a series of cons cells chained together, one cons cell per | |
40 | element of the list. By convention, the @sc{car}s of the cons cells are | |
41 | the elements of the list, and the @sc{cdr}s are used to chain the list: | |
42 | the @sc{cdr} of each cons cell is the following cons cell. The @sc{cdr} | |
43 | of the last cons cell is @code{nil}. This asymmetry between the | |
44 | @sc{car} and the @sc{cdr} is entirely a matter of convention; at the | |
45 | level of cons cells, the @sc{car} and @sc{cdr} slots have the same | |
46 | characteristics. | |
47 | ||
2b3fc6c3 RS |
48 | @cindex list structure |
49 | Because most cons cells are used as part of lists, the phrase | |
50 | @dfn{list structure} has come to mean any structure made out of cons | |
51 | cells. | |
52 | ||
73804d4b RS |
53 | The symbol @code{nil} is considered a list as well as a symbol; it is |
54 | the list with no elements. For convenience, the symbol @code{nil} is | |
55 | considered to have @code{nil} as its @sc{cdr} (and also as its | |
56 | @sc{car}). | |
57 | ||
58 | The @sc{cdr} of any nonempty list @var{l} is a list containing all the | |
59 | elements of @var{l} except the first. | |
60 | ||
61 | @node Lists as Boxes | |
62 | @comment node-name, next, previous, up | |
63 | @section Lists as Linked Pairs of Boxes | |
64 | @cindex box representation for lists | |
65 | @cindex lists represented as boxes | |
66 | @cindex cons cell as box | |
67 | ||
68 | A cons cell can be illustrated as a pair of boxes. The first box | |
69 | represents the @sc{car} and the second box represents the @sc{cdr}. | |
70 | Here is an illustration of the two-element list, @code{(tulip lily)}, | |
71 | made from two cons cells: | |
72 | ||
73 | @example | |
74 | @group | |
75 | --------------- --------------- | |
76 | | car | cdr | | car | cdr | | |
77 | | tulip | o---------->| lily | nil | | |
78 | | | | | | | | |
79 | --------------- --------------- | |
80 | @end group | |
81 | @end example | |
82 | ||
83 | Each pair of boxes represents a cons cell. Each box ``refers to'', | |
84 | ``points to'' or ``contains'' a Lisp object. (These terms are | |
85 | synonymous.) The first box, which is the @sc{car} of the first cons | |
86 | cell, contains the symbol @code{tulip}. The arrow from the @sc{cdr} of | |
87 | the first cons cell to the second cons cell indicates that the @sc{cdr} | |
88 | of the first cons cell points to the second cons cell. | |
89 | ||
90 | The same list can be illustrated in a different sort of box notation | |
91 | like this: | |
92 | ||
93 | @example | |
94 | @group | |
969fe9b5 RS |
95 | --- --- --- --- |
96 | | | |--> | | |--> nil | |
97 | --- --- --- --- | |
73804d4b RS |
98 | | | |
99 | | | | |
100 | --> tulip --> lily | |
101 | @end group | |
102 | @end example | |
103 | ||
104 | Here is a more complex illustration, showing the three-element list, | |
105 | @code{((pine needles) oak maple)}, the first element of which is a | |
106 | two-element list: | |
107 | ||
108 | @example | |
109 | @group | |
969fe9b5 RS |
110 | --- --- --- --- --- --- |
111 | | | |--> | | |--> | | |--> nil | |
112 | --- --- --- --- --- --- | |
73804d4b RS |
113 | | | | |
114 | | | | | |
115 | | --> oak --> maple | |
116 | | | |
969fe9b5 RS |
117 | | --- --- --- --- |
118 | --> | | |--> | | |--> nil | |
119 | --- --- --- --- | |
73804d4b RS |
120 | | | |
121 | | | | |
122 | --> pine --> needles | |
123 | @end group | |
124 | @end example | |
125 | ||
126 | The same list represented in the first box notation looks like this: | |
127 | ||
128 | @example | |
129 | @group | |
130 | -------------- -------------- -------------- | |
131 | | car | cdr | | car | cdr | | car | cdr | | |
132 | | o | o------->| oak | o------->| maple | nil | | |
133 | | | | | | | | | | | | |
134 | -- | --------- -------------- -------------- | |
135 | | | |
136 | | | |
137 | | -------------- ---------------- | |
138 | | | car | cdr | | car | cdr | | |
139 | ------>| pine | o------->| needles | nil | | |
140 | | | | | | | | |
141 | -------------- ---------------- | |
142 | @end group | |
143 | @end example | |
144 | ||
2b3fc6c3 RS |
145 | @xref{Cons Cell Type}, for the read and print syntax of cons cells and |
146 | lists, and for more ``box and arrow'' illustrations of lists. | |
73804d4b RS |
147 | |
148 | @node List-related Predicates | |
149 | @section Predicates on Lists | |
150 | ||
151 | The following predicates test whether a Lisp object is an atom, is a | |
152 | cons cell or is a list, or whether it is the distinguished object | |
153 | @code{nil}. (Many of these predicates can be defined in terms of the | |
154 | others, but they are used so often that it is worth having all of them.) | |
155 | ||
156 | @defun consp object | |
157 | This function returns @code{t} if @var{object} is a cons cell, @code{nil} | |
158 | otherwise. @code{nil} is not a cons cell, although it @emph{is} a list. | |
159 | @end defun | |
160 | ||
161 | @defun atom object | |
162 | @cindex atoms | |
163 | This function returns @code{t} if @var{object} is an atom, @code{nil} | |
164 | otherwise. All objects except cons cells are atoms. The symbol | |
165 | @code{nil} is an atom and is also a list; it is the only Lisp object | |
2b3fc6c3 | 166 | that is both. |
73804d4b RS |
167 | |
168 | @example | |
169 | (atom @var{object}) @equiv{} (not (consp @var{object})) | |
170 | @end example | |
171 | @end defun | |
172 | ||
173 | @defun listp object | |
174 | This function returns @code{t} if @var{object} is a cons cell or | |
175 | @code{nil}. Otherwise, it returns @code{nil}. | |
176 | ||
177 | @example | |
178 | @group | |
179 | (listp '(1)) | |
180 | @result{} t | |
181 | @end group | |
182 | @group | |
183 | (listp '()) | |
184 | @result{} t | |
185 | @end group | |
186 | @end example | |
187 | @end defun | |
188 | ||
189 | @defun nlistp object | |
190 | This function is the opposite of @code{listp}: it returns @code{t} if | |
191 | @var{object} is not a list. Otherwise, it returns @code{nil}. | |
192 | ||
193 | @example | |
194 | (listp @var{object}) @equiv{} (not (nlistp @var{object})) | |
195 | @end example | |
196 | @end defun | |
197 | ||
198 | @defun null object | |
199 | This function returns @code{t} if @var{object} is @code{nil}, and | |
200 | returns @code{nil} otherwise. This function is identical to @code{not}, | |
201 | but as a matter of clarity we use @code{null} when @var{object} is | |
202 | considered a list and @code{not} when it is considered a truth value | |
203 | (see @code{not} in @ref{Combining Conditions}). | |
204 | ||
205 | @example | |
206 | @group | |
207 | (null '(1)) | |
208 | @result{} nil | |
209 | @end group | |
210 | @group | |
211 | (null '()) | |
212 | @result{} t | |
213 | @end group | |
214 | @end example | |
215 | @end defun | |
216 | ||
ec221d13 | 217 | @need 2000 |
73804d4b RS |
218 | |
219 | @node List Elements | |
220 | @section Accessing Elements of Lists | |
221 | @cindex list elements | |
222 | ||
223 | @defun car cons-cell | |
224 | This function returns the value pointed to by the first pointer of the | |
225 | cons cell @var{cons-cell}. Expressed another way, this function | |
226 | returns the @sc{car} of @var{cons-cell}. | |
227 | ||
228 | As a special case, if @var{cons-cell} is @code{nil}, then @code{car} | |
229 | is defined to return @code{nil}; therefore, any list is a valid argument | |
230 | for @code{car}. An error is signaled if the argument is not a cons cell | |
231 | or @code{nil}. | |
232 | ||
233 | @example | |
234 | @group | |
235 | (car '(a b c)) | |
236 | @result{} a | |
237 | @end group | |
238 | @group | |
239 | (car '()) | |
240 | @result{} nil | |
241 | @end group | |
242 | @end example | |
243 | @end defun | |
244 | ||
245 | @defun cdr cons-cell | |
246 | This function returns the value pointed to by the second pointer of | |
247 | the cons cell @var{cons-cell}. Expressed another way, this function | |
248 | returns the @sc{cdr} of @var{cons-cell}. | |
249 | ||
250 | As a special case, if @var{cons-cell} is @code{nil}, then @code{cdr} | |
251 | is defined to return @code{nil}; therefore, any list is a valid argument | |
252 | for @code{cdr}. An error is signaled if the argument is not a cons cell | |
253 | or @code{nil}. | |
254 | ||
255 | @example | |
256 | @group | |
257 | (cdr '(a b c)) | |
258 | @result{} (b c) | |
259 | @end group | |
260 | @group | |
261 | (cdr '()) | |
262 | @result{} nil | |
263 | @end group | |
264 | @end example | |
265 | @end defun | |
266 | ||
267 | @defun car-safe object | |
268 | This function lets you take the @sc{car} of a cons cell while avoiding | |
269 | errors for other data types. It returns the @sc{car} of @var{object} if | |
270 | @var{object} is a cons cell, @code{nil} otherwise. This is in contrast | |
271 | to @code{car}, which signals an error if @var{object} is not a list. | |
272 | ||
273 | @example | |
274 | @group | |
275 | (car-safe @var{object}) | |
276 | @equiv{} | |
277 | (let ((x @var{object})) | |
278 | (if (consp x) | |
279 | (car x) | |
280 | nil)) | |
281 | @end group | |
282 | @end example | |
283 | @end defun | |
284 | ||
285 | @defun cdr-safe object | |
286 | This function lets you take the @sc{cdr} of a cons cell while | |
287 | avoiding errors for other data types. It returns the @sc{cdr} of | |
288 | @var{object} if @var{object} is a cons cell, @code{nil} otherwise. | |
289 | This is in contrast to @code{cdr}, which signals an error if | |
290 | @var{object} is not a list. | |
291 | ||
292 | @example | |
293 | @group | |
294 | (cdr-safe @var{object}) | |
295 | @equiv{} | |
296 | (let ((x @var{object})) | |
297 | (if (consp x) | |
298 | (cdr x) | |
299 | nil)) | |
300 | @end group | |
301 | @end example | |
302 | @end defun | |
303 | ||
304 | @defun nth n list | |
305 | This function returns the @var{n}th element of @var{list}. Elements | |
306 | are numbered starting with zero, so the @sc{car} of @var{list} is | |
307 | element number zero. If the length of @var{list} is @var{n} or less, | |
308 | the value is @code{nil}. | |
309 | ||
310 | If @var{n} is negative, @code{nth} returns the first element of | |
311 | @var{list}. | |
312 | ||
313 | @example | |
314 | @group | |
315 | (nth 2 '(1 2 3 4)) | |
316 | @result{} 3 | |
317 | @end group | |
318 | @group | |
319 | (nth 10 '(1 2 3 4)) | |
320 | @result{} nil | |
321 | @end group | |
322 | @group | |
323 | (nth -3 '(1 2 3 4)) | |
324 | @result{} 1 | |
325 | ||
326 | (nth n x) @equiv{} (car (nthcdr n x)) | |
327 | @end group | |
328 | @end example | |
969fe9b5 RS |
329 | |
330 | The function @code{elt} is similar, but applies to any kind of sequence. | |
331 | For historical reasons, it takes its arguments in the opposite order. | |
332 | @xref{Sequence Functions}. | |
73804d4b RS |
333 | @end defun |
334 | ||
335 | @defun nthcdr n list | |
336 | This function returns the @var{n}th @sc{cdr} of @var{list}. In other | |
f9f59935 | 337 | words, it skips past the first @var{n} links of @var{list} and returns |
73804d4b RS |
338 | what follows. |
339 | ||
340 | If @var{n} is zero or negative, @code{nthcdr} returns all of | |
341 | @var{list}. If the length of @var{list} is @var{n} or less, | |
342 | @code{nthcdr} returns @code{nil}. | |
343 | ||
344 | @example | |
345 | @group | |
346 | (nthcdr 1 '(1 2 3 4)) | |
347 | @result{} (2 3 4) | |
348 | @end group | |
349 | @group | |
350 | (nthcdr 10 '(1 2 3 4)) | |
351 | @result{} nil | |
352 | @end group | |
353 | @group | |
354 | (nthcdr -3 '(1 2 3 4)) | |
355 | @result{} (1 2 3 4) | |
356 | @end group | |
357 | @end example | |
358 | @end defun | |
359 | ||
f9f59935 | 360 | @tindex safe-length |
969fe9b5 | 361 | @defun safe-length list |
f9f59935 RS |
362 | This function returns the length of @var{list}, with no risk |
363 | of either an error or an infinite loop. | |
364 | ||
365 | If @var{list} is not really a list, @code{safe-length} returns 0. If | |
366 | @var{list} is circular, it returns a finite value which is at least the | |
367 | number of distinct elements. | |
368 | @end defun | |
369 | ||
969fe9b5 RS |
370 | The most common way to compute the length of a list, when you are not |
371 | worried that it may be circular, is with @code{length}. @xref{Sequence | |
372 | Functions}. | |
373 | ||
f9f59935 | 374 | @tindex caar |
969fe9b5 RS |
375 | @defun caar cons-cell |
376 | This is the same as @code{(car (car @var{cons-cell}))}. | |
f9f59935 RS |
377 | @end defun |
378 | ||
379 | @tindex cadr | |
969fe9b5 RS |
380 | @defun cadr cons-cell |
381 | This is the same as @code{(car (cdr @var{cons-cell}))} | |
382 | or @code{(nth 1 @var{cons-cell})}. | |
f9f59935 RS |
383 | @end defun |
384 | ||
385 | @tindex cdar | |
969fe9b5 RS |
386 | @defun cdar cons-cell |
387 | This is the same as @code{(cdr (car @var{cons-cell}))}. | |
f9f59935 RS |
388 | @end defun |
389 | ||
390 | @tindex cddr | |
969fe9b5 RS |
391 | @defun cddr cons-cell |
392 | This is the same as @code{(cdr (cdr @var{cons-cell}))} | |
393 | or @code{(nthcdr 2 @var{cons-cell})}. | |
f9f59935 RS |
394 | @end defun |
395 | ||
73804d4b RS |
396 | @node Building Lists |
397 | @comment node-name, next, previous, up | |
398 | @section Building Cons Cells and Lists | |
399 | @cindex cons cells | |
400 | @cindex building lists | |
401 | ||
402 | Many functions build lists, as lists reside at the very heart of Lisp. | |
403 | @code{cons} is the fundamental list-building function; however, it is | |
404 | interesting to note that @code{list} is used more times in the source | |
405 | code for Emacs than @code{cons}. | |
406 | ||
407 | @defun cons object1 object2 | |
408 | This function is the fundamental function used to build new list | |
409 | structure. It creates a new cons cell, making @var{object1} the | |
410 | @sc{car}, and @var{object2} the @sc{cdr}. It then returns the new cons | |
411 | cell. The arguments @var{object1} and @var{object2} may be any Lisp | |
412 | objects, but most often @var{object2} is a list. | |
413 | ||
414 | @example | |
415 | @group | |
416 | (cons 1 '(2)) | |
417 | @result{} (1 2) | |
418 | @end group | |
419 | @group | |
420 | (cons 1 '()) | |
421 | @result{} (1) | |
422 | @end group | |
423 | @group | |
424 | (cons 1 2) | |
425 | @result{} (1 . 2) | |
426 | @end group | |
427 | @end example | |
428 | ||
429 | @cindex consing | |
430 | @code{cons} is often used to add a single element to the front of a | |
431 | list. This is called @dfn{consing the element onto the list}. For | |
432 | example: | |
433 | ||
434 | @example | |
435 | (setq list (cons newelt list)) | |
436 | @end example | |
437 | ||
438 | Note that there is no conflict between the variable named @code{list} | |
439 | used in this example and the function named @code{list} described below; | |
440 | any symbol can serve both purposes. | |
441 | @end defun | |
442 | ||
443 | @defun list &rest objects | |
444 | This function creates a list with @var{objects} as its elements. The | |
445 | resulting list is always @code{nil}-terminated. If no @var{objects} | |
446 | are given, the empty list is returned. | |
447 | ||
448 | @example | |
449 | @group | |
450 | (list 1 2 3 4 5) | |
451 | @result{} (1 2 3 4 5) | |
452 | @end group | |
453 | @group | |
454 | (list 1 2 '(3 4 5) 'foo) | |
455 | @result{} (1 2 (3 4 5) foo) | |
456 | @end group | |
457 | @group | |
458 | (list) | |
459 | @result{} nil | |
460 | @end group | |
461 | @end example | |
462 | @end defun | |
463 | ||
464 | @defun make-list length object | |
465 | This function creates a list of length @var{length}, in which all the | |
466 | elements have the identical value @var{object}. Compare | |
467 | @code{make-list} with @code{make-string} (@pxref{Creating Strings}). | |
468 | ||
469 | @example | |
470 | @group | |
471 | (make-list 3 'pigs) | |
472 | @result{} (pigs pigs pigs) | |
473 | @end group | |
474 | @group | |
475 | (make-list 0 'pigs) | |
476 | @result{} nil | |
477 | @end group | |
478 | @end example | |
479 | @end defun | |
480 | ||
481 | @defun append &rest sequences | |
482 | @cindex copying lists | |
483 | This function returns a list containing all the elements of | |
969fe9b5 RS |
484 | @var{sequences}. The @var{sequences} may be lists, vectors, |
485 | bool-vectors, or strings, but the last one should usually be a list. | |
486 | All arguments except the last one are copied, so none of the arguments | |
487 | is altered. (See @code{nconc} in @ref{Rearrangement}, for a way to join | |
488 | lists with no copying.) | |
2b3fc6c3 RS |
489 | |
490 | More generally, the final argument to @code{append} may be any Lisp | |
491 | object. The final argument is not copied or converted; it becomes the | |
492 | @sc{cdr} of the last cons cell in the new list. If the final argument | |
493 | is itself a list, then its elements become in effect elements of the | |
494 | result list. If the final element is not a list, the result is a | |
495 | ``dotted list'' since its final @sc{cdr} is not @code{nil} as required | |
496 | in a true list. | |
73804d4b | 497 | |
2b3fc6c3 | 498 | Here is an example of using @code{append}: |
73804d4b RS |
499 | |
500 | @example | |
501 | @group | |
502 | (setq trees '(pine oak)) | |
503 | @result{} (pine oak) | |
504 | (setq more-trees (append '(maple birch) trees)) | |
505 | @result{} (maple birch pine oak) | |
506 | @end group | |
507 | ||
508 | @group | |
509 | trees | |
510 | @result{} (pine oak) | |
511 | more-trees | |
512 | @result{} (maple birch pine oak) | |
513 | @end group | |
514 | @group | |
515 | (eq trees (cdr (cdr more-trees))) | |
516 | @result{} t | |
517 | @end group | |
518 | @end example | |
519 | ||
2b3fc6c3 RS |
520 | You can see how @code{append} works by looking at a box diagram. The |
521 | variable @code{trees} is set to the list @code{(pine oak)} and then the | |
522 | variable @code{more-trees} is set to the list @code{(maple birch pine | |
523 | oak)}. However, the variable @code{trees} continues to refer to the | |
524 | original list: | |
73804d4b RS |
525 | |
526 | @smallexample | |
527 | @group | |
528 | more-trees trees | |
529 | | | | |
969fe9b5 RS |
530 | | --- --- --- --- -> --- --- --- --- |
531 | --> | | |--> | | |--> | | |--> | | |--> nil | |
532 | --- --- --- --- --- --- --- --- | |
73804d4b RS |
533 | | | | | |
534 | | | | | | |
535 | --> maple -->birch --> pine --> oak | |
536 | @end group | |
537 | @end smallexample | |
538 | ||
539 | An empty sequence contributes nothing to the value returned by | |
540 | @code{append}. As a consequence of this, a final @code{nil} argument | |
541 | forces a copy of the previous argument. | |
542 | ||
543 | @example | |
544 | @group | |
545 | trees | |
546 | @result{} (pine oak) | |
547 | @end group | |
548 | @group | |
969fe9b5 | 549 | (setq wood (append trees nil)) |
73804d4b RS |
550 | @result{} (pine oak) |
551 | @end group | |
552 | @group | |
553 | wood | |
554 | @result{} (pine oak) | |
555 | @end group | |
556 | @group | |
557 | (eq wood trees) | |
558 | @result{} nil | |
559 | @end group | |
560 | @end example | |
561 | ||
562 | @noindent | |
563 | This once was the usual way to copy a list, before the function | |
564 | @code{copy-sequence} was invented. @xref{Sequences Arrays Vectors}. | |
565 | ||
969fe9b5 RS |
566 | Here we show the use of vectors and strings as arguments to @code{append}: |
567 | ||
568 | @example | |
569 | @group | |
570 | (append [a b] "cd" nil) | |
571 | @result{} (a b 99 100) | |
572 | @end group | |
573 | @end example | |
574 | ||
73804d4b RS |
575 | With the help of @code{apply}, we can append all the lists in a list of |
576 | lists: | |
577 | ||
578 | @example | |
579 | @group | |
580 | (apply 'append '((a b c) nil (x y z) nil)) | |
581 | @result{} (a b c x y z) | |
582 | @end group | |
583 | @end example | |
584 | ||
585 | If no @var{sequences} are given, @code{nil} is returned: | |
586 | ||
587 | @example | |
588 | @group | |
589 | (append) | |
590 | @result{} nil | |
591 | @end group | |
592 | @end example | |
593 | ||
2b3fc6c3 RS |
594 | Here are some examples where the final argument is not a list: |
595 | ||
596 | @example | |
597 | (append '(x y) 'z) | |
bfe721d1 | 598 | @result{} (x y . z) |
2b3fc6c3 | 599 | (append '(x y) [z]) |
bfe721d1 | 600 | @result{} (x y . [z]) |
2b3fc6c3 RS |
601 | @end example |
602 | ||
603 | @noindent | |
604 | The second example shows that when the final argument is a sequence but | |
605 | not a list, the sequence's elements do not become elements of the | |
606 | resulting list. Instead, the sequence becomes the final @sc{cdr}, like | |
607 | any other non-list final argument. | |
73804d4b | 608 | |
22697dac KH |
609 | The @code{append} function also allows integers as arguments. It |
610 | converts them to strings of digits, making up the decimal print | |
611 | representation of the integer, and then uses the strings instead of the | |
612 | original integers. @strong{Don't use this feature; we plan to eliminate | |
613 | it. If you already use this feature, change your programs now!} The | |
614 | proper way to convert an integer to a decimal number in this way is with | |
615 | @code{format} (@pxref{Formatting Strings}) or @code{number-to-string} | |
616 | (@pxref{String Conversion}). | |
73804d4b RS |
617 | @end defun |
618 | ||
619 | @defun reverse list | |
620 | This function creates a new list whose elements are the elements of | |
621 | @var{list}, but in reverse order. The original argument @var{list} is | |
622 | @emph{not} altered. | |
623 | ||
624 | @example | |
625 | @group | |
626 | (setq x '(1 2 3 4)) | |
627 | @result{} (1 2 3 4) | |
628 | @end group | |
629 | @group | |
630 | (reverse x) | |
631 | @result{} (4 3 2 1) | |
632 | x | |
633 | @result{} (1 2 3 4) | |
634 | @end group | |
635 | @end example | |
636 | @end defun | |
637 | ||
638 | @node Modifying Lists | |
639 | @section Modifying Existing List Structure | |
640 | ||
641 | You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the | |
642 | primitives @code{setcar} and @code{setcdr}. | |
643 | ||
644 | @cindex CL note---@code{rplaca} vrs @code{setcar} | |
645 | @quotation | |
646 | @findex rplaca | |
647 | @findex rplacd | |
648 | @b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and | |
649 | @code{rplacd} to alter list structure; they change structure the same | |
650 | way as @code{setcar} and @code{setcdr}, but the Common Lisp functions | |
651 | return the cons cell while @code{setcar} and @code{setcdr} return the | |
652 | new @sc{car} or @sc{cdr}. | |
653 | @end quotation | |
654 | ||
655 | @menu | |
656 | * Setcar:: Replacing an element in a list. | |
657 | * Setcdr:: Replacing part of the list backbone. | |
658 | This can be used to remove or add elements. | |
659 | * Rearrangement:: Reordering the elements in a list; combining lists. | |
660 | @end menu | |
661 | ||
662 | @node Setcar | |
663 | @subsection Altering List Elements with @code{setcar} | |
664 | ||
2b3fc6c3 RS |
665 | Changing the @sc{car} of a cons cell is done with @code{setcar}. When |
666 | used on a list, @code{setcar} replaces one element of a list with a | |
667 | different element. | |
73804d4b RS |
668 | |
669 | @defun setcar cons object | |
670 | This function stores @var{object} as the new @sc{car} of @var{cons}, | |
671 | replacing its previous @sc{car}. It returns the value @var{object}. | |
672 | For example: | |
673 | ||
674 | @example | |
675 | @group | |
676 | (setq x '(1 2)) | |
677 | @result{} (1 2) | |
678 | @end group | |
679 | @group | |
680 | (setcar x 4) | |
681 | @result{} 4 | |
682 | @end group | |
683 | @group | |
684 | x | |
685 | @result{} (4 2) | |
686 | @end group | |
687 | @end example | |
688 | @end defun | |
689 | ||
690 | When a cons cell is part of the shared structure of several lists, | |
691 | storing a new @sc{car} into the cons changes one element of each of | |
692 | these lists. Here is an example: | |
693 | ||
694 | @example | |
695 | @group | |
696 | ;; @r{Create two lists that are partly shared.} | |
697 | (setq x1 '(a b c)) | |
698 | @result{} (a b c) | |
699 | (setq x2 (cons 'z (cdr x1))) | |
700 | @result{} (z b c) | |
701 | @end group | |
702 | ||
703 | @group | |
704 | ;; @r{Replace the @sc{car} of a shared link.} | |
705 | (setcar (cdr x1) 'foo) | |
706 | @result{} foo | |
707 | x1 ; @r{Both lists are changed.} | |
708 | @result{} (a foo c) | |
709 | x2 | |
710 | @result{} (z foo c) | |
711 | @end group | |
712 | ||
713 | @group | |
714 | ;; @r{Replace the @sc{car} of a link that is not shared.} | |
715 | (setcar x1 'baz) | |
716 | @result{} baz | |
717 | x1 ; @r{Only one list is changed.} | |
718 | @result{} (baz foo c) | |
719 | x2 | |
720 | @result{} (z foo c) | |
721 | @end group | |
722 | @end example | |
723 | ||
724 | Here is a graphical depiction of the shared structure of the two lists | |
725 | in the variables @code{x1} and @code{x2}, showing why replacing @code{b} | |
726 | changes them both: | |
727 | ||
728 | @example | |
729 | @group | |
969fe9b5 RS |
730 | --- --- --- --- --- --- |
731 | x1---> | | |----> | | |--> | | |--> nil | |
732 | --- --- --- --- --- --- | |
73804d4b RS |
733 | | --> | | |
734 | | | | | | |
735 | --> a | --> b --> c | |
736 | | | |
969fe9b5 RS |
737 | --- --- | |
738 | x2--> | | |-- | |
739 | --- --- | |
73804d4b RS |
740 | | |
741 | | | |
742 | --> z | |
743 | @end group | |
744 | @end example | |
745 | ||
746 | Here is an alternative form of box diagram, showing the same relationship: | |
747 | ||
748 | @example | |
749 | @group | |
750 | x1: | |
751 | -------------- -------------- -------------- | |
752 | | car | cdr | | car | cdr | | car | cdr | | |
753 | | a | o------->| b | o------->| c | nil | | |
754 | | | | -->| | | | | | | |
755 | -------------- | -------------- -------------- | |
756 | | | |
757 | x2: | | |
758 | -------------- | | |
759 | | car | cdr | | | |
760 | | z | o---- | |
761 | | | | | |
762 | -------------- | |
763 | @end group | |
764 | @end example | |
765 | ||
766 | @node Setcdr | |
767 | @subsection Altering the CDR of a List | |
768 | ||
769 | The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}: | |
770 | ||
771 | @defun setcdr cons object | |
2b3fc6c3 RS |
772 | This function stores @var{object} as the new @sc{cdr} of @var{cons}, |
773 | replacing its previous @sc{cdr}. It returns the value @var{object}. | |
73804d4b RS |
774 | @end defun |
775 | ||
776 | Here is an example of replacing the @sc{cdr} of a list with a | |
777 | different list. All but the first element of the list are removed in | |
778 | favor of a different sequence of elements. The first element is | |
779 | unchanged, because it resides in the @sc{car} of the list, and is not | |
780 | reached via the @sc{cdr}. | |
781 | ||
782 | @example | |
783 | @group | |
784 | (setq x '(1 2 3)) | |
785 | @result{} (1 2 3) | |
786 | @end group | |
787 | @group | |
788 | (setcdr x '(4)) | |
789 | @result{} (4) | |
790 | @end group | |
791 | @group | |
792 | x | |
793 | @result{} (1 4) | |
794 | @end group | |
795 | @end example | |
796 | ||
797 | You can delete elements from the middle of a list by altering the | |
798 | @sc{cdr}s of the cons cells in the list. For example, here we delete | |
799 | the second element, @code{b}, from the list @code{(a b c)}, by changing | |
800 | the @sc{cdr} of the first cell: | |
801 | ||
802 | @example | |
803 | @group | |
804 | (setq x1 '(a b c)) | |
805 | @result{} (a b c) | |
806 | (setcdr x1 (cdr (cdr x1))) | |
807 | @result{} (c) | |
808 | x1 | |
809 | @result{} (a c) | |
810 | @end group | |
811 | @end example | |
812 | ||
bda144f4 | 813 | @need 4000 |
73804d4b RS |
814 | Here is the result in box notation: |
815 | ||
816 | @example | |
817 | @group | |
818 | -------------------- | |
819 | | | | |
820 | -------------- | -------------- | -------------- | |
821 | | car | cdr | | | car | cdr | -->| car | cdr | | |
822 | | a | o----- | b | o-------->| c | nil | | |
823 | | | | | | | | | | | |
824 | -------------- -------------- -------------- | |
825 | @end group | |
826 | @end example | |
827 | ||
828 | @noindent | |
829 | The second cons cell, which previously held the element @code{b}, still | |
830 | exists and its @sc{car} is still @code{b}, but it no longer forms part | |
831 | of this list. | |
832 | ||
833 | It is equally easy to insert a new element by changing @sc{cdr}s: | |
834 | ||
835 | @example | |
836 | @group | |
837 | (setq x1 '(a b c)) | |
838 | @result{} (a b c) | |
839 | (setcdr x1 (cons 'd (cdr x1))) | |
840 | @result{} (d b c) | |
841 | x1 | |
842 | @result{} (a d b c) | |
843 | @end group | |
844 | @end example | |
845 | ||
846 | Here is this result in box notation: | |
847 | ||
848 | @smallexample | |
849 | @group | |
850 | -------------- ------------- ------------- | |
851 | | car | cdr | | car | cdr | | car | cdr | | |
852 | | a | o | -->| b | o------->| c | nil | | |
853 | | | | | | | | | | | | | |
854 | --------- | -- | ------------- ------------- | |
855 | | | | |
856 | ----- -------- | |
857 | | | | |
858 | | --------------- | | |
859 | | | car | cdr | | | |
860 | -->| d | o------ | |
861 | | | | | |
862 | --------------- | |
863 | @end group | |
864 | @end smallexample | |
865 | ||
866 | @node Rearrangement | |
867 | @subsection Functions that Rearrange Lists | |
868 | @cindex rearrangement of lists | |
869 | @cindex modification of lists | |
870 | ||
871 | Here are some functions that rearrange lists ``destructively'' by | |
872 | modifying the @sc{cdr}s of their component cons cells. We call these | |
873 | functions ``destructive'' because they chew up the original lists passed | |
874 | to them as arguments, to produce a new list that is the returned value. | |
875 | ||
2b3fc6c3 RS |
876 | @ifinfo |
877 | See @code{delq}, in @ref{Sets And Lists}, for another function | |
878 | that modifies cons cells. | |
879 | @end ifinfo | |
880 | @iftex | |
881 | The function @code{delq} in the following section is another example | |
882 | of destructive list manipulation. | |
883 | @end iftex | |
884 | ||
73804d4b RS |
885 | @defun nconc &rest lists |
886 | @cindex concatenating lists | |
887 | @cindex joining lists | |
888 | This function returns a list containing all the elements of @var{lists}. | |
889 | Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are | |
890 | @emph{not} copied. Instead, the last @sc{cdr} of each of the | |
891 | @var{lists} is changed to refer to the following list. The last of the | |
892 | @var{lists} is not altered. For example: | |
893 | ||
894 | @example | |
895 | @group | |
896 | (setq x '(1 2 3)) | |
897 | @result{} (1 2 3) | |
898 | @end group | |
899 | @group | |
900 | (nconc x '(4 5)) | |
901 | @result{} (1 2 3 4 5) | |
902 | @end group | |
903 | @group | |
904 | x | |
905 | @result{} (1 2 3 4 5) | |
906 | @end group | |
907 | @end example | |
908 | ||
909 | Since the last argument of @code{nconc} is not itself modified, it is | |
910 | reasonable to use a constant list, such as @code{'(4 5)}, as in the | |
911 | above example. For the same reason, the last argument need not be a | |
912 | list: | |
913 | ||
914 | @example | |
915 | @group | |
916 | (setq x '(1 2 3)) | |
917 | @result{} (1 2 3) | |
918 | @end group | |
919 | @group | |
920 | (nconc x 'z) | |
921 | @result{} (1 2 3 . z) | |
922 | @end group | |
923 | @group | |
924 | x | |
925 | @result{} (1 2 3 . z) | |
926 | @end group | |
927 | @end example | |
928 | ||
969fe9b5 RS |
929 | However, the other arguments (all but the last) must be lists. |
930 | ||
73804d4b RS |
931 | A common pitfall is to use a quoted constant list as a non-last |
932 | argument to @code{nconc}. If you do this, your program will change | |
933 | each time you run it! Here is what happens: | |
934 | ||
935 | @smallexample | |
936 | @group | |
937 | (defun add-foo (x) ; @r{We want this function to add} | |
938 | (nconc '(foo) x)) ; @r{@code{foo} to the front of its arg.} | |
939 | @end group | |
940 | ||
941 | @group | |
942 | (symbol-function 'add-foo) | |
943 | @result{} (lambda (x) (nconc (quote (foo)) x)) | |
944 | @end group | |
945 | ||
946 | @group | |
947 | (setq xx (add-foo '(1 2))) ; @r{It seems to work.} | |
948 | @result{} (foo 1 2) | |
949 | @end group | |
950 | @group | |
951 | (setq xy (add-foo '(3 4))) ; @r{What happened?} | |
952 | @result{} (foo 1 2 3 4) | |
953 | @end group | |
954 | @group | |
955 | (eq xx xy) | |
956 | @result{} t | |
957 | @end group | |
958 | ||
959 | @group | |
960 | (symbol-function 'add-foo) | |
961 | @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x))) | |
962 | @end group | |
963 | @end smallexample | |
964 | @end defun | |
965 | ||
966 | @defun nreverse list | |
967 | @cindex reversing a list | |
968 | This function reverses the order of the elements of @var{list}. | |
2b3fc6c3 RS |
969 | Unlike @code{reverse}, @code{nreverse} alters its argument by reversing |
970 | the @sc{cdr}s in the cons cells forming the list. The cons cell that | |
971 | used to be the last one in @var{list} becomes the first cell of the | |
972 | value. | |
73804d4b RS |
973 | |
974 | For example: | |
975 | ||
976 | @example | |
977 | @group | |
978 | (setq x '(1 2 3 4)) | |
979 | @result{} (1 2 3 4) | |
980 | @end group | |
981 | @group | |
982 | x | |
983 | @result{} (1 2 3 4) | |
984 | (nreverse x) | |
985 | @result{} (4 3 2 1) | |
986 | @end group | |
987 | @group | |
988 | ;; @r{The cell that was first is now last.} | |
989 | x | |
990 | @result{} (1) | |
991 | @end group | |
992 | @end example | |
993 | ||
994 | To avoid confusion, we usually store the result of @code{nreverse} | |
995 | back in the same variable which held the original list: | |
996 | ||
997 | @example | |
998 | (setq x (nreverse x)) | |
999 | @end example | |
1000 | ||
1001 | Here is the @code{nreverse} of our favorite example, @code{(a b c)}, | |
1002 | presented graphically: | |
1003 | ||
1004 | @smallexample | |
1005 | @group | |
1006 | @r{Original list head:} @r{Reversed list:} | |
1007 | ------------- ------------- ------------ | |
1008 | | car | cdr | | car | cdr | | car | cdr | | |
1009 | | a | nil |<-- | b | o |<-- | c | o | | |
1010 | | | | | | | | | | | | | | | |
1011 | ------------- | --------- | - | -------- | - | |
1012 | | | | | | |
1013 | ------------- ------------ | |
1014 | @end group | |
1015 | @end smallexample | |
1016 | @end defun | |
1017 | ||
1018 | @defun sort list predicate | |
1019 | @cindex stable sort | |
1020 | @cindex sorting lists | |
1021 | This function sorts @var{list} stably, though destructively, and | |
1022 | returns the sorted list. It compares elements using @var{predicate}. A | |
1023 | stable sort is one in which elements with equal sort keys maintain their | |
1024 | relative order before and after the sort. Stability is important when | |
1025 | successive sorts are used to order elements according to different | |
1026 | criteria. | |
1027 | ||
1028 | The argument @var{predicate} must be a function that accepts two | |
1029 | arguments. It is called with two elements of @var{list}. To get an | |
1030 | increasing order sort, the @var{predicate} should return @code{t} if the | |
1031 | first element is ``less than'' the second, or @code{nil} if not. | |
1032 | ||
1033 | The destructive aspect of @code{sort} is that it rearranges the cons | |
1034 | cells forming @var{list} by changing @sc{cdr}s. A nondestructive sort | |
1035 | function would create new cons cells to store the elements in their | |
1036 | sorted order. If you wish to make a sorted copy without destroying the | |
1037 | original, copy it first with @code{copy-sequence} and then sort. | |
1038 | ||
1039 | Sorting does not change the @sc{car}s of the cons cells in @var{list}; | |
1040 | the cons cell that originally contained the element @code{a} in | |
1041 | @var{list} still has @code{a} in its @sc{car} after sorting, but it now | |
1042 | appears in a different position in the list due to the change of | |
1043 | @sc{cdr}s. For example: | |
1044 | ||
1045 | @example | |
1046 | @group | |
1047 | (setq nums '(1 3 2 6 5 4 0)) | |
1048 | @result{} (1 3 2 6 5 4 0) | |
1049 | @end group | |
1050 | @group | |
1051 | (sort nums '<) | |
1052 | @result{} (0 1 2 3 4 5 6) | |
1053 | @end group | |
1054 | @group | |
1055 | nums | |
1056 | @result{} (1 2 3 4 5 6) | |
1057 | @end group | |
1058 | @end example | |
1059 | ||
1060 | @noindent | |
f9f59935 RS |
1061 | @strong{Warning}: Note that the list in @code{nums} no longer contains |
1062 | 0; this is the same cons cell that it was before, but it is no longer | |
1063 | the first one in the list. Don't assume a variable that formerly held | |
1064 | the argument now holds the entire sorted list! Instead, save the result | |
1065 | of @code{sort} and use that. Most often we store the result back into | |
1066 | the variable that held the original list: | |
73804d4b RS |
1067 | |
1068 | @example | |
1069 | (setq nums (sort nums '<)) | |
1070 | @end example | |
1071 | ||
1072 | @xref{Sorting}, for more functions that perform sorting. | |
1073 | See @code{documentation} in @ref{Accessing Documentation}, for a | |
1074 | useful example of @code{sort}. | |
1075 | @end defun | |
1076 | ||
73804d4b RS |
1077 | @node Sets And Lists |
1078 | @section Using Lists as Sets | |
1079 | @cindex lists as sets | |
1080 | @cindex sets | |
1081 | ||
1082 | A list can represent an unordered mathematical set---simply consider a | |
1083 | value an element of a set if it appears in the list, and ignore the | |
1084 | order of the list. To form the union of two sets, use @code{append} (as | |
1085 | long as you don't mind having duplicate elements). Other useful | |
1086 | functions for sets include @code{memq} and @code{delq}, and their | |
1087 | @code{equal} versions, @code{member} and @code{delete}. | |
1088 | ||
b5ef0e92 | 1089 | @cindex CL note---lack @code{union}, @code{intersection} |
73804d4b RS |
1090 | @quotation |
1091 | @b{Common Lisp note:} Common Lisp has functions @code{union} (which | |
1092 | avoids duplicate elements) and @code{intersection} for set operations, | |
1093 | but GNU Emacs Lisp does not have them. You can write them in Lisp if | |
1094 | you wish. | |
1095 | @end quotation | |
1096 | ||
1097 | @defun memq object list | |
1098 | @cindex membership in a list | |
1099 | This function tests to see whether @var{object} is a member of | |
1100 | @var{list}. If it is, @code{memq} returns a list starting with the | |
1101 | first occurrence of @var{object}. Otherwise, it returns @code{nil}. | |
1102 | The letter @samp{q} in @code{memq} says that it uses @code{eq} to | |
1103 | compare @var{object} against the elements of the list. For example: | |
1104 | ||
1105 | @example | |
1106 | @group | |
2b3fc6c3 RS |
1107 | (memq 'b '(a b c b a)) |
1108 | @result{} (b c b a) | |
73804d4b RS |
1109 | @end group |
1110 | @group | |
1111 | (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.} | |
1112 | @result{} nil | |
1113 | @end group | |
1114 | @end example | |
1115 | @end defun | |
1116 | ||
1117 | @defun delq object list | |
1118 | @cindex deletion of elements | |
1119 | This function destructively removes all elements @code{eq} to | |
1120 | @var{object} from @var{list}. The letter @samp{q} in @code{delq} says | |
1121 | that it uses @code{eq} to compare @var{object} against the elements of | |
1122 | the list, like @code{memq}. | |
1123 | @end defun | |
1124 | ||
1125 | When @code{delq} deletes elements from the front of the list, it does so | |
1126 | simply by advancing down the list and returning a sublist that starts | |
1127 | after those elements: | |
1128 | ||
1129 | @example | |
1130 | @group | |
1131 | (delq 'a '(a b c)) @equiv{} (cdr '(a b c)) | |
1132 | @end group | |
1133 | @end example | |
1134 | ||
1135 | When an element to be deleted appears in the middle of the list, | |
1136 | removing it involves changing the @sc{cdr}s (@pxref{Setcdr}). | |
1137 | ||
1138 | @example | |
1139 | @group | |
2b3fc6c3 RS |
1140 | (setq sample-list '(a b c (4))) |
1141 | @result{} (a b c (4)) | |
73804d4b RS |
1142 | @end group |
1143 | @group | |
2b3fc6c3 RS |
1144 | (delq 'a sample-list) |
1145 | @result{} (b c (4)) | |
73804d4b RS |
1146 | @end group |
1147 | @group | |
1148 | sample-list | |
2b3fc6c3 | 1149 | @result{} (a b c (4)) |
73804d4b RS |
1150 | @end group |
1151 | @group | |
2b3fc6c3 | 1152 | (delq 'c sample-list) |
34e1af81 | 1153 | @result{} (a b (4)) |
73804d4b RS |
1154 | @end group |
1155 | @group | |
1156 | sample-list | |
34e1af81 | 1157 | @result{} (a b (4)) |
73804d4b RS |
1158 | @end group |
1159 | @end example | |
1160 | ||
bfe721d1 KH |
1161 | Note that @code{(delq 'c sample-list)} modifies @code{sample-list} to |
1162 | splice out the third element, but @code{(delq 'a sample-list)} does not | |
73804d4b RS |
1163 | splice anything---it just returns a shorter list. Don't assume that a |
1164 | variable which formerly held the argument @var{list} now has fewer | |
1165 | elements, or that it still holds the original list! Instead, save the | |
1166 | result of @code{delq} and use that. Most often we store the result back | |
1167 | into the variable that held the original list: | |
1168 | ||
1169 | @example | |
1170 | (setq flowers (delq 'rose flowers)) | |
1171 | @end example | |
1172 | ||
1173 | In the following example, the @code{(4)} that @code{delq} attempts to match | |
1174 | and the @code{(4)} in the @code{sample-list} are not @code{eq}: | |
1175 | ||
1176 | @example | |
1177 | @group | |
1178 | (delq '(4) sample-list) | |
2b3fc6c3 | 1179 | @result{} (a c (4)) |
73804d4b RS |
1180 | @end group |
1181 | @end example | |
1182 | ||
1183 | The following two functions are like @code{memq} and @code{delq} but use | |
969fe9b5 RS |
1184 | @code{equal} rather than @code{eq} to compare elements. @xref{Equality |
1185 | Predicates}. | |
73804d4b RS |
1186 | |
1187 | @defun member object list | |
1188 | The function @code{member} tests to see whether @var{object} is a member | |
1189 | of @var{list}, comparing members with @var{object} using @code{equal}. | |
1190 | If @var{object} is a member, @code{member} returns a list starting with | |
1191 | its first occurrence in @var{list}. Otherwise, it returns @code{nil}. | |
1192 | ||
1193 | Compare this with @code{memq}: | |
1194 | ||
1195 | @example | |
1196 | @group | |
1197 | (member '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are @code{equal}.} | |
1198 | @result{} ((2)) | |
1199 | @end group | |
1200 | @group | |
1201 | (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.} | |
1202 | @result{} nil | |
1203 | @end group | |
1204 | @group | |
1205 | ;; @r{Two strings with the same contents are @code{equal}.} | |
1206 | (member "foo" '("foo" "bar")) | |
1207 | @result{} ("foo" "bar") | |
1208 | @end group | |
1209 | @end example | |
1210 | @end defun | |
1211 | ||
1212 | @defun delete object list | |
1213 | This function destructively removes all elements @code{equal} to | |
1214 | @var{object} from @var{list}. It is to @code{delq} as @code{member} is | |
1215 | to @code{memq}: it uses @code{equal} to compare elements with | |
1216 | @var{object}, like @code{member}; when it finds an element that matches, | |
1217 | it removes the element just as @code{delq} would. For example: | |
1218 | ||
1219 | @example | |
1220 | @group | |
1221 | (delete '(2) '((2) (1) (2))) | |
b5ef0e92 | 1222 | @result{} ((1)) |
73804d4b RS |
1223 | @end group |
1224 | @end example | |
1225 | @end defun | |
1226 | ||
1227 | @quotation | |
1228 | @b{Common Lisp note:} The functions @code{member} and @code{delete} in | |
1229 | GNU Emacs Lisp are derived from Maclisp, not Common Lisp. The Common | |
1230 | Lisp versions do not use @code{equal} to compare elements. | |
1231 | @end quotation | |
1232 | ||
bfe721d1 KH |
1233 | See also the function @code{add-to-list}, in @ref{Setting Variables}, |
1234 | for another way to add an element to a list stored in a variable. | |
1235 | ||
73804d4b RS |
1236 | @node Association Lists |
1237 | @section Association Lists | |
1238 | @cindex association list | |
1239 | @cindex alist | |
1240 | ||
1241 | An @dfn{association list}, or @dfn{alist} for short, records a mapping | |
1242 | from keys to values. It is a list of cons cells called | |
1243 | @dfn{associations}: the @sc{car} of each cell is the @dfn{key}, and the | |
1244 | @sc{cdr} is the @dfn{associated value}.@footnote{This usage of ``key'' | |
1245 | is not related to the term ``key sequence''; it means a value used to | |
1246 | look up an item in a table. In this case, the table is the alist, and | |
1247 | the alist associations are the items.} | |
1248 | ||
1249 | Here is an example of an alist. The key @code{pine} is associated with | |
1250 | the value @code{cones}; the key @code{oak} is associated with | |
1251 | @code{acorns}; and the key @code{maple} is associated with @code{seeds}. | |
1252 | ||
1253 | @example | |
1254 | @group | |
1255 | '((pine . cones) | |
1256 | (oak . acorns) | |
1257 | (maple . seeds)) | |
1258 | @end group | |
1259 | @end example | |
1260 | ||
1261 | The associated values in an alist may be any Lisp objects; so may the | |
1262 | keys. For example, in the following alist, the symbol @code{a} is | |
1263 | associated with the number @code{1}, and the string @code{"b"} is | |
1264 | associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of | |
1265 | the alist element: | |
1266 | ||
1267 | @example | |
1268 | ((a . 1) ("b" 2 3)) | |
1269 | @end example | |
1270 | ||
1271 | Sometimes it is better to design an alist to store the associated | |
1272 | value in the @sc{car} of the @sc{cdr} of the element. Here is an | |
1273 | example: | |
1274 | ||
1275 | @example | |
1276 | '((rose red) (lily white) (buttercup yellow)) | |
1277 | @end example | |
1278 | ||
1279 | @noindent | |
1280 | Here we regard @code{red} as the value associated with @code{rose}. One | |
f9f59935 | 1281 | advantage of this kind of alist is that you can store other related |
73804d4b RS |
1282 | information---even a list of other items---in the @sc{cdr} of the |
1283 | @sc{cdr}. One disadvantage is that you cannot use @code{rassq} (see | |
1284 | below) to find the element containing a given value. When neither of | |
1285 | these considerations is important, the choice is a matter of taste, as | |
1286 | long as you are consistent about it for any given alist. | |
1287 | ||
1288 | Note that the same alist shown above could be regarded as having the | |
1289 | associated value in the @sc{cdr} of the element; the value associated | |
1290 | with @code{rose} would be the list @code{(red)}. | |
1291 | ||
1292 | Association lists are often used to record information that you might | |
1293 | otherwise keep on a stack, since new associations may be added easily to | |
1294 | the front of the list. When searching an association list for an | |
1295 | association with a given key, the first one found is returned, if there | |
1296 | is more than one. | |
1297 | ||
1298 | In Emacs Lisp, it is @emph{not} an error if an element of an | |
1299 | association list is not a cons cell. The alist search functions simply | |
1300 | ignore such elements. Many other versions of Lisp signal errors in such | |
1301 | cases. | |
1302 | ||
1303 | Note that property lists are similar to association lists in several | |
1304 | respects. A property list behaves like an association list in which | |
1305 | each key can occur only once. @xref{Property Lists}, for a comparison | |
1306 | of property lists and association lists. | |
1307 | ||
1308 | @defun assoc key alist | |
1309 | This function returns the first association for @var{key} in | |
1310 | @var{alist}. It compares @var{key} against the alist elements using | |
1311 | @code{equal} (@pxref{Equality Predicates}). It returns @code{nil} if no | |
1312 | association in @var{alist} has a @sc{car} @code{equal} to @var{key}. | |
1313 | For example: | |
1314 | ||
1315 | @smallexample | |
1316 | (setq trees '((pine . cones) (oak . acorns) (maple . seeds))) | |
1317 | @result{} ((pine . cones) (oak . acorns) (maple . seeds)) | |
1318 | (assoc 'oak trees) | |
1319 | @result{} (oak . acorns) | |
1320 | (cdr (assoc 'oak trees)) | |
1321 | @result{} acorns | |
1322 | (assoc 'birch trees) | |
1323 | @result{} nil | |
1324 | @end smallexample | |
1325 | ||
2b3fc6c3 | 1326 | Here is another example, in which the keys and values are not symbols: |
73804d4b RS |
1327 | |
1328 | @smallexample | |
1329 | (setq needles-per-cluster | |
1330 | '((2 "Austrian Pine" "Red Pine") | |
1331 | (3 "Pitch Pine") | |
1332 | (5 "White Pine"))) | |
1333 | ||
1334 | (cdr (assoc 3 needles-per-cluster)) | |
1335 | @result{} ("Pitch Pine") | |
1336 | (cdr (assoc 2 needles-per-cluster)) | |
1337 | @result{} ("Austrian Pine" "Red Pine") | |
1338 | @end smallexample | |
1339 | @end defun | |
1340 | ||
22697dac KH |
1341 | @defun rassoc value alist |
1342 | This function returns the first association with value @var{value} in | |
1343 | @var{alist}. It returns @code{nil} if no association in @var{alist} has | |
1344 | a @sc{cdr} @code{equal} to @var{value}. | |
1345 | ||
1346 | @code{rassoc} is like @code{assoc} except that it compares the @sc{cdr} of | |
1347 | each @var{alist} association instead of the @sc{car}. You can think of | |
1348 | this as ``reverse @code{assoc}'', finding the key for a given value. | |
1349 | @end defun | |
1350 | ||
73804d4b RS |
1351 | @defun assq key alist |
1352 | This function is like @code{assoc} in that it returns the first | |
1353 | association for @var{key} in @var{alist}, but it makes the comparison | |
1354 | using @code{eq} instead of @code{equal}. @code{assq} returns @code{nil} | |
1355 | if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}. | |
1356 | This function is used more often than @code{assoc}, since @code{eq} is | |
1357 | faster than @code{equal} and most alists use symbols as keys. | |
1358 | @xref{Equality Predicates}. | |
1359 | ||
1360 | @smallexample | |
1361 | (setq trees '((pine . cones) (oak . acorns) (maple . seeds))) | |
1362 | @result{} ((pine . cones) (oak . acorns) (maple . seeds)) | |
1363 | (assq 'pine trees) | |
1364 | @result{} (pine . cones) | |
1365 | @end smallexample | |
1366 | ||
1367 | On the other hand, @code{assq} is not usually useful in alists where the | |
1368 | keys may not be symbols: | |
1369 | ||
1370 | @smallexample | |
1371 | (setq leaves | |
1372 | '(("simple leaves" . oak) | |
1373 | ("compound leaves" . horsechestnut))) | |
1374 | ||
1375 | (assq "simple leaves" leaves) | |
1376 | @result{} nil | |
1377 | (assoc "simple leaves" leaves) | |
1378 | @result{} ("simple leaves" . oak) | |
1379 | @end smallexample | |
1380 | @end defun | |
1381 | ||
1382 | @defun rassq value alist | |
1383 | This function returns the first association with value @var{value} in | |
1384 | @var{alist}. It returns @code{nil} if no association in @var{alist} has | |
1385 | a @sc{cdr} @code{eq} to @var{value}. | |
1386 | ||
1387 | @code{rassq} is like @code{assq} except that it compares the @sc{cdr} of | |
1388 | each @var{alist} association instead of the @sc{car}. You can think of | |
1389 | this as ``reverse @code{assq}'', finding the key for a given value. | |
1390 | ||
1391 | For example: | |
1392 | ||
1393 | @smallexample | |
1394 | (setq trees '((pine . cones) (oak . acorns) (maple . seeds))) | |
1395 | ||
1396 | (rassq 'acorns trees) | |
1397 | @result{} (oak . acorns) | |
1398 | (rassq 'spores trees) | |
1399 | @result{} nil | |
1400 | @end smallexample | |
1401 | ||
1402 | Note that @code{rassq} cannot search for a value stored in the @sc{car} | |
1403 | of the @sc{cdr} of an element: | |
1404 | ||
1405 | @smallexample | |
1406 | (setq colors '((rose red) (lily white) (buttercup yellow))) | |
1407 | ||
1408 | (rassq 'white colors) | |
1409 | @result{} nil | |
1410 | @end smallexample | |
1411 | ||
1412 | In this case, the @sc{cdr} of the association @code{(lily white)} is not | |
1413 | the symbol @code{white}, but rather the list @code{(white)}. This | |
1414 | becomes clearer if the association is written in dotted pair notation: | |
1415 | ||
1416 | @smallexample | |
1417 | (lily white) @equiv{} (lily . (white)) | |
1418 | @end smallexample | |
1419 | @end defun | |
1420 | ||
1421 | @defun copy-alist alist | |
1422 | @cindex copying alists | |
1423 | This function returns a two-level deep copy of @var{alist}: it creates a | |
1424 | new copy of each association, so that you can alter the associations of | |
1425 | the new alist without changing the old one. | |
1426 | ||
1427 | @smallexample | |
1428 | @group | |
1429 | (setq needles-per-cluster | |
1430 | '((2 . ("Austrian Pine" "Red Pine")) | |
2b3fc6c3 | 1431 | (3 . ("Pitch Pine")) |
ec221d13 | 1432 | @end group |
2b3fc6c3 | 1433 | (5 . ("White Pine")))) |
73804d4b RS |
1434 | @result{} |
1435 | ((2 "Austrian Pine" "Red Pine") | |
2b3fc6c3 RS |
1436 | (3 "Pitch Pine") |
1437 | (5 "White Pine")) | |
73804d4b RS |
1438 | |
1439 | (setq copy (copy-alist needles-per-cluster)) | |
1440 | @result{} | |
1441 | ((2 "Austrian Pine" "Red Pine") | |
2b3fc6c3 RS |
1442 | (3 "Pitch Pine") |
1443 | (5 "White Pine")) | |
73804d4b RS |
1444 | |
1445 | (eq needles-per-cluster copy) | |
1446 | @result{} nil | |
1447 | (equal needles-per-cluster copy) | |
1448 | @result{} t | |
1449 | (eq (car needles-per-cluster) (car copy)) | |
1450 | @result{} nil | |
1451 | (cdr (car (cdr needles-per-cluster))) | |
2b3fc6c3 | 1452 | @result{} ("Pitch Pine") |
ec221d13 | 1453 | @group |
73804d4b RS |
1454 | (eq (cdr (car (cdr needles-per-cluster))) |
1455 | (cdr (car (cdr copy)))) | |
1456 | @result{} t | |
1457 | @end group | |
3e099569 | 1458 | @end smallexample |
2b3fc6c3 RS |
1459 | |
1460 | This example shows how @code{copy-alist} makes it possible to change | |
1461 | the associations of one copy without affecting the other: | |
1462 | ||
3e099569 | 1463 | @smallexample |
2b3fc6c3 | 1464 | @group |
c74c521d | 1465 | (setcdr (assq 3 copy) '("Martian Vacuum Pine")) |
2b3fc6c3 RS |
1466 | (cdr (assq 3 needles-per-cluster)) |
1467 | @result{} ("Pitch Pine") | |
1468 | @end group | |
73804d4b RS |
1469 | @end smallexample |
1470 | @end defun | |
1471 | ||
1472 |