Add Commentary section, minor cleanup of file header.
[emacs.git] / lispref / lists.texi
blobb437916694f68717a7ff68028a1d94d8645d8f0d
1 @c -*-texinfo-*-
2 @c This is part of the GNU Emacs Lisp Reference Manual.
3 @c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998, 1999
4 @c   Free Software Foundation, Inc.
5 @c See the file elisp.texi for copying conditions.
6 @setfilename ../info/lists
7 @node Lists, Sequences Arrays Vectors, Strings and Characters, Top
8 @chapter Lists
9 @cindex list
10 @cindex element (of list)
12   A @dfn{list} represents a sequence of zero or more elements (which may
13 be any Lisp objects).  The important difference between lists and
14 vectors is that two or more lists can share part of their structure; in
15 addition, you can insert or delete elements in a list without copying
16 the whole list.
18 @menu
19 * Cons Cells::          How lists are made out of cons cells.
20 * Lists as Boxes::                 Graphical notation to explain lists.
21 * List-related Predicates::        Is this object a list?  Comparing two lists.
22 * List Elements::       Extracting the pieces of a list.
23 * Building Lists::      Creating list structure.
24 * Modifying Lists::     Storing new pieces into an existing list.
25 * Sets And Lists::      A list can represent a finite mathematical set.
26 * Association Lists::   A list can represent a finite relation or mapping.
27 @end menu
29 @node Cons Cells
30 @section Lists and Cons Cells
31 @cindex lists and cons cells
32 @cindex @code{nil} and lists
34   Lists in Lisp are not a primitive data type; they are built up from
35 @dfn{cons cells}.  A cons cell is a data object that represents an
36 ordered pair.  That is, it has two slots, and each slot @dfn{holds}, or
37 @dfn{refers to}, some Lisp object.  One slot is known as the @sc{car},
38 and the other is known as the @sc{cdr}.  (These names are traditional;
39 see @ref{Cons Cell Type}.)  @sc{cdr} is pronounced ``could-er.''
41   We say that ``the @sc{car} of this cons cell is'' whatever object
42 its @sc{car} slot currently holds, and likewise for the @sc{cdr}.
44   A list is a series of cons cells ``chained together,'' so that each
45 cell refers to the next one.  There is one cons cell for each element of
46 the list.  By convention, the @sc{car}s of the cons cells hold the
47 elements of the list, and the @sc{cdr}s are used to chain the list: the
48 @sc{cdr} slot of each cons cell refers to the following cons cell.  The
49 @sc{cdr} of the last cons cell is @code{nil}.  This asymmetry between
50 the @sc{car} and the @sc{cdr} is entirely a matter of convention; at the
51 level of cons cells, the @sc{car} and @sc{cdr} slots have the same
52 characteristics.
54 @cindex list structure
55   Because most cons cells are used as part of lists, the phrase
56 @dfn{list structure} has come to mean any structure made out of cons
57 cells.
59   The symbol @code{nil} is considered a list as well as a symbol; it is
60 the list with no elements.  For convenience, the symbol @code{nil} is
61 considered to have @code{nil} as its @sc{cdr} (and also as its
62 @sc{car}).
64   The @sc{cdr} of any nonempty list @var{l} is a list containing all the
65 elements of @var{l} except the first.
67 @node Lists as Boxes
68 @comment  node-name,  next,  previous,  up
69 @section Lists as Linked Pairs of Boxes
70 @cindex box representation for lists
71 @cindex lists represented as boxes
72 @cindex cons cell as box
74   A cons cell can be illustrated as a pair of boxes.  The first box
75 represents the @sc{car} and the second box represents the @sc{cdr}.
76 Here is an illustration of the two-element list, @code{(tulip lily)},
77 made from two cons cells:
79 @example
80 @group
81  ---------------         ---------------
82 | car   | cdr   |       | car   | cdr   |
83 | tulip |   o---------->| lily  |  nil  |
84 |       |       |       |       |       |
85  ---------------         ---------------
86 @end group
87 @end example
89   Each pair of boxes represents a cons cell.  Each box ``refers to'',
90 ``points to'' or ``holds'' a Lisp object.  (These terms are
91 synonymous.)  The first box, which describes the @sc{car} of the first
92 cons cell, contains the symbol @code{tulip}.  The arrow from the
93 @sc{cdr} box of the first cons cell to the second cons cell indicates
94 that the @sc{cdr} of the first cons cell is the second cons cell.
96   The same list can be illustrated in a different sort of box notation
97 like this:
99 @example
100 @group
101     --- ---      --- ---
102    |   |   |--> |   |   |--> nil
103     --- ---      --- ---
104      |            |
105      |            |
106       --> tulip    --> lily
107 @end group
108 @end example
110   Here is a more complex illustration, showing the three-element list,
111 @code{((pine needles) oak maple)}, the first element of which is a
112 two-element list:
114 @example
115 @group
116     --- ---      --- ---      --- ---
117    |   |   |--> |   |   |--> |   |   |--> nil
118     --- ---      --- ---      --- ---
119      |            |            |
120      |            |            |
121      |             --> oak      --> maple
122      |
123      |     --- ---      --- ---
124       --> |   |   |--> |   |   |--> nil
125            --- ---      --- ---
126             |            |
127             |            |
128              --> pine     --> needles
129 @end group
130 @end example
132   The same list represented in the first box notation looks like this:
134 @example
135 @group
136  --------------       --------------       --------------
137 | car   | cdr  |     | car   | cdr  |     | car   | cdr  |
138 |   o   |   o------->| oak   |   o------->| maple |  nil |
139 |   |   |      |     |       |      |     |       |      |
140  -- | ---------       --------------       --------------
141     |
142     |
143     |        --------------       ----------------
144     |       | car   | cdr  |     | car     | cdr  |
145      ------>| pine  |   o------->| needles |  nil |
146             |       |      |     |         |      |
147              --------------       ----------------
148 @end group
149 @end example
151   @xref{Cons Cell Type}, for the read and print syntax of cons cells and
152 lists, and for more ``box and arrow'' illustrations of lists.
154 @node List-related Predicates
155 @section Predicates on Lists
157   The following predicates test whether a Lisp object is an atom, is a
158 cons cell or is a list, or whether it is the distinguished object
159 @code{nil}.  (Many of these predicates can be defined in terms of the
160 others, but they are used so often that it is worth having all of them.)
162 @defun consp object
163 This function returns @code{t} if @var{object} is a cons cell, @code{nil}
164 otherwise.  @code{nil} is not a cons cell, although it @emph{is} a list.
165 @end defun
167 @defun atom object
168 @cindex atoms
169 This function returns @code{t} if @var{object} is an atom, @code{nil}
170 otherwise.  All objects except cons cells are atoms.  The symbol
171 @code{nil} is an atom and is also a list; it is the only Lisp object
172 that is both.
174 @example
175 (atom @var{object}) @equiv{} (not (consp @var{object}))
176 @end example
177 @end defun
179 @defun listp object
180 This function returns @code{t} if @var{object} is a cons cell or
181 @code{nil}.  Otherwise, it returns @code{nil}.
183 @example
184 @group
185 (listp '(1))
186      @result{} t
187 @end group
188 @group
189 (listp '())
190      @result{} t
191 @end group
192 @end example
193 @end defun
195 @defun nlistp object
196 This function is the opposite of @code{listp}: it returns @code{t} if
197 @var{object} is not a list.  Otherwise, it returns @code{nil}.
199 @example
200 (listp @var{object}) @equiv{} (not (nlistp @var{object}))
201 @end example
202 @end defun
204 @defun null object
205 This function returns @code{t} if @var{object} is @code{nil}, and
206 returns @code{nil} otherwise.  This function is identical to @code{not},
207 but as a matter of clarity we use @code{null} when @var{object} is
208 considered a list and @code{not} when it is considered a truth value
209 (see @code{not} in @ref{Combining Conditions}).
211 @example
212 @group
213 (null '(1))
214      @result{} nil
215 @end group
216 @group
217 (null '())
218      @result{} t
219 @end group
220 @end example
221 @end defun
223 @need 2000
225 @node List Elements
226 @section Accessing Elements of Lists
227 @cindex list elements
229 @defun car cons-cell
230 This function returns the value referred to by the first slot of the
231 cons cell @var{cons-cell}.  Expressed another way, this function
232 returns the @sc{car} of @var{cons-cell}.
234 As a special case, if @var{cons-cell} is @code{nil}, then @code{car}
235 is defined to return @code{nil}; therefore, any list is a valid argument
236 for @code{car}.  An error is signaled if the argument is not a cons cell
237 or @code{nil}.
239 @example
240 @group
241 (car '(a b c))
242      @result{} a
243 @end group
244 @group
245 (car '())
246      @result{} nil
247 @end group
248 @end example
249 @end defun
251 @defun cdr cons-cell
252 This function returns the value referred to by the second slot of
253 the cons cell @var{cons-cell}.  Expressed another way, this function
254 returns the @sc{cdr} of @var{cons-cell}.
256 As a special case, if @var{cons-cell} is @code{nil}, then @code{cdr}
257 is defined to return @code{nil}; therefore, any list is a valid argument
258 for @code{cdr}.  An error is signaled if the argument is not a cons cell
259 or @code{nil}.
261 @example
262 @group
263 (cdr '(a b c))
264      @result{} (b c)
265 @end group
266 @group
267 (cdr '())
268      @result{} nil
269 @end group
270 @end example
271 @end defun
273 @defun car-safe object
274 This function lets you take the @sc{car} of a cons cell while avoiding
275 errors for other data types.  It returns the @sc{car} of @var{object} if
276 @var{object} is a cons cell, @code{nil} otherwise.  This is in contrast
277 to @code{car}, which signals an error if @var{object} is not a list.
279 @example
280 @group
281 (car-safe @var{object})
282 @equiv{}
283 (let ((x @var{object}))
284   (if (consp x)
285       (car x)
286     nil))
287 @end group
288 @end example
289 @end defun
291 @defun cdr-safe object
292 This function lets you take the @sc{cdr} of a cons cell while
293 avoiding errors for other data types.  It returns the @sc{cdr} of
294 @var{object} if @var{object} is a cons cell, @code{nil} otherwise.
295 This is in contrast to @code{cdr}, which signals an error if
296 @var{object} is not a list.
298 @example
299 @group
300 (cdr-safe @var{object})
301 @equiv{}
302 (let ((x @var{object}))
303   (if (consp x)
304       (cdr x)
305     nil))
306 @end group
307 @end example
308 @end defun
310 @tindex pop
311 @defmac pop listname
312 This macro is a way of examining the @sc{car} of a list,
313 and taking it off the list, all at once.  It is new in Emacs 21.
315 It operates on the list which is stored in the symbol @var{listname}.
316 It removes this element from the list by setting @var{listname}
317 to the @sc{cdr} of its old value---but it also returns the @sc{car}
318 of that list, which is the element being removed.
320 @example
322      @result{} (a b c)
323 (pop x)
324      @result{} a
326      @result{} (b c)
327 @end example
328 @end defmac
330 @defun nth n list
331 This function returns the @var{n}th element of @var{list}.  Elements
332 are numbered starting with zero, so the @sc{car} of @var{list} is
333 element number zero.  If the length of @var{list} is @var{n} or less,
334 the value is @code{nil}.
336 If @var{n} is negative, @code{nth} returns the first element of
337 @var{list}.
339 @example
340 @group
341 (nth 2 '(1 2 3 4))
342      @result{} 3
343 @end group
344 @group
345 (nth 10 '(1 2 3 4))
346      @result{} nil
347 @end group
348 @group
349 (nth -3 '(1 2 3 4))
350      @result{} 1
352 (nth n x) @equiv{} (car (nthcdr n x))
353 @end group
354 @end example
356 The function @code{elt} is similar, but applies to any kind of sequence.
357 For historical reasons, it takes its arguments in the opposite order.
358 @xref{Sequence Functions}.
359 @end defun
361 @defun nthcdr n list
362 This function returns the @var{n}th @sc{cdr} of @var{list}.  In other
363 words, it skips past the first @var{n} links of @var{list} and returns
364 what follows.
366 If @var{n} is zero or negative, @code{nthcdr} returns all of
367 @var{list}.  If the length of @var{list} is @var{n} or less,
368 @code{nthcdr} returns @code{nil}.
370 @example
371 @group
372 (nthcdr 1 '(1 2 3 4))
373      @result{} (2 3 4)
374 @end group
375 @group
376 (nthcdr 10 '(1 2 3 4))
377      @result{} nil
378 @end group
379 @group
380 (nthcdr -3 '(1 2 3 4))
381      @result{} (1 2 3 4)
382 @end group
383 @end example
384 @end defun
386 @defun last list &optional n
387 This function returns the last link of @var{list}.  The @code{car} of
388 this link is the list's last element.  If @var{list} is null,
389 @code{nil} is returned.  If @var{n} is non-@code{nil}, the
390 @var{n}th-to-last link is returned instead, or the whole of @var{list}
391 if @var{n} is bigger than @var{list}'s length.
392 @end defun
394 @defun safe-length list
395 This function returns the length of @var{list}, with no risk
396 of either an error or an infinite loop.
398 If @var{list} is not really a list, @code{safe-length} returns 0.  If
399 @var{list} is circular, it returns a finite value which is at least the
400 number of distinct elements.
401 @end defun
403   The most common way to compute the length of a list, when you are not
404 worried that it may be circular, is with @code{length}.  @xref{Sequence
405 Functions}.
407 @defun caar cons-cell
408 This is the same as @code{(car (car @var{cons-cell}))}.
409 @end defun
411 @defun cadr cons-cell
412 This is the same as @code{(car (cdr @var{cons-cell}))}
413 or @code{(nth 1 @var{cons-cell})}.
414 @end defun
416 @defun cdar cons-cell
417 This is the same as @code{(cdr (car @var{cons-cell}))}.
418 @end defun
420 @defun cddr cons-cell
421 This is the same as @code{(cdr (cdr @var{cons-cell}))}
422 or @code{(nthcdr 2 @var{cons-cell})}.
423 @end defun
425 @defun butlast x &optional n
426 This function returns the list @var{x} with the last element,
427 or the last @var{n} elements, removed.  If @var{n} is greater
428 than zero it makes a copy of the list so as not to damage the
429 original list.  In general, @code{(append (butlast @var{x} @var{n})
430 (last @var{x} @var{n}))} will return a list equal to @var{x}.
431 @end defun
433 @defun nbutlast x &optional n
434 This is a version of @code{butlast} that works by destructively
435 modifying the @code{cdr} of the appropriate element, rather than
436 making a copy of the list.
437 @end defun
439 @node Building Lists
440 @comment  node-name,  next,  previous,  up
441 @section Building Cons Cells and Lists
442 @cindex cons cells
443 @cindex building lists
445   Many functions build lists, as lists reside at the very heart of Lisp.
446 @code{cons} is the fundamental list-building function; however, it is
447 interesting to note that @code{list} is used more times in the source
448 code for Emacs than @code{cons}.
450 @defun cons object1 object2
451 This function is the fundamental function used to build new list
452 structure.  It creates a new cons cell, making @var{object1} the
453 @sc{car}, and @var{object2} the @sc{cdr}.  It then returns the new cons
454 cell.  The arguments @var{object1} and @var{object2} may be any Lisp
455 objects, but most often @var{object2} is a list.
457 @example
458 @group
459 (cons 1 '(2))
460      @result{} (1 2)
461 @end group
462 @group
463 (cons 1 '())
464      @result{} (1)
465 @end group
466 @group
467 (cons 1 2)
468      @result{} (1 . 2)
469 @end group
470 @end example
472 @cindex consing
473 @code{cons} is often used to add a single element to the front of a
474 list.  This is called @dfn{consing the element onto the list}.
475 @footnote{There is no strictly equivalent way to add an element to
476 the end of a list.  You can use @code{(append @var{listname} (list
477 @var{newelt}))}, which creates a whole new list by copying @var{listname}
478 and adding @var{newelt} to its end.  Or you can use @code{(nconc
479 @var{listname} (list @var{newelt}))}, which modifies @var{listname}
480 by following all the @sc{cdr}s and then replacing the terminating
481 @code{nil}.  Compare this to adding an element to the beginning of a
482 list with @code{cons}, which neither copies nor modifies the list.}
483 For example:
485 @example
486 (setq list (cons newelt list))
487 @end example
489 Note that there is no conflict between the variable named @code{list}
490 used in this example and the function named @code{list} described below;
491 any symbol can serve both purposes.
492 @end defun
494 @tindex push
495 @defmac push newelt listname
496 This macro provides an alternative way to write
497 @code{(setq @var{listname} (cons @var{newelt} @var{listname}))}.
498 It is new in Emacs 21.
500 @example
501 (setq l '(a b))
502      @result{} (a b)
503 (push 'c l)
504      @result{} (c a b)
506      @result{} (c a b)
507 @end example
508 @end defmac
510 @defun list &rest objects
511 This function creates a list with @var{objects} as its elements.  The
512 resulting list is always @code{nil}-terminated.  If no @var{objects}
513 are given, the empty list is returned.
515 @example
516 @group
517 (list 1 2 3 4 5)
518      @result{} (1 2 3 4 5)
519 @end group
520 @group
521 (list 1 2 '(3 4 5) 'foo)
522      @result{} (1 2 (3 4 5) foo)
523 @end group
524 @group
525 (list)
526      @result{} nil
527 @end group
528 @end example
529 @end defun
531 @defun make-list length object
532 This function creates a list of @var{length} elements, in which each
533 element is @var{object}.  Compare @code{make-list} with
534 @code{make-string} (@pxref{Creating Strings}).
536 @example
537 @group
538 (make-list 3 'pigs)
539      @result{} (pigs pigs pigs)
540 @end group
541 @group
542 (make-list 0 'pigs)
543      @result{} nil
544 @end group
545 @group
546 (setq l (make-list 3 '(a b))
547      @result{} ((a b) (a b) (a b))
548 (eq (car l) (cadr l))
549      @result{} t
550 @end group
551 @end example
552 @end defun
554 @defun append &rest sequences
555 @cindex copying lists
556 This function returns a list containing all the elements of
557 @var{sequences}.  The @var{sequences} may be lists, vectors,
558 bool-vectors, or strings, but the last one should usually be a list.
559 All arguments except the last one are copied, so none of the arguments
560 is altered.  (See @code{nconc} in @ref{Rearrangement}, for a way to join
561 lists with no copying.)
563 More generally, the final argument to @code{append} may be any Lisp
564 object.  The final argument is not copied or converted; it becomes the
565 @sc{cdr} of the last cons cell in the new list.  If the final argument
566 is itself a list, then its elements become in effect elements of the
567 result list.  If the final element is not a list, the result is a
568 ``dotted list'' since its final @sc{cdr} is not @code{nil} as required
569 in a true list.
571 The @code{append} function also allows integers as arguments.  It
572 converts them to strings of digits, making up the decimal print
573 representation of the integer, and then uses the strings instead of the
574 original integers.  @strong{Don't use this feature; we plan to eliminate
575 it.  If you already use this feature, change your programs now!}  The
576 proper way to convert an integer to a decimal number in this way is with
577 @code{format} (@pxref{Formatting Strings}) or @code{number-to-string}
578 (@pxref{String Conversion}).
579 @end defun
581   Here is an example of using @code{append}:
583 @example
584 @group
585 (setq trees '(pine oak))
586      @result{} (pine oak)
587 (setq more-trees (append '(maple birch) trees))
588      @result{} (maple birch pine oak)
589 @end group
591 @group
592 trees
593      @result{} (pine oak)
594 more-trees
595      @result{} (maple birch pine oak)
596 @end group
597 @group
598 (eq trees (cdr (cdr more-trees)))
599      @result{} t
600 @end group
601 @end example
603   You can see how @code{append} works by looking at a box diagram.  The
604 variable @code{trees} is set to the list @code{(pine oak)} and then the
605 variable @code{more-trees} is set to the list @code{(maple birch pine
606 oak)}.  However, the variable @code{trees} continues to refer to the
607 original list:
609 @smallexample
610 @group
611 more-trees                trees
612 |                           |
613 |     --- ---      --- ---   -> --- ---      --- ---
614  --> |   |   |--> |   |   |--> |   |   |--> |   |   |--> nil
615       --- ---      --- ---      --- ---      --- ---
616        |            |            |            |
617        |            |            |            |
618         --> maple    -->birch     --> pine     --> oak
619 @end group
620 @end smallexample
622   An empty sequence contributes nothing to the value returned by
623 @code{append}.  As a consequence of this, a final @code{nil} argument
624 forces a copy of the previous argument:
626 @example
627 @group
628 trees
629      @result{} (pine oak)
630 @end group
631 @group
632 (setq wood (append trees nil))
633      @result{} (pine oak)
634 @end group
635 @group
636 wood
637      @result{} (pine oak)
638 @end group
639 @group
640 (eq wood trees)
641      @result{} nil
642 @end group
643 @end example
645 @noindent
646 This once was the usual way to copy a list, before the function
647 @code{copy-sequence} was invented.  @xref{Sequences Arrays Vectors}.
649   Here we show the use of vectors and strings as arguments to @code{append}:
651 @example
652 @group
653 (append [a b] "cd" nil)
654      @result{} (a b 99 100)
655 @end group
656 @end example
658   With the help of @code{apply} (@pxref{Calling Functions}), we can append
659 all the lists in a list of lists:
661 @example
662 @group
663 (apply 'append '((a b c) nil (x y z) nil))
664      @result{} (a b c x y z)
665 @end group
666 @end example
668   If no @var{sequences} are given, @code{nil} is returned:
670 @example
671 @group
672 (append)
673      @result{} nil
674 @end group
675 @end example
677   Here are some examples where the final argument is not a list:
679 @example
680 (append '(x y) 'z)
681      @result{} (x y . z)
682 (append '(x y) [z])
683      @result{} (x y . [z])
684 @end example
686 @noindent
687 The second example shows that when the final argument is a sequence but
688 not a list, the sequence's elements do not become elements of the
689 resulting list.  Instead, the sequence becomes the final @sc{cdr}, like
690 any other non-list final argument.
692 @defun reverse list
693 This function creates a new list whose elements are the elements of
694 @var{list}, but in reverse order.  The original argument @var{list} is
695 @emph{not} altered.
697 @example
698 @group
699 (setq x '(1 2 3 4))
700      @result{} (1 2 3 4)
701 @end group
702 @group
703 (reverse x)
704      @result{} (4 3 2 1)
706      @result{} (1 2 3 4)
707 @end group
708 @end example
709 @end defun
711 @defun remq object list
712 This function returns a copy of @var{list}, with all elements removed
713 which are @code{eq} to @var{object}.  The letter @samp{q} in @code{remq}
714 says that it uses @code{eq} to compare @var{object} against the elements
715 of @code{list}.
717 @example
718 @group
719 (setq sample-list '(a b c a b c))
720      @result{} (a b c a b c)
721 @end group
722 @group
723 (remq 'a sample-list)
724      @result{} (b c b c)
725 @end group
726 @group
727 sample-list
728      @result{} (a b c a b c)
729 @end group
730 @end example
731 @noindent
732 The function @code{delq} offers a way to perform this operation
733 destructively.  See @ref{Sets And Lists}.
734 @end defun
736 @defun copy-tree tree &optional vecp
737 This function returns a copy the tree @code{tree}.  If @var{tree} is a
738 cons cell, this makes a new cons cell with the same @sc{car} and
739 @sc{cdr}, then recursively copies the @sc{car} and @sc{cdr} in the
740 same way.
742 Normally, when @var{tree} is anything other than a cons cell,
743 @code{copy-tree} simply returns @var{tree}.  However, if @var{vecp} is
744 non-@code{nil}, it copies vectors too (and operates recursively on
745 their elements).
746 @end defun
748 @defun number-sequence from to &optional separation
749 This returns a list of numbers starting with @var{from}
750 and incrementing by @var{separation} (or by 1 if @var{separation}
751 is @code{nil} or omitted), and ending at or just before @var{to}.
752 For example,
754 @example
755 (number-sequence 4 9)
756      @result{} (4 5 6 7 8 9)
757 (number-sequence 1.5 6 2)
758      @result{} (1.5 3.5 5.5)
759 @end example
760 @end defun
762 @node Modifying Lists
763 @section Modifying Existing List Structure
764 @cindex destructive list operations
766   You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the
767 primitives @code{setcar} and @code{setcdr}.  We call these ``destructive''
768 operations because they change existing list structure.
770 @cindex CL note---@code{rplaca} vrs @code{setcar}
771 @quotation
772 @findex rplaca
773 @findex rplacd
774 @b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and
775 @code{rplacd} to alter list structure; they change structure the same
776 way as @code{setcar} and @code{setcdr}, but the Common Lisp functions
777 return the cons cell while @code{setcar} and @code{setcdr} return the
778 new @sc{car} or @sc{cdr}.
779 @end quotation
781 @menu
782 * Setcar::          Replacing an element in a list.
783 * Setcdr::          Replacing part of the list backbone.
784                       This can be used to remove or add elements.
785 * Rearrangement::   Reordering the elements in a list; combining lists.
786 @end menu
788 @node Setcar
789 @subsection Altering List Elements with @code{setcar}
791   Changing the @sc{car} of a cons cell is done with @code{setcar}.  When
792 used on a list, @code{setcar} replaces one element of a list with a
793 different element.
795 @defun setcar cons object
796 This function stores @var{object} as the new @sc{car} of @var{cons},
797 replacing its previous @sc{car}.  In other words, it changes the
798 @sc{car} slot of @var{cons} to refer to @var{object}.  It returns the
799 value @var{object}.  For example:
801 @example
802 @group
803 (setq x '(1 2))
804      @result{} (1 2)
805 @end group
806 @group
807 (setcar x 4)
808      @result{} 4
809 @end group
810 @group
812      @result{} (4 2)
813 @end group
814 @end example
815 @end defun
817   When a cons cell is part of the shared structure of several lists,
818 storing a new @sc{car} into the cons changes one element of each of
819 these lists.  Here is an example:
821 @example
822 @group
823 ;; @r{Create two lists that are partly shared.}
824 (setq x1 '(a b c))
825      @result{} (a b c)
826 (setq x2 (cons 'z (cdr x1)))
827      @result{} (z b c)
828 @end group
830 @group
831 ;; @r{Replace the @sc{car} of a shared link.}
832 (setcar (cdr x1) 'foo)
833      @result{} foo
834 x1                           ; @r{Both lists are changed.}
835      @result{} (a foo c)
837      @result{} (z foo c)
838 @end group
840 @group
841 ;; @r{Replace the @sc{car} of a link that is not shared.}
842 (setcar x1 'baz)
843      @result{} baz
844 x1                           ; @r{Only one list is changed.}
845      @result{} (baz foo c)
847      @result{} (z foo c)
848 @end group
849 @end example
851   Here is a graphical depiction of the shared structure of the two lists
852 in the variables @code{x1} and @code{x2}, showing why replacing @code{b}
853 changes them both:
855 @example
856 @group
857         --- ---        --- ---      --- ---
858 x1---> |   |   |----> |   |   |--> |   |   |--> nil
859         --- ---        --- ---      --- ---
860          |        -->   |            |
861          |       |      |            |
862           --> a  |       --> b        --> c
863                  |
864        --- ---   |
865 x2--> |   |   |--
866        --- ---
867         |
868         |
869          --> z
870 @end group
871 @end example
873   Here is an alternative form of box diagram, showing the same relationship:
875 @example
876 @group
878  --------------       --------------       --------------
879 | car   | cdr  |     | car   | cdr  |     | car   | cdr  |
880 |   a   |   o------->|   b   |   o------->|   c   |  nil |
881 |       |      |  -->|       |      |     |       |      |
882  --------------  |    --------------       --------------
883                  |
884 x2:              |
885  --------------  |
886 | car   | cdr  | |
887 |   z   |   o----
888 |       |      |
889  --------------
890 @end group
891 @end example
893 @node Setcdr
894 @subsection Altering the CDR of a List
896   The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}:
898 @defun setcdr cons object
899 This function stores @var{object} as the new @sc{cdr} of @var{cons},
900 replacing its previous @sc{cdr}.  In other words, it changes the
901 @sc{cdr} slot of @var{cons} to refer to @var{object}.  It returns the
902 value @var{object}.
903 @end defun
905   Here is an example of replacing the @sc{cdr} of a list with a
906 different list.  All but the first element of the list are removed in
907 favor of a different sequence of elements.  The first element is
908 unchanged, because it resides in the @sc{car} of the list, and is not
909 reached via the @sc{cdr}.
911 @example
912 @group
913 (setq x '(1 2 3))
914      @result{} (1 2 3)
915 @end group
916 @group
917 (setcdr x '(4))
918      @result{} (4)
919 @end group
920 @group
922      @result{} (1 4)
923 @end group
924 @end example
926   You can delete elements from the middle of a list by altering the
927 @sc{cdr}s of the cons cells in the list.  For example, here we delete
928 the second element, @code{b}, from the list @code{(a b c)}, by changing
929 the @sc{cdr} of the first cons cell:
931 @example
932 @group
933 (setq x1 '(a b c))
934      @result{} (a b c)
935 (setcdr x1 (cdr (cdr x1)))
936      @result{} (c)
938      @result{} (a c)
939 @end group
940 @end example
942 @need 4000
943   Here is the result in box notation:
945 @example
946 @group
947                    --------------------
948                   |                    |
949  --------------   |   --------------   |    --------------
950 | car   | cdr  |  |  | car   | cdr  |   -->| car   | cdr  |
951 |   a   |   o-----   |   b   |   o-------->|   c   |  nil |
952 |       |      |     |       |      |      |       |      |
953  --------------       --------------        --------------
954 @end group
955 @end example
957 @noindent
958 The second cons cell, which previously held the element @code{b}, still
959 exists and its @sc{car} is still @code{b}, but it no longer forms part
960 of this list.
962   It is equally easy to insert a new element by changing @sc{cdr}s:
964 @example
965 @group
966 (setq x1 '(a b c))
967      @result{} (a b c)
968 (setcdr x1 (cons 'd (cdr x1)))
969      @result{} (d b c)
971      @result{} (a d b c)
972 @end group
973 @end example
975   Here is this result in box notation:
977 @smallexample
978 @group
979  --------------        -------------       -------------
980 | car  | cdr   |      | car  | cdr  |     | car  | cdr  |
981 |   a  |   o   |   -->|   b  |   o------->|   c  |  nil |
982 |      |   |   |  |   |      |      |     |      |      |
983  --------- | --   |    -------------       -------------
984            |      |
985      -----         --------
986     |                      |
987     |    ---------------   |
988     |   | car   | cdr   |  |
989      -->|   d   |   o------
990         |       |       |
991          ---------------
992 @end group
993 @end smallexample
995 @node Rearrangement
996 @subsection Functions that Rearrange Lists
997 @cindex rearrangement of lists
998 @cindex modification of lists
1000   Here are some functions that rearrange lists ``destructively'' by
1001 modifying the @sc{cdr}s of their component cons cells.  We call these
1002 functions ``destructive'' because they chew up the original lists passed
1003 to them as arguments, relinking their cons cells to form a new list that
1004 is the returned value.
1006 @ifnottex
1007   See @code{delq}, in @ref{Sets And Lists}, for another function
1008 that modifies cons cells.
1009 @end ifnottex
1010 @iftex
1011    The function @code{delq} in the following section is another example
1012 of destructive list manipulation.
1013 @end iftex
1015 @defun nconc &rest lists
1016 @cindex concatenating lists
1017 @cindex joining lists
1018 This function returns a list containing all the elements of @var{lists}.
1019 Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are
1020 @emph{not} copied.  Instead, the last @sc{cdr} of each of the
1021 @var{lists} is changed to refer to the following list.  The last of the
1022 @var{lists} is not altered.  For example:
1024 @example
1025 @group
1026 (setq x '(1 2 3))
1027      @result{} (1 2 3)
1028 @end group
1029 @group
1030 (nconc x '(4 5))
1031      @result{} (1 2 3 4 5)
1032 @end group
1033 @group
1035      @result{} (1 2 3 4 5)
1036 @end group
1037 @end example
1039    Since the last argument of @code{nconc} is not itself modified, it is
1040 reasonable to use a constant list, such as @code{'(4 5)}, as in the
1041 above example.  For the same reason, the last argument need not be a
1042 list:
1044 @example
1045 @group
1046 (setq x '(1 2 3))
1047      @result{} (1 2 3)
1048 @end group
1049 @group
1050 (nconc x 'z)
1051      @result{} (1 2 3 . z)
1052 @end group
1053 @group
1055      @result{} (1 2 3 . z)
1056 @end group
1057 @end example
1059 However, the other arguments (all but the last) must be lists.
1061 A common pitfall is to use a quoted constant list as a non-last
1062 argument to @code{nconc}.  If you do this, your program will change
1063 each time you run it!  Here is what happens:
1065 @smallexample
1066 @group
1067 (defun add-foo (x)            ; @r{We want this function to add}
1068   (nconc '(foo) x))           ;   @r{@code{foo} to the front of its arg.}
1069 @end group
1071 @group
1072 (symbol-function 'add-foo)
1073      @result{} (lambda (x) (nconc (quote (foo)) x))
1074 @end group
1076 @group
1077 (setq xx (add-foo '(1 2)))    ; @r{It seems to work.}
1078      @result{} (foo 1 2)
1079 @end group
1080 @group
1081 (setq xy (add-foo '(3 4)))    ; @r{What happened?}
1082      @result{} (foo 1 2 3 4)
1083 @end group
1084 @group
1085 (eq xx xy)
1086      @result{} t
1087 @end group
1089 @group
1090 (symbol-function 'add-foo)
1091      @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x)))
1092 @end group
1093 @end smallexample
1094 @end defun
1096 @defun nreverse list
1097 @cindex reversing a list
1098   This function reverses the order of the elements of @var{list}.
1099 Unlike @code{reverse}, @code{nreverse} alters its argument by reversing
1100 the @sc{cdr}s in the cons cells forming the list.  The cons cell that
1101 used to be the last one in @var{list} becomes the first cons cell of the
1102 value.
1104   For example:
1106 @example
1107 @group
1108 (setq x '(a b c))
1109      @result{} (a b c)
1110 @end group
1111 @group
1113      @result{} (a b c)
1114 (nreverse x)
1115      @result{} (c b a)
1116 @end group
1117 @group
1118 ;; @r{The cons cell that was first is now last.}
1120      @result{} (a)
1121 @end group
1122 @end example
1124   To avoid confusion, we usually store the result of @code{nreverse}
1125 back in the same variable which held the original list:
1127 @example
1128 (setq x (nreverse x))
1129 @end example
1131   Here is the @code{nreverse} of our favorite example, @code{(a b c)},
1132 presented graphically:
1134 @smallexample
1135 @group
1136 @r{Original list head:}                       @r{Reversed list:}
1137  -------------        -------------        ------------
1138 | car  | cdr  |      | car  | cdr  |      | car | cdr  |
1139 |   a  |  nil |<--   |   b  |   o  |<--   |   c |   o  |
1140 |      |      |   |  |      |   |  |   |  |     |   |  |
1141  -------------    |   --------- | -    |   -------- | -
1142                   |             |      |            |
1143                    -------------        ------------
1144 @end group
1145 @end smallexample
1146 @end defun
1148 @defun sort list predicate
1149 @cindex stable sort
1150 @cindex sorting lists
1151 This function sorts @var{list} stably, though destructively, and
1152 returns the sorted list.  It compares elements using @var{predicate}.  A
1153 stable sort is one in which elements with equal sort keys maintain their
1154 relative order before and after the sort.  Stability is important when
1155 successive sorts are used to order elements according to different
1156 criteria.
1158 The argument @var{predicate} must be a function that accepts two
1159 arguments.  It is called with two elements of @var{list}.  To get an
1160 increasing order sort, the @var{predicate} should return @code{t} if the
1161 first element is ``less than'' the second, or @code{nil} if not.
1163 The comparison function @var{predicate} must give reliable results for
1164 any given pair of arguments, at least within a single call to
1165 @code{sort}.  It must be @dfn{antisymmetric}; that is, if @var{a} is
1166 less than @var{b}, @var{b} must not be less than @var{a}.  It must be
1167 @dfn{transitive}---that is, if @var{a} is less than @var{b}, and @var{b}
1168 is less than @var{c}, then @var{a} must be less than @var{c}.  If you
1169 use a comparison function which does not meet these requirements, the
1170 result of @code{sort} is unpredictable.
1172 The destructive aspect of @code{sort} is that it rearranges the cons
1173 cells forming @var{list} by changing @sc{cdr}s.  A nondestructive sort
1174 function would create new cons cells to store the elements in their
1175 sorted order.  If you wish to make a sorted copy without destroying the
1176 original, copy it first with @code{copy-sequence} and then sort.
1178 Sorting does not change the @sc{car}s of the cons cells in @var{list};
1179 the cons cell that originally contained the element @code{a} in
1180 @var{list} still has @code{a} in its @sc{car} after sorting, but it now
1181 appears in a different position in the list due to the change of
1182 @sc{cdr}s.  For example:
1184 @example
1185 @group
1186 (setq nums '(1 3 2 6 5 4 0))
1187      @result{} (1 3 2 6 5 4 0)
1188 @end group
1189 @group
1190 (sort nums '<)
1191      @result{} (0 1 2 3 4 5 6)
1192 @end group
1193 @group
1194 nums
1195      @result{} (1 2 3 4 5 6)
1196 @end group
1197 @end example
1199 @noindent
1200 @strong{Warning}: Note that the list in @code{nums} no longer contains
1201 0; this is the same cons cell that it was before, but it is no longer
1202 the first one in the list.  Don't assume a variable that formerly held
1203 the argument now holds the entire sorted list!  Instead, save the result
1204 of @code{sort} and use that.  Most often we store the result back into
1205 the variable that held the original list:
1207 @example
1208 (setq nums (sort nums '<))
1209 @end example
1211 @xref{Sorting}, for more functions that perform sorting.
1212 See @code{documentation} in @ref{Accessing Documentation}, for a
1213 useful example of @code{sort}.
1214 @end defun
1216 @node Sets And Lists
1217 @section Using Lists as Sets
1218 @cindex lists as sets
1219 @cindex sets
1221   A list can represent an unordered mathematical set---simply consider a
1222 value an element of a set if it appears in the list, and ignore the
1223 order of the list.  To form the union of two sets, use @code{append} (as
1224 long as you don't mind having duplicate elements).  Other useful
1225 functions for sets include @code{memq} and @code{delq}, and their
1226 @code{equal} versions, @code{member} and @code{delete}.
1228 @cindex CL note---lack @code{union}, @code{intersection}
1229 @quotation
1230 @b{Common Lisp note:} Common Lisp has functions @code{union} (which
1231 avoids duplicate elements) and @code{intersection} for set operations,
1232 but GNU Emacs Lisp does not have them.  You can write them in Lisp if
1233 you wish.
1234 @end quotation
1236 @defun memq object list
1237 @cindex membership in a list
1238 This function tests to see whether @var{object} is a member of
1239 @var{list}.  If it is, @code{memq} returns a list starting with the
1240 first occurrence of @var{object}.  Otherwise, it returns @code{nil}.
1241 The letter @samp{q} in @code{memq} says that it uses @code{eq} to
1242 compare @var{object} against the elements of the list.  For example:
1244 @example
1245 @group
1246 (memq 'b '(a b c b a))
1247      @result{} (b c b a)
1248 @end group
1249 @group
1250 (memq '(2) '((1) (2)))    ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1251      @result{} nil
1252 @end group
1253 @end example
1254 @end defun
1256 @defun member-ignore-case object list
1257 This function is like @code{member}, except that it ignores
1258 differences in letter-case and text representation: upper-case and
1259 lower-case letters are treated as equal, and unibyte strings are
1260 converted to multibyte prior to comparison.
1261 @end defun
1263 @defun delq object list
1264 @cindex deletion of elements
1265 This function destructively removes all elements @code{eq} to
1266 @var{object} from @var{list}.  The letter @samp{q} in @code{delq} says
1267 that it uses @code{eq} to compare @var{object} against the elements of
1268 the list, like @code{memq} and @code{remq}.
1269 @end defun
1271 When @code{delq} deletes elements from the front of the list, it does so
1272 simply by advancing down the list and returning a sublist that starts
1273 after those elements:
1275 @example
1276 @group
1277 (delq 'a '(a b c)) @equiv{} (cdr '(a b c))
1278 @end group
1279 @end example
1281 When an element to be deleted appears in the middle of the list,
1282 removing it involves changing the @sc{cdr}s (@pxref{Setcdr}).
1284 @example
1285 @group
1286 (setq sample-list '(a b c (4)))
1287      @result{} (a b c (4))
1288 @end group
1289 @group
1290 (delq 'a sample-list)
1291      @result{} (b c (4))
1292 @end group
1293 @group
1294 sample-list
1295      @result{} (a b c (4))
1296 @end group
1297 @group
1298 (delq 'c sample-list)
1299      @result{} (a b (4))
1300 @end group
1301 @group
1302 sample-list
1303      @result{} (a b (4))
1304 @end group
1305 @end example
1307 Note that @code{(delq 'c sample-list)} modifies @code{sample-list} to
1308 splice out the third element, but @code{(delq 'a sample-list)} does not
1309 splice anything---it just returns a shorter list.  Don't assume that a
1310 variable which formerly held the argument @var{list} now has fewer
1311 elements, or that it still holds the original list!  Instead, save the
1312 result of @code{delq} and use that.  Most often we store the result back
1313 into the variable that held the original list:
1315 @example
1316 (setq flowers (delq 'rose flowers))
1317 @end example
1319 In the following example, the @code{(4)} that @code{delq} attempts to match
1320 and the @code{(4)} in the @code{sample-list} are not @code{eq}:
1322 @example
1323 @group
1324 (delq '(4) sample-list)
1325      @result{} (a c (4))
1326 @end group
1327 @end example
1329 The following two functions are like @code{memq} and @code{delq} but use
1330 @code{equal} rather than @code{eq} to compare elements.  @xref{Equality
1331 Predicates}.
1333 @defun member object list
1334 The function @code{member} tests to see whether @var{object} is a member
1335 of @var{list}, comparing members with @var{object} using @code{equal}.
1336 If @var{object} is a member, @code{member} returns a list starting with
1337 its first occurrence in @var{list}.  Otherwise, it returns @code{nil}.
1339 Compare this with @code{memq}:
1341 @example
1342 @group
1343 (member '(2) '((1) (2)))  ; @r{@code{(2)} and @code{(2)} are @code{equal}.}
1344      @result{} ((2))
1345 @end group
1346 @group
1347 (memq '(2) '((1) (2)))    ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1348      @result{} nil
1349 @end group
1350 @group
1351 ;; @r{Two strings with the same contents are @code{equal}.}
1352 (member "foo" '("foo" "bar"))
1353      @result{} ("foo" "bar")
1354 @end group
1355 @end example
1356 @end defun
1358 @defun delete object sequence
1359 If @code{sequence} is a list, this function destructively removes all
1360 elements @code{equal} to @var{object} from @var{sequence}.  For lists,
1361 @code{delete} is to @code{delq} as @code{member} is to @code{memq}: it
1362 uses @code{equal} to compare elements with @var{object}, like
1363 @code{member}; when it finds an element that matches, it removes the
1364 element just as @code{delq} would.
1366 If @code{sequence} is a vector or string, @code{delete} returns a copy
1367 of @code{sequence} with all elements @code{equal} to @code{object}
1368 removed.
1370 For example:
1372 @example
1373 @group
1374 (delete '(2) '((2) (1) (2)))
1375      @result{} ((1))
1376 @end group
1377 @group
1378 (delete '(2) [(2) (1) (2)])
1379      @result{} [(1)]
1380 @end group
1381 @end example
1382 @end defun
1384 @defun remove object sequence
1385 This function is the non-destructive counterpart of @code{delete}.  If
1386 returns a copy of @code{sequence}, a list, vector, or string, with
1387 elements @code{equal} to @code{object} removed.  For example:
1389 @example
1390 @group
1391 (remove '(2) '((2) (1) (2)))
1392      @result{} ((1))
1393 @end group
1394 @group
1395 (remove '(2) [(2) (1) (2)])
1396      @result{} [(1)]
1397 @end group
1398 @end example
1399 @end defun
1401 @quotation
1402 @b{Common Lisp note:} The functions @code{member}, @code{delete} and
1403 @code{remove} in GNU Emacs Lisp are derived from Maclisp, not Common
1404 Lisp.  The Common Lisp versions do not use @code{equal} to compare
1405 elements.
1406 @end quotation
1408   See also the function @code{add-to-list}, in @ref{Setting Variables},
1409 for another way to add an element to a list stored in a variable.
1411 @node Association Lists
1412 @section Association Lists
1413 @cindex association list
1414 @cindex alist
1416   An @dfn{association list}, or @dfn{alist} for short, records a mapping
1417 from keys to values.  It is a list of cons cells called
1418 @dfn{associations}: the @sc{car} of each cons cell is the @dfn{key}, and the
1419 @sc{cdr} is the @dfn{associated value}.@footnote{This usage of ``key''
1420 is not related to the term ``key sequence''; it means a value used to
1421 look up an item in a table.  In this case, the table is the alist, and
1422 the alist associations are the items.}
1424   Here is an example of an alist.  The key @code{pine} is associated with
1425 the value @code{cones}; the key @code{oak} is associated with
1426 @code{acorns}; and the key @code{maple} is associated with @code{seeds}.
1428 @example
1429 @group
1430 ((pine . cones)
1431  (oak . acorns)
1432  (maple . seeds))
1433 @end group
1434 @end example
1436   The associated values in an alist may be any Lisp objects; so may the
1437 keys.  For example, in the following alist, the symbol @code{a} is
1438 associated with the number @code{1}, and the string @code{"b"} is
1439 associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of
1440 the alist element:
1442 @example
1443 ((a . 1) ("b" 2 3))
1444 @end example
1446   Sometimes it is better to design an alist to store the associated
1447 value in the @sc{car} of the @sc{cdr} of the element.  Here is an
1448 example of such an alist:
1450 @example
1451 ((rose red) (lily white) (buttercup yellow))
1452 @end example
1454 @noindent
1455 Here we regard @code{red} as the value associated with @code{rose}.  One
1456 advantage of this kind of alist is that you can store other related
1457 information---even a list of other items---in the @sc{cdr} of the
1458 @sc{cdr}.  One disadvantage is that you cannot use @code{rassq} (see
1459 below) to find the element containing a given value.  When neither of
1460 these considerations is important, the choice is a matter of taste, as
1461 long as you are consistent about it for any given alist.
1463   Note that the same alist shown above could be regarded as having the
1464 associated value in the @sc{cdr} of the element; the value associated
1465 with @code{rose} would be the list @code{(red)}.
1467   Association lists are often used to record information that you might
1468 otherwise keep on a stack, since new associations may be added easily to
1469 the front of the list.  When searching an association list for an
1470 association with a given key, the first one found is returned, if there
1471 is more than one.
1473   In Emacs Lisp, it is @emph{not} an error if an element of an
1474 association list is not a cons cell.  The alist search functions simply
1475 ignore such elements.  Many other versions of Lisp signal errors in such
1476 cases.
1478   Note that property lists are similar to association lists in several
1479 respects.  A property list behaves like an association list in which
1480 each key can occur only once.  @xref{Property Lists}, for a comparison
1481 of property lists and association lists.
1483 @defun assoc key alist
1484 This function returns the first association for @var{key} in
1485 @var{alist}.  It compares @var{key} against the alist elements using
1486 @code{equal} (@pxref{Equality Predicates}).  It returns @code{nil} if no
1487 association in @var{alist} has a @sc{car} @code{equal} to @var{key}.
1488 For example:
1490 @smallexample
1491 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1492      @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1493 (assoc 'oak trees)
1494      @result{} (oak . acorns)
1495 (cdr (assoc 'oak trees))
1496      @result{} acorns
1497 (assoc 'birch trees)
1498      @result{} nil
1499 @end smallexample
1501 Here is another example, in which the keys and values are not symbols:
1503 @smallexample
1504 (setq needles-per-cluster
1505       '((2 "Austrian Pine" "Red Pine")
1506         (3 "Pitch Pine")
1507         (5 "White Pine")))
1509 (cdr (assoc 3 needles-per-cluster))
1510      @result{} ("Pitch Pine")
1511 (cdr (assoc 2 needles-per-cluster))
1512      @result{} ("Austrian Pine" "Red Pine")
1513 @end smallexample
1514 @end defun
1516   The functions @code{assoc-ignore-representation} and
1517 @code{assoc-ignore-case} are much like @code{assoc} except using
1518 @code{compare-strings} to do the comparison.  @xref{Text Comparison}.
1520 @defun rassoc value alist
1521 This function returns the first association with value @var{value} in
1522 @var{alist}.  It returns @code{nil} if no association in @var{alist} has
1523 a @sc{cdr} @code{equal} to @var{value}.
1525 @code{rassoc} is like @code{assoc} except that it compares the @sc{cdr} of
1526 each @var{alist} association instead of the @sc{car}.  You can think of
1527 this as ``reverse @code{assoc}'', finding the key for a given value.
1528 @end defun
1530 @defun assq key alist
1531 This function is like @code{assoc} in that it returns the first
1532 association for @var{key} in @var{alist}, but it makes the comparison
1533 using @code{eq} instead of @code{equal}.  @code{assq} returns @code{nil}
1534 if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}.
1535 This function is used more often than @code{assoc}, since @code{eq} is
1536 faster than @code{equal} and most alists use symbols as keys.
1537 @xref{Equality Predicates}.
1539 @smallexample
1540 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1541      @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1542 (assq 'pine trees)
1543      @result{} (pine . cones)
1544 @end smallexample
1546 On the other hand, @code{assq} is not usually useful in alists where the
1547 keys may not be symbols:
1549 @smallexample
1550 (setq leaves
1551       '(("simple leaves" . oak)
1552         ("compound leaves" . horsechestnut)))
1554 (assq "simple leaves" leaves)
1555      @result{} nil
1556 (assoc "simple leaves" leaves)
1557      @result{} ("simple leaves" . oak)
1558 @end smallexample
1559 @end defun
1561 @defun rassq value alist
1562 This function returns the first association with value @var{value} in
1563 @var{alist}.  It returns @code{nil} if no association in @var{alist} has
1564 a @sc{cdr} @code{eq} to @var{value}.
1566 @code{rassq} is like @code{assq} except that it compares the @sc{cdr} of
1567 each @var{alist} association instead of the @sc{car}.  You can think of
1568 this as ``reverse @code{assq}'', finding the key for a given value.
1570 For example:
1572 @smallexample
1573 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1575 (rassq 'acorns trees)
1576      @result{} (oak . acorns)
1577 (rassq 'spores trees)
1578      @result{} nil
1579 @end smallexample
1581 Note that @code{rassq} cannot search for a value stored in the @sc{car}
1582 of the @sc{cdr} of an element:
1584 @smallexample
1585 (setq colors '((rose red) (lily white) (buttercup yellow)))
1587 (rassq 'white colors)
1588      @result{} nil
1589 @end smallexample
1591 In this case, the @sc{cdr} of the association @code{(lily white)} is not
1592 the symbol @code{white}, but rather the list @code{(white)}.  This
1593 becomes clearer if the association is written in dotted pair notation:
1595 @smallexample
1596 (lily white) @equiv{} (lily . (white))
1597 @end smallexample
1598 @end defun
1600 @defun assoc-default key alist &optional test default
1601 This function searches @var{alist} for a match for @var{key}.  For each
1602 element of @var{alist}, it compares the element (if it is an atom) or
1603 the element's @sc{car} (if it is a cons) against @var{key}, by calling
1604 @var{test} with two arguments: the element or its @sc{car}, and
1605 @var{key}.  The arguments are passed in that order so that you can get
1606 useful results using @code{string-match} with an alist that contains
1607 regular expressions (@pxref{Regexp Search}).  If @var{test} is omitted
1608 or @code{nil}, @code{equal} is used for comparison.
1610 If an alist element matches @var{key} by this criterion,
1611 then @code{assoc-default} returns a value based on this element.
1612 If the element is a cons, then the value is the element's @sc{cdr}.
1613 Otherwise, the return value is @var{default}.
1615 If no alist element matches @var{key}, @code{assoc-default} returns
1616 @code{nil}.
1617 @end defun
1619 @defun copy-alist alist
1620 @cindex copying alists
1621 This function returns a two-level deep copy of @var{alist}: it creates a
1622 new copy of each association, so that you can alter the associations of
1623 the new alist without changing the old one.
1625 @smallexample
1626 @group
1627 (setq needles-per-cluster
1628       '((2 . ("Austrian Pine" "Red Pine"))
1629         (3 . ("Pitch Pine"))
1630 @end group
1631         (5 . ("White Pine"))))
1632 @result{}
1633 ((2 "Austrian Pine" "Red Pine")
1634  (3 "Pitch Pine")
1635  (5 "White Pine"))
1637 (setq copy (copy-alist needles-per-cluster))
1638 @result{}
1639 ((2 "Austrian Pine" "Red Pine")
1640  (3 "Pitch Pine")
1641  (5 "White Pine"))
1643 (eq needles-per-cluster copy)
1644      @result{} nil
1645 (equal needles-per-cluster copy)
1646      @result{} t
1647 (eq (car needles-per-cluster) (car copy))
1648      @result{} nil
1649 (cdr (car (cdr needles-per-cluster)))
1650      @result{} ("Pitch Pine")
1651 @group
1652 (eq (cdr (car (cdr needles-per-cluster)))
1653     (cdr (car (cdr copy))))
1654      @result{} t
1655 @end group
1656 @end smallexample
1658   This example shows how @code{copy-alist} makes it possible to change
1659 the associations of one copy without affecting the other:
1661 @smallexample
1662 @group
1663 (setcdr (assq 3 copy) '("Martian Vacuum Pine"))
1664 (cdr (assq 3 needles-per-cluster))
1665      @result{} ("Pitch Pine")
1666 @end group
1667 @end smallexample
1668 @end defun
1670 @defun assq-delete-all key alist
1671 @tindex assq-delete-all
1672 This function deletes from @var{alist} all the elements whose @sc{car}
1673 is @code{eq} to @var{key}.  It returns @var{alist}, modified
1674 in this way.  Note that it modifies the original list structure
1675 of @var{alist}.
1677 @example
1678 (assq-delete-all 'foo
1679                  '((foo 1) (bar 2) (foo 3) (lose 4)))
1680      @result{} ((bar 2) (lose 4))
1681 @end example
1682 @end defun
1684 @ignore
1685    arch-tag: 31fb8a4e-4aa8-4a74-a206-aa00451394d4
1686 @end ignore