*** empty log message ***
[emacs.git] / lispref / lists.texi
blob458d011c489fbc9b708454002a6a2e31bfca018f
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 reruns the last link of the given @var{list}.  The
388 @code{car} of this link is the list's last element.  If @var{list} is
389 null, @code{nil} is returned.  If @var{n} is non-nil the
390 @var{n}-th-to-last link is returned instead, or the whole @var{list} if
391 @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 @node Building Lists
426 @comment  node-name,  next,  previous,  up
427 @section Building Cons Cells and Lists
428 @cindex cons cells
429 @cindex building lists
431   Many functions build lists, as lists reside at the very heart of Lisp.
432 @code{cons} is the fundamental list-building function; however, it is
433 interesting to note that @code{list} is used more times in the source
434 code for Emacs than @code{cons}.
436 @defun cons object1 object2
437 This function is the fundamental function used to build new list
438 structure.  It creates a new cons cell, making @var{object1} the
439 @sc{car}, and @var{object2} the @sc{cdr}.  It then returns the new cons
440 cell.  The arguments @var{object1} and @var{object2} may be any Lisp
441 objects, but most often @var{object2} is a list.
443 @example
444 @group
445 (cons 1 '(2))
446      @result{} (1 2)
447 @end group
448 @group
449 (cons 1 '())
450      @result{} (1)
451 @end group
452 @group
453 (cons 1 2)
454      @result{} (1 . 2)
455 @end group
456 @end example
458 @cindex consing
459 @code{cons} is often used to add a single element to the front of a
460 list.  This is called @dfn{consing the element onto the list}.  For
461 example:
463 @example
464 (setq list (cons newelt list))
465 @end example
467 Note that there is no conflict between the variable named @code{list}
468 used in this example and the function named @code{list} described below;
469 any symbol can serve both purposes.
470 @end defun
472 @tindex push
473 @defmac push newelt listname
474 This macro provides an alternative way to write
475 @code{(setq @var{listname} (cons @var{newelt} @var{listname}))}.
476 It is new in Emacs 21.
477 @end defmac
479 @defun list &rest objects
480 This function creates a list with @var{objects} as its elements.  The
481 resulting list is always @code{nil}-terminated.  If no @var{objects}
482 are given, the empty list is returned.
484 @example
485 @group
486 (list 1 2 3 4 5)
487      @result{} (1 2 3 4 5)
488 @end group
489 @group
490 (list 1 2 '(3 4 5) 'foo)
491      @result{} (1 2 (3 4 5) foo)
492 @end group
493 @group
494 (list)
495      @result{} nil
496 @end group
497 @end example
498 @end defun
500 @defun make-list length object
501 This function creates a list of length @var{length}, in which all the
502 elements have the identical value @var{object}.  Compare
503 @code{make-list} with @code{make-string} (@pxref{Creating Strings}).
505 @example
506 @group
507 (make-list 3 'pigs)
508      @result{} (pigs pigs pigs)
509 @end group
510 @group
511 (make-list 0 'pigs)
512      @result{} nil
513 @end group
514 @end example
515 @end defun
517 @defun append &rest sequences
518 @cindex copying lists
519 This function returns a list containing all the elements of
520 @var{sequences}.  The @var{sequences} may be lists, vectors,
521 bool-vectors, or strings, but the last one should usually be a list.
522 All arguments except the last one are copied, so none of the arguments
523 is altered.  (See @code{nconc} in @ref{Rearrangement}, for a way to join
524 lists with no copying.)
526 More generally, the final argument to @code{append} may be any Lisp
527 object.  The final argument is not copied or converted; it becomes the
528 @sc{cdr} of the last cons cell in the new list.  If the final argument
529 is itself a list, then its elements become in effect elements of the
530 result list.  If the final element is not a list, the result is a
531 ``dotted list'' since its final @sc{cdr} is not @code{nil} as required
532 in a true list.
534 The @code{append} function also allows integers as arguments.  It
535 converts them to strings of digits, making up the decimal print
536 representation of the integer, and then uses the strings instead of the
537 original integers.  @strong{Don't use this feature; we plan to eliminate
538 it.  If you already use this feature, change your programs now!}  The
539 proper way to convert an integer to a decimal number in this way is with
540 @code{format} (@pxref{Formatting Strings}) or @code{number-to-string}
541 (@pxref{String Conversion}).
542 @end defun
544   Here is an example of using @code{append}:
546 @example
547 @group
548 (setq trees '(pine oak))
549      @result{} (pine oak)
550 (setq more-trees (append '(maple birch) trees))
551      @result{} (maple birch pine oak)
552 @end group
554 @group
555 trees
556      @result{} (pine oak)
557 more-trees
558      @result{} (maple birch pine oak)
559 @end group
560 @group
561 (eq trees (cdr (cdr more-trees)))
562      @result{} t
563 @end group
564 @end example
566   You can see how @code{append} works by looking at a box diagram.  The
567 variable @code{trees} is set to the list @code{(pine oak)} and then the
568 variable @code{more-trees} is set to the list @code{(maple birch pine
569 oak)}.  However, the variable @code{trees} continues to refer to the
570 original list:
572 @smallexample
573 @group
574 more-trees                trees
575 |                           |
576 |     --- ---      --- ---   -> --- ---      --- ---
577  --> |   |   |--> |   |   |--> |   |   |--> |   |   |--> nil
578       --- ---      --- ---      --- ---      --- ---
579        |            |            |            |
580        |            |            |            |
581         --> maple    -->birch     --> pine     --> oak
582 @end group
583 @end smallexample
585   An empty sequence contributes nothing to the value returned by
586 @code{append}.  As a consequence of this, a final @code{nil} argument
587 forces a copy of the previous argument:
589 @example
590 @group
591 trees
592      @result{} (pine oak)
593 @end group
594 @group
595 (setq wood (append trees nil))
596      @result{} (pine oak)
597 @end group
598 @group
599 wood
600      @result{} (pine oak)
601 @end group
602 @group
603 (eq wood trees)
604      @result{} nil
605 @end group
606 @end example
608 @noindent
609 This once was the usual way to copy a list, before the function
610 @code{copy-sequence} was invented.  @xref{Sequences Arrays Vectors}.
612   Here we show the use of vectors and strings as arguments to @code{append}:
614 @example
615 @group
616 (append [a b] "cd" nil)
617      @result{} (a b 99 100)
618 @end group
619 @end example
621   With the help of @code{apply} (@pxref{Calling Functions}), we can append
622 all the lists in a list of lists:
624 @example
625 @group
626 (apply 'append '((a b c) nil (x y z) nil))
627      @result{} (a b c x y z)
628 @end group
629 @end example
631   If no @var{sequences} are given, @code{nil} is returned:
633 @example
634 @group
635 (append)
636      @result{} nil
637 @end group
638 @end example
640   Here are some examples where the final argument is not a list:
642 @example
643 (append '(x y) 'z)
644      @result{} (x y . z)
645 (append '(x y) [z])
646      @result{} (x y . [z])
647 @end example
649 @noindent
650 The second example shows that when the final argument is a sequence but
651 not a list, the sequence's elements do not become elements of the
652 resulting list.  Instead, the sequence becomes the final @sc{cdr}, like
653 any other non-list final argument.
655 @defun reverse list
656 This function creates a new list whose elements are the elements of
657 @var{list}, but in reverse order.  The original argument @var{list} is
658 @emph{not} altered.
660 @example
661 @group
662 (setq x '(1 2 3 4))
663      @result{} (1 2 3 4)
664 @end group
665 @group
666 (reverse x)
667      @result{} (4 3 2 1)
669      @result{} (1 2 3 4)
670 @end group
671 @end example
672 @end defun
674 @defun remq object list
675 This function returns a copy of @var{list}, with all elements removed
676 which are @code{eq} to @var{object}.  The letter @samp{q} in @code{remq}
677 says that it uses @code{eq} to compare @var{object} against the elements
678 of @code{list}.
680 @example
681 @group
682 (setq sample-list '(a b c a b c))
683      @result{} (a b c a b c)
684 @end group
685 @group
686 (remq 'a sample-list)
687      @result{} (b c b c)
688 @end group
689 @group
690 sample-list
691      @result{} (a b c a b c)
692 @end group
693 @end example
694 @noindent
695 The function @code{delq} offers a way to perform this operation
696 destructively.  See @ref{Sets And Lists}.
697 @end defun
699 @node Modifying Lists
700 @section Modifying Existing List Structure
701 @cindex destructive list operations
703   You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the
704 primitives @code{setcar} and @code{setcdr}.  We call these ``destructive'' 
705 operations because they change existing list structure.
707 @cindex CL note---@code{rplaca} vrs @code{setcar}
708 @quotation
709 @findex rplaca
710 @findex rplacd
711 @b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and
712 @code{rplacd} to alter list structure; they change structure the same
713 way as @code{setcar} and @code{setcdr}, but the Common Lisp functions
714 return the cons cell while @code{setcar} and @code{setcdr} return the
715 new @sc{car} or @sc{cdr}.
716 @end quotation
718 @menu
719 * Setcar::          Replacing an element in a list.
720 * Setcdr::          Replacing part of the list backbone.
721                       This can be used to remove or add elements.
722 * Rearrangement::   Reordering the elements in a list; combining lists.
723 @end menu
725 @node Setcar
726 @subsection Altering List Elements with @code{setcar}
728   Changing the @sc{car} of a cons cell is done with @code{setcar}.  When
729 used on a list, @code{setcar} replaces one element of a list with a
730 different element.
732 @defun setcar cons object
733 This function stores @var{object} as the new @sc{car} of @var{cons},
734 replacing its previous @sc{car}.  In other words, it changes the
735 @sc{car} slot of @var{cons} to refer to @var{object}.  It returns the
736 value @var{object}.  For example:
738 @example
739 @group
740 (setq x '(1 2))
741      @result{} (1 2)
742 @end group
743 @group
744 (setcar x 4)
745      @result{} 4
746 @end group
747 @group
749      @result{} (4 2)
750 @end group
751 @end example
752 @end defun
754   When a cons cell is part of the shared structure of several lists,
755 storing a new @sc{car} into the cons changes one element of each of
756 these lists.  Here is an example:
758 @example
759 @group
760 ;; @r{Create two lists that are partly shared.}
761 (setq x1 '(a b c))
762      @result{} (a b c)
763 (setq x2 (cons 'z (cdr x1)))
764      @result{} (z b c)
765 @end group
767 @group
768 ;; @r{Replace the @sc{car} of a shared link.}
769 (setcar (cdr x1) 'foo)
770      @result{} foo
771 x1                           ; @r{Both lists are changed.}
772      @result{} (a foo c)
774      @result{} (z foo c)
775 @end group
777 @group
778 ;; @r{Replace the @sc{car} of a link that is not shared.}
779 (setcar x1 'baz)
780      @result{} baz
781 x1                           ; @r{Only one list is changed.}
782      @result{} (baz foo c)
784      @result{} (z foo c)
785 @end group
786 @end example
788   Here is a graphical depiction of the shared structure of the two lists
789 in the variables @code{x1} and @code{x2}, showing why replacing @code{b}
790 changes them both:
792 @example
793 @group
794         --- ---        --- ---      --- ---
795 x1---> |   |   |----> |   |   |--> |   |   |--> nil
796         --- ---        --- ---      --- ---
797          |        -->   |            |
798          |       |      |            |
799           --> a  |       --> b        --> c
800                  |
801        --- ---   |
802 x2--> |   |   |--
803        --- ---
804         |
805         |
806          --> z
807 @end group
808 @end example
810   Here is an alternative form of box diagram, showing the same relationship:
812 @example
813 @group
815  --------------       --------------       --------------
816 | car   | cdr  |     | car   | cdr  |     | car   | cdr  |
817 |   a   |   o------->|   b   |   o------->|   c   |  nil |
818 |       |      |  -->|       |      |     |       |      |
819  --------------  |    --------------       --------------
820                  |
821 x2:              |
822  --------------  |
823 | car   | cdr  | |
824 |   z   |   o----
825 |       |      |
826  --------------
827 @end group
828 @end example
830 @node Setcdr
831 @subsection Altering the CDR of a List
833   The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}:
835 @defun setcdr cons object
836 This function stores @var{object} as the new @sc{cdr} of @var{cons},
837 replacing its previous @sc{cdr}.  In other words, it changes the
838 @sc{cdr} slot of @var{cons} to refer to @var{object}.  It returns the
839 value @var{object}.
840 @end defun
842   Here is an example of replacing the @sc{cdr} of a list with a
843 different list.  All but the first element of the list are removed in
844 favor of a different sequence of elements.  The first element is
845 unchanged, because it resides in the @sc{car} of the list, and is not
846 reached via the @sc{cdr}.
848 @example
849 @group
850 (setq x '(1 2 3))
851      @result{} (1 2 3)
852 @end group
853 @group
854 (setcdr x '(4))
855      @result{} (4)
856 @end group
857 @group
859      @result{} (1 4)
860 @end group
861 @end example
863   You can delete elements from the middle of a list by altering the
864 @sc{cdr}s of the cons cells in the list.  For example, here we delete
865 the second element, @code{b}, from the list @code{(a b c)}, by changing
866 the @sc{cdr} of the first cons cell:
868 @example
869 @group
870 (setq x1 '(a b c))
871      @result{} (a b c)
872 (setcdr x1 (cdr (cdr x1)))
873      @result{} (c)
875      @result{} (a c)
876 @end group
877 @end example
879 @need 4000
880   Here is the result in box notation:
882 @example
883 @group
884                    --------------------
885                   |                    |
886  --------------   |   --------------   |    --------------
887 | car   | cdr  |  |  | car   | cdr  |   -->| car   | cdr  |
888 |   a   |   o-----   |   b   |   o-------->|   c   |  nil |
889 |       |      |     |       |      |      |       |      |
890  --------------       --------------        --------------
891 @end group
892 @end example
894 @noindent
895 The second cons cell, which previously held the element @code{b}, still
896 exists and its @sc{car} is still @code{b}, but it no longer forms part
897 of this list.
899   It is equally easy to insert a new element by changing @sc{cdr}s:
901 @example
902 @group
903 (setq x1 '(a b c))
904      @result{} (a b c)
905 (setcdr x1 (cons 'd (cdr x1)))
906      @result{} (d b c)
908      @result{} (a d b c)
909 @end group
910 @end example
912   Here is this result in box notation:
914 @smallexample
915 @group
916  --------------        -------------       -------------
917 | car  | cdr   |      | car  | cdr  |     | car  | cdr  |
918 |   a  |   o   |   -->|   b  |   o------->|   c  |  nil |
919 |      |   |   |  |   |      |      |     |      |      |
920  --------- | --   |    -------------       -------------
921            |      |
922      -----         --------
923     |                      |
924     |    ---------------   |
925     |   | car   | cdr   |  |
926      -->|   d   |   o------
927         |       |       |
928          ---------------
929 @end group
930 @end smallexample
932 @node Rearrangement
933 @subsection Functions that Rearrange Lists
934 @cindex rearrangement of lists
935 @cindex modification of lists
937   Here are some functions that rearrange lists ``destructively'' by
938 modifying the @sc{cdr}s of their component cons cells.  We call these
939 functions ``destructive'' because they chew up the original lists passed
940 to them as arguments, relinking their cons cells to form a new list that
941 is the returned value.
943 @ifnottex
944   See @code{delq}, in @ref{Sets And Lists}, for another function
945 that modifies cons cells.
946 @end ifnottex
947 @iftex
948    The function @code{delq} in the following section is another example
949 of destructive list manipulation.
950 @end iftex
952 @defun nconc &rest lists
953 @cindex concatenating lists
954 @cindex joining lists
955 This function returns a list containing all the elements of @var{lists}.
956 Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are
957 @emph{not} copied.  Instead, the last @sc{cdr} of each of the
958 @var{lists} is changed to refer to the following list.  The last of the
959 @var{lists} is not altered.  For example:
961 @example
962 @group
963 (setq x '(1 2 3))
964      @result{} (1 2 3)
965 @end group
966 @group
967 (nconc x '(4 5))
968      @result{} (1 2 3 4 5)
969 @end group
970 @group
972      @result{} (1 2 3 4 5)
973 @end group
974 @end example
976    Since the last argument of @code{nconc} is not itself modified, it is
977 reasonable to use a constant list, such as @code{'(4 5)}, as in the
978 above example.  For the same reason, the last argument need not be a
979 list:
981 @example
982 @group
983 (setq x '(1 2 3))
984      @result{} (1 2 3)
985 @end group
986 @group
987 (nconc x 'z)
988      @result{} (1 2 3 . z)
989 @end group
990 @group
992      @result{} (1 2 3 . z)
993 @end group
994 @end example
996 However, the other arguments (all but the last) must be lists.
998 A common pitfall is to use a quoted constant list as a non-last
999 argument to @code{nconc}.  If you do this, your program will change
1000 each time you run it!  Here is what happens:
1002 @smallexample
1003 @group
1004 (defun add-foo (x)            ; @r{We want this function to add}
1005   (nconc '(foo) x))           ;   @r{@code{foo} to the front of its arg.}
1006 @end group
1008 @group
1009 (symbol-function 'add-foo)
1010      @result{} (lambda (x) (nconc (quote (foo)) x))
1011 @end group
1013 @group
1014 (setq xx (add-foo '(1 2)))    ; @r{It seems to work.}
1015      @result{} (foo 1 2)
1016 @end group
1017 @group
1018 (setq xy (add-foo '(3 4)))    ; @r{What happened?}
1019      @result{} (foo 1 2 3 4)
1020 @end group
1021 @group
1022 (eq xx xy)
1023      @result{} t
1024 @end group
1026 @group
1027 (symbol-function 'add-foo)
1028      @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x)))
1029 @end group
1030 @end smallexample
1031 @end defun
1033 @defun nreverse list
1034 @cindex reversing a list
1035   This function reverses the order of the elements of @var{list}.
1036 Unlike @code{reverse}, @code{nreverse} alters its argument by reversing
1037 the @sc{cdr}s in the cons cells forming the list.  The cons cell that
1038 used to be the last one in @var{list} becomes the first cons cell of the
1039 value.
1041   For example:
1043 @example
1044 @group
1045 (setq x '(1 2 3 4))
1046      @result{} (1 2 3 4)
1047 @end group
1048 @group
1050      @result{} (1 2 3 4)
1051 (nreverse x)
1052      @result{} (4 3 2 1)
1053 @end group
1054 @group
1055 ;; @r{The cons cell that was first is now last.}
1057      @result{} (1)
1058 @end group
1059 @end example
1061   To avoid confusion, we usually store the result of @code{nreverse}
1062 back in the same variable which held the original list:
1064 @example
1065 (setq x (nreverse x))
1066 @end example
1068   Here is the @code{nreverse} of our favorite example, @code{(a b c)},
1069 presented graphically:
1071 @smallexample
1072 @group
1073 @r{Original list head:}                       @r{Reversed list:}
1074  -------------        -------------        ------------
1075 | car  | cdr  |      | car  | cdr  |      | car | cdr  |
1076 |   a  |  nil |<--   |   b  |   o  |<--   |   c |   o  |
1077 |      |      |   |  |      |   |  |   |  |     |   |  |
1078  -------------    |   --------- | -    |   -------- | -
1079                   |             |      |            |
1080                    -------------        ------------
1081 @end group
1082 @end smallexample
1083 @end defun
1085 @defun sort list predicate
1086 @cindex stable sort
1087 @cindex sorting lists
1088 This function sorts @var{list} stably, though destructively, and
1089 returns the sorted list.  It compares elements using @var{predicate}.  A
1090 stable sort is one in which elements with equal sort keys maintain their
1091 relative order before and after the sort.  Stability is important when
1092 successive sorts are used to order elements according to different
1093 criteria.
1095 The argument @var{predicate} must be a function that accepts two
1096 arguments.  It is called with two elements of @var{list}.  To get an
1097 increasing order sort, the @var{predicate} should return @code{t} if the
1098 first element is ``less than'' the second, or @code{nil} if not.
1100 The comparison function @var{predicate} must give reliable results for
1101 any given pair of arguments, at least within a single call to
1102 @code{sort}.  It must be @dfn{antisymmetric}; that is, if @var{a} is
1103 less than @var{b}, @var{b} must not be less than @var{a}.  It must be
1104 @dfn{transitive}---that is, if @var{a} is less than @var{b}, and @var{b}
1105 is less than @var{c}, then @var{a} must be less than @var{c}.  If you
1106 use a comparison function which does not meet these requirements, the
1107 result of @code{sort} is unpredictable.
1109 The destructive aspect of @code{sort} is that it rearranges the cons
1110 cells forming @var{list} by changing @sc{cdr}s.  A nondestructive sort
1111 function would create new cons cells to store the elements in their
1112 sorted order.  If you wish to make a sorted copy without destroying the
1113 original, copy it first with @code{copy-sequence} and then sort.
1115 Sorting does not change the @sc{car}s of the cons cells in @var{list};
1116 the cons cell that originally contained the element @code{a} in
1117 @var{list} still has @code{a} in its @sc{car} after sorting, but it now
1118 appears in a different position in the list due to the change of
1119 @sc{cdr}s.  For example:
1121 @example
1122 @group
1123 (setq nums '(1 3 2 6 5 4 0))
1124      @result{} (1 3 2 6 5 4 0)
1125 @end group
1126 @group
1127 (sort nums '<)
1128      @result{} (0 1 2 3 4 5 6)
1129 @end group
1130 @group
1131 nums
1132      @result{} (1 2 3 4 5 6)
1133 @end group
1134 @end example
1136 @noindent
1137 @strong{Warning}: Note that the list in @code{nums} no longer contains
1138 0; this is the same cons cell that it was before, but it is no longer
1139 the first one in the list.  Don't assume a variable that formerly held
1140 the argument now holds the entire sorted list!  Instead, save the result
1141 of @code{sort} and use that.  Most often we store the result back into
1142 the variable that held the original list:
1144 @example
1145 (setq nums (sort nums '<))
1146 @end example
1148 @xref{Sorting}, for more functions that perform sorting.
1149 See @code{documentation} in @ref{Accessing Documentation}, for a
1150 useful example of @code{sort}.
1151 @end defun
1153 @node Sets And Lists
1154 @section Using Lists as Sets
1155 @cindex lists as sets
1156 @cindex sets
1158   A list can represent an unordered mathematical set---simply consider a
1159 value an element of a set if it appears in the list, and ignore the
1160 order of the list.  To form the union of two sets, use @code{append} (as
1161 long as you don't mind having duplicate elements).  Other useful
1162 functions for sets include @code{memq} and @code{delq}, and their
1163 @code{equal} versions, @code{member} and @code{delete}.
1165 @cindex CL note---lack @code{union}, @code{intersection}
1166 @quotation
1167 @b{Common Lisp note:} Common Lisp has functions @code{union} (which
1168 avoids duplicate elements) and @code{intersection} for set operations,
1169 but GNU Emacs Lisp does not have them.  You can write them in Lisp if
1170 you wish.
1171 @end quotation
1173 @defun memq object list
1174 @cindex membership in a list
1175 This function tests to see whether @var{object} is a member of
1176 @var{list}.  If it is, @code{memq} returns a list starting with the
1177 first occurrence of @var{object}.  Otherwise, it returns @code{nil}.
1178 The letter @samp{q} in @code{memq} says that it uses @code{eq} to
1179 compare @var{object} against the elements of the list.  For example:
1181 @example
1182 @group
1183 (memq 'b '(a b c b a))
1184      @result{} (b c b a)
1185 @end group
1186 @group
1187 (memq '(2) '((1) (2)))    ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1188      @result{} nil
1189 @end group
1190 @end example
1191 @end defun
1193 @defun delq object list
1194 @cindex deletion of elements
1195 This function destructively removes all elements @code{eq} to
1196 @var{object} from @var{list}.  The letter @samp{q} in @code{delq} says
1197 that it uses @code{eq} to compare @var{object} against the elements of
1198 the list, like @code{memq} and @code{remq}.
1199 @end defun
1201 When @code{delq} deletes elements from the front of the list, it does so
1202 simply by advancing down the list and returning a sublist that starts
1203 after those elements:
1205 @example
1206 @group
1207 (delq 'a '(a b c)) @equiv{} (cdr '(a b c))
1208 @end group
1209 @end example
1211 When an element to be deleted appears in the middle of the list,
1212 removing it involves changing the @sc{cdr}s (@pxref{Setcdr}).
1214 @example
1215 @group
1216 (setq sample-list '(a b c (4)))
1217      @result{} (a b c (4))
1218 @end group
1219 @group
1220 (delq 'a sample-list)
1221      @result{} (b c (4))
1222 @end group
1223 @group
1224 sample-list
1225      @result{} (a b c (4))
1226 @end group
1227 @group
1228 (delq 'c sample-list)
1229      @result{} (a b (4))
1230 @end group
1231 @group
1232 sample-list
1233      @result{} (a b (4))
1234 @end group
1235 @end example
1237 Note that @code{(delq 'c sample-list)} modifies @code{sample-list} to
1238 splice out the third element, but @code{(delq 'a sample-list)} does not
1239 splice anything---it just returns a shorter list.  Don't assume that a
1240 variable which formerly held the argument @var{list} now has fewer
1241 elements, or that it still holds the original list!  Instead, save the
1242 result of @code{delq} and use that.  Most often we store the result back
1243 into the variable that held the original list:
1245 @example
1246 (setq flowers (delq 'rose flowers))
1247 @end example
1249 In the following example, the @code{(4)} that @code{delq} attempts to match
1250 and the @code{(4)} in the @code{sample-list} are not @code{eq}:
1252 @example
1253 @group
1254 (delq '(4) sample-list)
1255      @result{} (a c (4))
1256 @end group
1257 @end example
1259 The following two functions are like @code{memq} and @code{delq} but use
1260 @code{equal} rather than @code{eq} to compare elements.  @xref{Equality
1261 Predicates}.
1263 @defun member object list
1264 The function @code{member} tests to see whether @var{object} is a member
1265 of @var{list}, comparing members with @var{object} using @code{equal}.
1266 If @var{object} is a member, @code{member} returns a list starting with
1267 its first occurrence in @var{list}.  Otherwise, it returns @code{nil}.
1269 Compare this with @code{memq}:
1271 @example
1272 @group
1273 (member '(2) '((1) (2)))  ; @r{@code{(2)} and @code{(2)} are @code{equal}.}
1274      @result{} ((2))
1275 @end group
1276 @group
1277 (memq '(2) '((1) (2)))    ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1278      @result{} nil
1279 @end group
1280 @group
1281 ;; @r{Two strings with the same contents are @code{equal}.}
1282 (member "foo" '("foo" "bar"))
1283      @result{} ("foo" "bar")
1284 @end group
1285 @end example
1286 @end defun
1288 @defun delete object sequence
1289 If @code{sequence} is a list, this function destructively removes all
1290 elements @code{equal} to @var{object} from @var{sequence}.  For lists,
1291 @code{delete} is to @code{delq} as @code{member} is to @code{memq}: it
1292 uses @code{equal} to compare elements with @var{object}, like
1293 @code{member}; when it finds an element that matches, it removes the
1294 element just as @code{delq} would.
1296 If @code{sequence} is a vector or string, @code{delete} returns a copy
1297 of @code{sequence} with all elements @code{equal} to @code{object}
1298 removed.
1300 For example:
1302 @example
1303 @group
1304 (delete '(2) '((2) (1) (2)))
1305      @result{} ((1))
1306 @end group
1307 @group
1308 (delete '(2) [(2) (1) (2)])
1309      @result{} [(1)]
1310 @end group
1311 @end example
1312 @end defun
1314 @defun remove object sequence
1315 This function is the non-destructive counterpart of @code{delete}.  If
1316 returns a copy of @code{sequence}, a list, vector, or string, with
1317 elements @code{equal} to @code{object} removed.  For example:
1319 @example
1320 @group
1321 (remove '(2) '((2) (1) (2)))
1322      @result{} ((1))
1323 @end group
1324 @group
1325 (remove '(2) [(2) (1) (2)])
1326      @result{} [(1)]
1327 @end group
1328 @end example
1329 @end defun
1331 @quotation
1332 @b{Common Lisp note:} The functions @code{member}, @code{delete} and
1333 @code{remove} in GNU Emacs Lisp are derived from Maclisp, not Common
1334 Lisp.  The Common Lisp versions do not use @code{equal} to compare
1335 elements.
1336 @end quotation
1338   See also the function @code{add-to-list}, in @ref{Setting Variables},
1339 for another way to add an element to a list stored in a variable.
1341 @node Association Lists
1342 @section Association Lists
1343 @cindex association list
1344 @cindex alist
1346   An @dfn{association list}, or @dfn{alist} for short, records a mapping
1347 from keys to values.  It is a list of cons cells called
1348 @dfn{associations}: the @sc{car} of each cons cell is the @dfn{key}, and the
1349 @sc{cdr} is the @dfn{associated value}.@footnote{This usage of ``key''
1350 is not related to the term ``key sequence''; it means a value used to
1351 look up an item in a table.  In this case, the table is the alist, and
1352 the alist associations are the items.}
1354   Here is an example of an alist.  The key @code{pine} is associated with
1355 the value @code{cones}; the key @code{oak} is associated with
1356 @code{acorns}; and the key @code{maple} is associated with @code{seeds}.
1358 @example
1359 @group
1360 '((pine . cones)
1361   (oak . acorns)
1362   (maple . seeds))
1363 @end group
1364 @end example
1366   The associated values in an alist may be any Lisp objects; so may the
1367 keys.  For example, in the following alist, the symbol @code{a} is
1368 associated with the number @code{1}, and the string @code{"b"} is
1369 associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of
1370 the alist element:
1372 @example
1373 ((a . 1) ("b" 2 3))
1374 @end example
1376   Sometimes it is better to design an alist to store the associated
1377 value in the @sc{car} of the @sc{cdr} of the element.  Here is an
1378 example:
1380 @example
1381 '((rose red) (lily white) (buttercup yellow))
1382 @end example
1384 @noindent
1385 Here we regard @code{red} as the value associated with @code{rose}.  One
1386 advantage of this kind of alist is that you can store other related
1387 information---even a list of other items---in the @sc{cdr} of the
1388 @sc{cdr}.  One disadvantage is that you cannot use @code{rassq} (see
1389 below) to find the element containing a given value.  When neither of
1390 these considerations is important, the choice is a matter of taste, as
1391 long as you are consistent about it for any given alist.
1393   Note that the same alist shown above could be regarded as having the
1394 associated value in the @sc{cdr} of the element; the value associated
1395 with @code{rose} would be the list @code{(red)}.
1397   Association lists are often used to record information that you might
1398 otherwise keep on a stack, since new associations may be added easily to
1399 the front of the list.  When searching an association list for an
1400 association with a given key, the first one found is returned, if there
1401 is more than one.
1403   In Emacs Lisp, it is @emph{not} an error if an element of an
1404 association list is not a cons cell.  The alist search functions simply
1405 ignore such elements.  Many other versions of Lisp signal errors in such
1406 cases.
1408   Note that property lists are similar to association lists in several
1409 respects.  A property list behaves like an association list in which
1410 each key can occur only once.  @xref{Property Lists}, for a comparison
1411 of property lists and association lists.
1413 @defun assoc key alist
1414 This function returns the first association for @var{key} in
1415 @var{alist}.  It compares @var{key} against the alist elements using
1416 @code{equal} (@pxref{Equality Predicates}).  It returns @code{nil} if no
1417 association in @var{alist} has a @sc{car} @code{equal} to @var{key}.
1418 For example:
1420 @smallexample
1421 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1422      @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1423 (assoc 'oak trees)
1424      @result{} (oak . acorns)
1425 (cdr (assoc 'oak trees))
1426      @result{} acorns
1427 (assoc 'birch trees)
1428      @result{} nil
1429 @end smallexample
1431 Here is another example, in which the keys and values are not symbols:
1433 @smallexample
1434 (setq needles-per-cluster
1435       '((2 "Austrian Pine" "Red Pine")
1436         (3 "Pitch Pine")
1437         (5 "White Pine")))
1439 (cdr (assoc 3 needles-per-cluster))
1440      @result{} ("Pitch Pine")
1441 (cdr (assoc 2 needles-per-cluster))
1442      @result{} ("Austrian Pine" "Red Pine")
1443 @end smallexample
1444 @end defun
1446   The functions @code{assoc-ignore-representation} and
1447 @code{assoc-ignore-case} are much like @code{assoc} except using
1448 @code{compare-strings} to do the comparison.  @xref{Text Comparison}.
1450 @defun rassoc value alist
1451 This function returns the first association with value @var{value} in
1452 @var{alist}.  It returns @code{nil} if no association in @var{alist} has
1453 a @sc{cdr} @code{equal} to @var{value}.
1455 @code{rassoc} is like @code{assoc} except that it compares the @sc{cdr} of
1456 each @var{alist} association instead of the @sc{car}.  You can think of
1457 this as ``reverse @code{assoc}'', finding the key for a given value.
1458 @end defun
1460 @defun assq key alist
1461 This function is like @code{assoc} in that it returns the first
1462 association for @var{key} in @var{alist}, but it makes the comparison
1463 using @code{eq} instead of @code{equal}.  @code{assq} returns @code{nil}
1464 if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}.
1465 This function is used more often than @code{assoc}, since @code{eq} is
1466 faster than @code{equal} and most alists use symbols as keys.
1467 @xref{Equality Predicates}.
1469 @smallexample
1470 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1471      @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1472 (assq 'pine trees)
1473      @result{} (pine . cones)
1474 @end smallexample
1476 On the other hand, @code{assq} is not usually useful in alists where the
1477 keys may not be symbols:
1479 @smallexample
1480 (setq leaves
1481       '(("simple leaves" . oak)
1482         ("compound leaves" . horsechestnut)))
1484 (assq "simple leaves" leaves)
1485      @result{} nil
1486 (assoc "simple leaves" leaves)
1487      @result{} ("simple leaves" . oak)
1488 @end smallexample
1489 @end defun
1491 @defun rassq value alist
1492 This function returns the first association with value @var{value} in
1493 @var{alist}.  It returns @code{nil} if no association in @var{alist} has
1494 a @sc{cdr} @code{eq} to @var{value}.
1496 @code{rassq} is like @code{assq} except that it compares the @sc{cdr} of
1497 each @var{alist} association instead of the @sc{car}.  You can think of
1498 this as ``reverse @code{assq}'', finding the key for a given value.
1500 For example:
1502 @smallexample
1503 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1505 (rassq 'acorns trees)
1506      @result{} (oak . acorns)
1507 (rassq 'spores trees)
1508      @result{} nil
1509 @end smallexample
1511 Note that @code{rassq} cannot search for a value stored in the @sc{car}
1512 of the @sc{cdr} of an element:
1514 @smallexample
1515 (setq colors '((rose red) (lily white) (buttercup yellow)))
1517 (rassq 'white colors)
1518      @result{} nil
1519 @end smallexample
1521 In this case, the @sc{cdr} of the association @code{(lily white)} is not
1522 the symbol @code{white}, but rather the list @code{(white)}.  This
1523 becomes clearer if the association is written in dotted pair notation:
1525 @smallexample
1526 (lily white) @equiv{} (lily . (white))
1527 @end smallexample
1528 @end defun
1530 @defun assoc-default key alist test default
1531 This function searches @var{alist} for a match for @var{key}.  For each
1532 element of @var{alist}, it compares the element (if it is an atom) or
1533 the element's @sc{car} (if it is a cons) against @var{key}, by calling
1534 @var{test} with two arguments: the element or its @sc{car}, and
1535 @var{key}.  The arguments are passed in that order so that you can get
1536 useful results using @code{string-match} with an alist that contains
1537 regular expressions (@pxref{Regexp Search}).  If @var{test} is omitted
1538 or @code{nil}, @code{equal} is used for comparison.
1540 If an alist element matches @var{key} by this criterion,
1541 then @code{assoc-default} returns a value based on this element.
1542 If the element is a cons, then the value is the element's @sc{cdr}.
1543 Otherwise, the return value is @var{default}.
1545 If no alist element matches @var{key}, @code{assoc-default} returns
1546 @code{nil}.
1547 @end defun
1549 @defun copy-alist alist
1550 @cindex copying alists
1551 This function returns a two-level deep copy of @var{alist}: it creates a
1552 new copy of each association, so that you can alter the associations of
1553 the new alist without changing the old one.
1555 @smallexample
1556 @group
1557 (setq needles-per-cluster
1558       '((2 . ("Austrian Pine" "Red Pine"))
1559         (3 . ("Pitch Pine"))
1560 @end group
1561         (5 . ("White Pine"))))
1562 @result{}
1563 ((2 "Austrian Pine" "Red Pine")
1564  (3 "Pitch Pine")
1565  (5 "White Pine"))
1567 (setq copy (copy-alist needles-per-cluster))
1568 @result{}
1569 ((2 "Austrian Pine" "Red Pine")
1570  (3 "Pitch Pine")
1571  (5 "White Pine"))
1573 (eq needles-per-cluster copy)
1574      @result{} nil
1575 (equal needles-per-cluster copy)
1576      @result{} t
1577 (eq (car needles-per-cluster) (car copy))
1578      @result{} nil
1579 (cdr (car (cdr needles-per-cluster)))
1580      @result{} ("Pitch Pine")
1581 @group
1582 (eq (cdr (car (cdr needles-per-cluster)))
1583     (cdr (car (cdr copy))))
1584      @result{} t
1585 @end group
1586 @end smallexample
1588   This example shows how @code{copy-alist} makes it possible to change
1589 the associations of one copy without affecting the other:
1591 @smallexample
1592 @group
1593 (setcdr (assq 3 copy) '("Martian Vacuum Pine"))
1594 (cdr (assq 3 needles-per-cluster))
1595      @result{} ("Pitch Pine")
1596 @end group
1597 @end smallexample
1598 @end defun
1600 @defun assoc-delete-all key alist
1601 @tindex assoc-delete-all
1602 This function deletes from @var{alist} all the elements whose @sc{car}
1603 is @var{key}.  It returns the modified alist.
1605 @example
1606 (assoc-delete-all 'foo
1607                   '((foo 1) (bar 2) (foo 3) (lose 4)))
1608      @result{} ((bar 2) (lose 4))
1609 @end example
1610 @end defun