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