2 @c This is part of the GNU Emacs Lisp Reference Manual.
3 @c Copyright (C) 1990-1995, 1998-1999, 2001-2015 Free Software
5 @c See the file elisp.texi for copying conditions.
9 @cindex element (of list)
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
18 * Cons Cells:: How lists are made out of cons cells.
19 * List-related Predicates:: Is this object a list? Comparing two lists.
20 * List Elements:: Extracting the pieces of a list.
21 * Building Lists:: Creating list structure.
22 * List Variables:: Modifying lists stored in variables.
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 list of paired elements.
30 @section Lists and Cons Cells
31 @cindex lists and cons cells
33 Lists in Lisp are not a primitive data type; they are built up from
34 @dfn{cons cells} (@pxref{Cons Cell Type}). A cons cell is a data
35 object that represents an ordered pair. That is, it has two slots,
36 and each slot @dfn{holds}, or @dfn{refers to}, some Lisp object. One
37 slot is known as the @sc{car}, and the other is known as the @sc{cdr}.
38 (These names are traditional; see @ref{Cons Cell Type}.) @sc{cdr} is
39 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
46 of 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
48 (this asymmetry between @sc{car} and @sc{cdr} is entirely a matter of
49 convention; at the level of cons cells, the @sc{car} and @sc{cdr}
50 slots have similar properties). Hence, the @sc{cdr} slot of each cons
51 cell in a list refers to the following cons cell.
54 Also by convention, the @sc{cdr} of the last cons cell in a list is
55 @code{nil}. We call such a @code{nil}-terminated structure a
56 @dfn{true list}. In Emacs Lisp, the symbol @code{nil} is both a
57 symbol and a list with no elements. For convenience, the symbol
58 @code{nil} is considered to have @code{nil} as its @sc{cdr} (and also
61 Hence, the @sc{cdr} of a true list is always a true list. The
62 @sc{cdr} of a nonempty true list is a true list containing all the
63 elements except the first.
67 If the @sc{cdr} of a list's last cons cell is some value other than
68 @code{nil}, we call the structure a @dfn{dotted list}, since its
69 printed representation would use dotted pair notation (@pxref{Dotted
70 Pair Notation}). There is one other possibility: some cons cell's
71 @sc{cdr} could point to one of the previous cons cells in the list.
72 We call that structure a @dfn{circular list}.
74 For some purposes, it does not matter whether a list is true,
75 circular or dotted. If a program doesn't look far enough down the
76 list to see the @sc{cdr} of the final cons cell, it won't care.
77 However, some functions that operate on lists demand true lists and
78 signal errors if given a dotted list. Most functions that try to find
79 the end of a list enter infinite loops if given a circular list.
81 @cindex list structure
82 Because most cons cells are used as part of lists, we refer to any
83 structure made out of cons cells as a @dfn{list structure}.
85 @node List-related Predicates
86 @section Predicates on Lists
87 @cindex predicates for lists
88 @cindex list predicates
90 The following predicates test whether a Lisp object is an atom,
91 whether it is a cons cell or is a list, or whether it is the
92 distinguished object @code{nil}. (Many of these predicates can be
93 defined in terms of the others, but they are used so often that it is
97 This function returns @code{t} if @var{object} is a cons cell, @code{nil}
98 otherwise. @code{nil} is not a cons cell, although it @emph{is} a list.
102 This function returns @code{t} if @var{object} is an atom, @code{nil}
103 otherwise. All objects except cons cells are atoms. The symbol
104 @code{nil} is an atom and is also a list; it is the only Lisp object
108 (atom @var{object}) @equiv{} (not (consp @var{object}))
113 This function returns @code{t} if @var{object} is a cons cell or
114 @code{nil}. Otherwise, it returns @code{nil}.
129 This function is the opposite of @code{listp}: it returns @code{t} if
130 @var{object} is not a list. Otherwise, it returns @code{nil}.
133 (listp @var{object}) @equiv{} (not (nlistp @var{object}))
138 This function returns @code{t} if @var{object} is @code{nil}, and
139 returns @code{nil} otherwise. This function is identical to @code{not},
140 but as a matter of clarity we use @code{null} when @var{object} is
141 considered a list and @code{not} when it is considered a truth value
142 (see @code{not} in @ref{Combining Conditions}).
158 @section Accessing Elements of Lists
159 @cindex list elements
162 This function returns the value referred to by the first slot of the
163 cons cell @var{cons-cell}. In other words, it returns the @sc{car} of
166 As a special case, if @var{cons-cell} is @code{nil}, this function
167 returns @code{nil}. Therefore, any list is a valid argument. An
168 error is signaled if the argument is not a cons cell or @code{nil}.
183 This function returns the value referred to by the second slot of the
184 cons cell @var{cons-cell}. In other words, it returns the @sc{cdr} of
187 As a special case, if @var{cons-cell} is @code{nil}, this function
188 returns @code{nil}; therefore, any list is a valid argument. An error
189 is signaled if the argument is not a cons cell or @code{nil}.
203 @defun car-safe object
204 This function lets you take the @sc{car} of a cons cell while avoiding
205 errors for other data types. It returns the @sc{car} of @var{object} if
206 @var{object} is a cons cell, @code{nil} otherwise. This is in contrast
207 to @code{car}, which signals an error if @var{object} is not a list.
211 (car-safe @var{object})
213 (let ((x @var{object}))
221 @defun cdr-safe object
222 This function lets you take the @sc{cdr} of a cons cell while
223 avoiding errors for other data types. It returns the @sc{cdr} of
224 @var{object} if @var{object} is a cons cell, @code{nil} otherwise.
225 This is in contrast to @code{cdr}, which signals an error if
226 @var{object} is not a list.
230 (cdr-safe @var{object})
232 (let ((x @var{object}))
241 This macro provides a convenient way to examine the @sc{car} of a
242 list, and take it off the list, all at once. It operates on the list
243 stored in @var{listname}. It removes the first element from the list,
244 saves the @sc{cdr} into @var{listname}, then returns the removed
247 In the simplest case, @var{listname} is an unquoted symbol naming a
248 list; in that case, this macro is equivalent to @w{@code{(prog1
249 (car listname) (setq listname (cdr listname)))}}.
260 More generally, @var{listname} can be a generalized variable. In that
261 case, this macro saves into @var{listname} using @code{setf}.
262 @xref{Generalized Variables}.
264 For the @code{push} macro, which adds an element to a list,
265 @xref{List Variables}.
269 @anchor{Definition of nth}
270 This function returns the @var{n}th element of @var{list}. Elements
271 are numbered starting with zero, so the @sc{car} of @var{list} is
272 element number zero. If the length of @var{list} is @var{n} or less,
273 the value is @code{nil}.
275 @c Behavior for -ve n undefined since 2013/08; see bug#15059.
277 If @var{n} is negative, @code{nth} returns the first element of @var{list}.
289 (nth n x) @equiv{} (car (nthcdr n x))
293 The function @code{elt} is similar, but applies to any kind of sequence.
294 For historical reasons, it takes its arguments in the opposite order.
295 @xref{Sequence Functions}.
299 This function returns the @var{n}th @sc{cdr} of @var{list}. In other
300 words, it skips past the first @var{n} links of @var{list} and returns
303 @c "or negative" removed 2013/08; see bug#15059.
304 If @var{n} is zero, @code{nthcdr} returns all of
305 @var{list}. If the length of @var{list} is @var{n} or less,
306 @code{nthcdr} returns @code{nil}.
310 (nthcdr 1 '(1 2 3 4))
314 (nthcdr 10 '(1 2 3 4))
318 (nthcdr 0 '(1 2 3 4))
324 @defun last list &optional n
325 This function returns the last link of @var{list}. The @code{car} of
326 this link is the list's last element. If @var{list} is null,
327 @code{nil} is returned. If @var{n} is non-@code{nil}, the
328 @var{n}th-to-last link is returned instead, or the whole of @var{list}
329 if @var{n} is bigger than @var{list}'s length.
332 @defun safe-length list
333 @anchor{Definition of safe-length}
334 This function returns the length of @var{list}, with no risk of either
335 an error or an infinite loop. It generally returns the number of
336 distinct cons cells in the list. However, for circular lists,
337 the value is just an upper bound; it is often too large.
339 If @var{list} is not @code{nil} or a cons cell, @code{safe-length}
343 The most common way to compute the length of a list, when you are not
344 worried that it may be circular, is with @code{length}. @xref{Sequence
347 @defun caar cons-cell
348 This is the same as @code{(car (car @var{cons-cell}))}.
351 @defun cadr cons-cell
352 This is the same as @code{(car (cdr @var{cons-cell}))}
353 or @code{(nth 1 @var{cons-cell})}.
356 @defun cdar cons-cell
357 This is the same as @code{(cdr (car @var{cons-cell}))}.
360 @defun cddr cons-cell
361 This is the same as @code{(cdr (cdr @var{cons-cell}))}
362 or @code{(nthcdr 2 @var{cons-cell})}.
365 @defun butlast x &optional n
366 This function returns the list @var{x} with the last element,
367 or the last @var{n} elements, removed. If @var{n} is greater
368 than zero it makes a copy of the list so as not to damage the
369 original list. In general, @code{(append (butlast @var{x} @var{n})
370 (last @var{x} @var{n}))} will return a list equal to @var{x}.
373 @defun nbutlast x &optional n
374 This is a version of @code{butlast} that works by destructively
375 modifying the @code{cdr} of the appropriate element, rather than
376 making a copy of the list.
380 @section Building Cons Cells and Lists
382 @cindex building lists
384 Many functions build lists, as lists reside at the very heart of Lisp.
385 @code{cons} is the fundamental list-building function; however, it is
386 interesting to note that @code{list} is used more times in the source
387 code for Emacs than @code{cons}.
389 @defun cons object1 object2
390 This function is the most basic function for building new list
391 structure. It creates a new cons cell, making @var{object1} the
392 @sc{car}, and @var{object2} the @sc{cdr}. It then returns the new
393 cons cell. The arguments @var{object1} and @var{object2} may be any
394 Lisp objects, but most often @var{object2} is a list.
412 @code{cons} is often used to add a single element to the front of a
413 list. This is called @dfn{consing the element onto the list}.
414 @footnote{There is no strictly equivalent way to add an element to
415 the end of a list. You can use @code{(append @var{listname} (list
416 @var{newelt}))}, which creates a whole new list by copying @var{listname}
417 and adding @var{newelt} to its end. Or you can use @code{(nconc
418 @var{listname} (list @var{newelt}))}, which modifies @var{listname}
419 by following all the @sc{cdr}s and then replacing the terminating
420 @code{nil}. Compare this to adding an element to the beginning of a
421 list with @code{cons}, which neither copies nor modifies the list.}
425 (setq list (cons newelt list))
428 Note that there is no conflict between the variable named @code{list}
429 used in this example and the function named @code{list} described below;
430 any symbol can serve both purposes.
433 @defun list &rest objects
434 This function creates a list with @var{objects} as its elements. The
435 resulting list is always @code{nil}-terminated. If no @var{objects}
436 are given, the empty list is returned.
441 @result{} (1 2 3 4 5)
444 (list 1 2 '(3 4 5) 'foo)
445 @result{} (1 2 (3 4 5) foo)
454 @defun make-list length object
455 This function creates a list of @var{length} elements, in which each
456 element is @var{object}. Compare @code{make-list} with
457 @code{make-string} (@pxref{Creating Strings}).
462 @result{} (pigs pigs pigs)
469 (setq l (make-list 3 '(a b)))
470 @result{} ((a b) (a b) (a b))
471 (eq (car l) (cadr l))
477 @defun append &rest sequences
478 @cindex copying lists
479 This function returns a list containing all the elements of
480 @var{sequences}. The @var{sequences} may be lists, vectors,
481 bool-vectors, or strings, but the last one should usually be a list.
482 All arguments except the last one are copied, so none of the arguments
483 is altered. (See @code{nconc} in @ref{Rearrangement}, for a way to join
484 lists with no copying.)
486 More generally, the final argument to @code{append} may be any Lisp
487 object. The final argument is not copied or converted; it becomes the
488 @sc{cdr} of the last cons cell in the new list. If the final argument
489 is itself a list, then its elements become in effect elements of the
490 result list. If the final element is not a list, the result is a
491 dotted list since its final @sc{cdr} is not @code{nil} as required
495 Here is an example of using @code{append}:
499 (setq trees '(pine oak))
501 (setq more-trees (append '(maple birch) trees))
502 @result{} (maple birch pine oak)
509 @result{} (maple birch pine oak)
512 (eq trees (cdr (cdr more-trees)))
517 You can see how @code{append} works by looking at a box diagram. The
518 variable @code{trees} is set to the list @code{(pine oak)} and then the
519 variable @code{more-trees} is set to the list @code{(maple birch pine
520 oak)}. However, the variable @code{trees} continues to refer to the
527 | --- --- --- --- -> --- --- --- ---
528 --> | | |--> | | |--> | | |--> | | |--> nil
529 --- --- --- --- --- --- --- ---
532 --> maple -->birch --> pine --> oak
536 An empty sequence contributes nothing to the value returned by
537 @code{append}. As a consequence of this, a final @code{nil} argument
538 forces a copy of the previous argument:
546 (setq wood (append trees nil))
560 This once was the usual way to copy a list, before the function
561 @code{copy-sequence} was invented. @xref{Sequences Arrays Vectors}.
563 Here we show the use of vectors and strings as arguments to @code{append}:
567 (append [a b] "cd" nil)
568 @result{} (a b 99 100)
572 With the help of @code{apply} (@pxref{Calling Functions}), we can append
573 all the lists in a list of lists:
577 (apply 'append '((a b c) nil (x y z) nil))
578 @result{} (a b c x y z)
582 If no @var{sequences} are given, @code{nil} is returned:
591 Here are some examples where the final argument is not a list:
597 @result{} (x y . [z])
601 The second example shows that when the final argument is a sequence but
602 not a list, the sequence's elements do not become elements of the
603 resulting list. Instead, the sequence becomes the final @sc{cdr}, like
604 any other non-list final argument.
606 @defun copy-tree tree &optional vecp
607 This function returns a copy of the tree @code{tree}. If @var{tree} is a
608 cons cell, this makes a new cons cell with the same @sc{car} and
609 @sc{cdr}, then recursively copies the @sc{car} and @sc{cdr} in the
612 Normally, when @var{tree} is anything other than a cons cell,
613 @code{copy-tree} simply returns @var{tree}. However, if @var{vecp} is
614 non-@code{nil}, it copies vectors too (and operates recursively on
618 @defun number-sequence from &optional to separation
619 This returns a list of numbers starting with @var{from} and
620 incrementing by @var{separation}, and ending at or just before
621 @var{to}. @var{separation} can be positive or negative and defaults
622 to 1. If @var{to} is @code{nil} or numerically equal to @var{from},
623 the value is the one-element list @code{(@var{from})}. If @var{to} is
624 less than @var{from} with a positive @var{separation}, or greater than
625 @var{from} with a negative @var{separation}, the value is @code{nil}
626 because those arguments specify an empty sequence.
628 If @var{separation} is 0 and @var{to} is neither @code{nil} nor
629 numerically equal to @var{from}, @code{number-sequence} signals an
630 error, since those arguments specify an infinite sequence.
632 All arguments are numbers.
633 Floating-point arguments can be tricky, because floating-point
634 arithmetic is inexact. For instance, depending on the machine, it may
635 quite well happen that @code{(number-sequence 0.4 0.6 0.2)} returns
636 the one element list @code{(0.4)}, whereas
637 @code{(number-sequence 0.4 0.8 0.2)} returns a list with three
638 elements. The @var{n}th element of the list is computed by the exact
639 formula @code{(+ @var{from} (* @var{n} @var{separation}))}. Thus, if
640 one wants to make sure that @var{to} is included in the list, one can
641 pass an expression of this exact type for @var{to}. Alternatively,
642 one can replace @var{to} with a slightly larger value (or a slightly
643 more negative value if @var{separation} is negative).
648 (number-sequence 4 9)
649 @result{} (4 5 6 7 8 9)
650 (number-sequence 9 4 -1)
651 @result{} (9 8 7 6 5 4)
652 (number-sequence 9 4 -2)
656 (number-sequence 8 5)
658 (number-sequence 5 8 -1)
660 (number-sequence 1.5 6 2)
661 @result{} (1.5 3.5 5.5)
666 @section Modifying List Variables
667 @cindex modify a list
668 @cindex list modification
670 These functions, and one macro, provide convenient ways
671 to modify a list which is stored in a variable.
673 @defmac push element listname
674 This macro creates a new list whose @sc{car} is @var{element} and
675 whose @sc{cdr} is the list specified by @var{listname}, and saves that
676 list in @var{listname}. In the simplest case, @var{listname} is an
677 unquoted symbol naming a list, and this macro is equivalent
678 to @w{@code{(setq @var{listname} (cons @var{element} @var{listname}))}}.
689 More generally, @code{listname} can be a generalized variable. In
690 that case, this macro does the equivalent of @w{@code{(setf
691 @var{listname} (cons @var{element} @var{listname}))}}.
692 @xref{Generalized Variables}.
694 For the @code{pop} macro, which removes the first element from a list,
695 @xref{List Elements}.
698 Two functions modify lists that are the values of variables.
700 @defun add-to-list symbol element &optional append compare-fn
701 This function sets the variable @var{symbol} by consing @var{element}
702 onto the old value, if @var{element} is not already a member of that
703 value. It returns the resulting list, whether updated or not. The
704 value of @var{symbol} had better be a list already before the call.
705 @code{add-to-list} uses @var{compare-fn} to compare @var{element}
706 against existing list members; if @var{compare-fn} is @code{nil}, it
709 Normally, if @var{element} is added, it is added to the front of
710 @var{symbol}, but if the optional argument @var{append} is
711 non-@code{nil}, it is added at the end.
713 The argument @var{symbol} is not implicitly quoted; @code{add-to-list}
714 is an ordinary function, like @code{set} and unlike @code{setq}. Quote
715 the argument yourself if that is what you want.
718 Here's a scenario showing how to use @code{add-to-list}:
724 (add-to-list 'foo 'c) ;; @r{Add @code{c}.}
727 (add-to-list 'foo 'b) ;; @r{No effect.}
730 foo ;; @r{@code{foo} was changed.}
734 An equivalent expression for @code{(add-to-list '@var{var}
735 @var{value})} is this:
738 (or (member @var{value} @var{var})
739 (setq @var{var} (cons @var{value} @var{var})))
742 @defun add-to-ordered-list symbol element &optional order
743 This function sets the variable @var{symbol} by inserting
744 @var{element} into the old value, which must be a list, at the
745 position specified by @var{order}. If @var{element} is already a
746 member of the list, its position in the list is adjusted according
747 to @var{order}. Membership is tested using @code{eq}.
748 This function returns the resulting list, whether updated or not.
750 The @var{order} is typically a number (integer or float), and the
751 elements of the list are sorted in non-decreasing numerical order.
753 @var{order} may also be omitted or @code{nil}. Then the numeric order
754 of @var{element} stays unchanged if it already has one; otherwise,
755 @var{element} has no numeric order. Elements without a numeric list
756 order are placed at the end of the list, in no particular order.
758 Any other value for @var{order} removes the numeric order of @var{element}
759 if it already has one; otherwise, it is equivalent to @code{nil}.
761 The argument @var{symbol} is not implicitly quoted;
762 @code{add-to-ordered-list} is an ordinary function, like @code{set}
763 and unlike @code{setq}. Quote the argument yourself if necessary.
765 The ordering information is stored in a hash table on @var{symbol}'s
766 @code{list-order} property.
769 Here's a scenario showing how to use @code{add-to-ordered-list}:
775 (add-to-ordered-list 'foo 'a 1) ;; @r{Add @code{a}.}
778 (add-to-ordered-list 'foo 'c 3) ;; @r{Add @code{c}.}
781 (add-to-ordered-list 'foo 'b 2) ;; @r{Add @code{b}.}
784 (add-to-ordered-list 'foo 'b 4) ;; @r{Move @code{b}.}
787 (add-to-ordered-list 'foo 'd) ;; @r{Append @code{d}.}
790 (add-to-ordered-list 'foo 'e) ;; @r{Add @code{e}}.
791 @result{} (a c b e d)
793 foo ;; @r{@code{foo} was changed.}
794 @result{} (a c b e d)
797 @node Modifying Lists
798 @section Modifying Existing List Structure
799 @cindex destructive list operations
801 You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the
802 primitives @code{setcar} and @code{setcdr}. We call these ``destructive''
803 operations because they change existing list structure.
805 @cindex CL note---@code{rplaca} vs @code{setcar}
809 @b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and
810 @code{rplacd} to alter list structure; they change structure the same
811 way as @code{setcar} and @code{setcdr}, but the Common Lisp functions
812 return the cons cell while @code{setcar} and @code{setcdr} return the
813 new @sc{car} or @sc{cdr}.
817 * Setcar:: Replacing an element in a list.
818 * Setcdr:: Replacing part of the list backbone.
819 This can be used to remove or add elements.
820 * Rearrangement:: Reordering the elements in a list; combining lists.
824 @subsection Altering List Elements with @code{setcar}
825 @cindex replace list element
826 @cindex list, replace element
828 Changing the @sc{car} of a cons cell is done with @code{setcar}. When
829 used on a list, @code{setcar} replaces one element of a list with a
832 @defun setcar cons object
833 This function stores @var{object} as the new @sc{car} of @var{cons},
834 replacing its previous @sc{car}. In other words, it changes the
835 @sc{car} slot of @var{cons} to refer to @var{object}. It returns the
836 value @var{object}. For example:
854 When a cons cell is part of the shared structure of several lists,
855 storing a new @sc{car} into the cons changes one element of each of
856 these lists. Here is an example:
860 ;; @r{Create two lists that are partly shared.}
863 (setq x2 (cons 'z (cdr x1)))
868 ;; @r{Replace the @sc{car} of a shared link.}
869 (setcar (cdr x1) 'foo)
871 x1 ; @r{Both lists are changed.}
878 ;; @r{Replace the @sc{car} of a link that is not shared.}
881 x1 ; @r{Only one list is changed.}
882 @result{} (baz foo c)
888 Here is a graphical depiction of the shared structure of the two lists
889 in the variables @code{x1} and @code{x2}, showing why replacing @code{b}
894 --- --- --- --- --- ---
895 x1---> | | |----> | | |--> | | |--> nil
896 --- --- --- --- --- ---
910 Here is an alternative form of box diagram, showing the same relationship:
915 -------------- -------------- --------------
916 | car | cdr | | car | cdr | | car | cdr |
917 | a | o------->| b | o------->| c | nil |
919 -------------- | -------------- --------------
931 @subsection Altering the CDR of a List
932 @cindex replace part of list
934 The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}:
936 @defun setcdr cons object
937 This function stores @var{object} as the new @sc{cdr} of @var{cons},
938 replacing its previous @sc{cdr}. In other words, it changes the
939 @sc{cdr} slot of @var{cons} to refer to @var{object}. It returns the
943 Here is an example of replacing the @sc{cdr} of a list with a
944 different list. All but the first element of the list are removed in
945 favor of a different sequence of elements. The first element is
946 unchanged, because it resides in the @sc{car} of the list, and is not
947 reached via the @sc{cdr}.
964 You can delete elements from the middle of a list by altering the
965 @sc{cdr}s of the cons cells in the list. For example, here we delete
966 the second element, @code{b}, from the list @code{(a b c)}, by changing
967 the @sc{cdr} of the first cons cell:
973 (setcdr x1 (cdr (cdr x1)))
980 Here is the result in box notation:
986 -------------- | -------------- | --------------
987 | car | cdr | | | car | cdr | -->| car | cdr |
988 | a | o----- | b | o-------->| c | nil |
990 -------------- -------------- --------------
995 The second cons cell, which previously held the element @code{b}, still
996 exists and its @sc{car} is still @code{b}, but it no longer forms part
999 It is equally easy to insert a new element by changing @sc{cdr}s:
1005 (setcdr x1 (cons 'd (cdr x1)))
1012 Here is this result in box notation:
1016 -------------- ------------- -------------
1017 | car | cdr | | car | cdr | | car | cdr |
1018 | a | o | -->| b | o------->| c | nil |
1019 | | | | | | | | | | |
1020 --------- | -- | ------------- -------------
1033 @subsection Functions that Rearrange Lists
1034 @cindex rearrangement of lists
1035 @cindex reordering, of elements in lists
1036 @cindex modification of lists
1038 Here are some functions that rearrange lists ``destructively'' by
1039 modifying the @sc{cdr}s of their component cons cells. We call these
1040 functions ``destructive'' because they chew up the original lists passed
1041 to them as arguments, relinking their cons cells to form a new list that
1042 is the returned value.
1045 See @code{delq}, in @ref{Sets And Lists}, for another function
1046 that modifies cons cells.
1049 The function @code{delq} in the following section is another example
1050 of destructive list manipulation.
1053 @defun nconc &rest lists
1054 @cindex concatenating lists
1055 @cindex joining lists
1056 This function returns a list containing all the elements of @var{lists}.
1057 Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are
1058 @emph{not} copied. Instead, the last @sc{cdr} of each of the
1059 @var{lists} is changed to refer to the following list. The last of the
1060 @var{lists} is not altered. For example:
1069 @result{} (1 2 3 4 5)
1073 @result{} (1 2 3 4 5)
1077 Since the last argument of @code{nconc} is not itself modified, it is
1078 reasonable to use a constant list, such as @code{'(4 5)}, as in the
1079 above example. For the same reason, the last argument need not be a
1089 @result{} (1 2 3 . z)
1093 @result{} (1 2 3 . z)
1097 However, the other arguments (all but the last) must be lists.
1099 A common pitfall is to use a quoted constant list as a non-last
1100 argument to @code{nconc}. If you do this, your program will change
1101 each time you run it! Here is what happens:
1105 (defun add-foo (x) ; @r{We want this function to add}
1106 (nconc '(foo) x)) ; @r{@code{foo} to the front of its arg.}
1110 (symbol-function 'add-foo)
1111 @result{} (lambda (x) (nconc (quote (foo)) x))
1115 (setq xx (add-foo '(1 2))) ; @r{It seems to work.}
1119 (setq xy (add-foo '(3 4))) ; @r{What happened?}
1120 @result{} (foo 1 2 3 4)
1128 (symbol-function 'add-foo)
1129 @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x)))
1134 @node Sets And Lists
1135 @section Using Lists as Sets
1136 @cindex lists as sets
1139 A list can represent an unordered mathematical set---simply consider a
1140 value an element of a set if it appears in the list, and ignore the
1141 order of the list. To form the union of two sets, use @code{append} (as
1142 long as you don't mind having duplicate elements). You can remove
1143 @code{equal} duplicates using @code{delete-dups}. Other useful
1144 functions for sets include @code{memq} and @code{delq}, and their
1145 @code{equal} versions, @code{member} and @code{delete}.
1147 @cindex CL note---lack @code{union}, @code{intersection}
1149 @b{Common Lisp note:} Common Lisp has functions @code{union} (which
1150 avoids duplicate elements) and @code{intersection} for set operations.
1151 Although standard GNU Emacs Lisp does not have them, the @file{cl-lib}
1152 library provides versions.
1153 @xref{Lists as Sets,,, cl, Common Lisp Extensions}.
1156 @defun memq object list
1157 @cindex membership in a list
1158 This function tests to see whether @var{object} is a member of
1159 @var{list}. If it is, @code{memq} returns a list starting with the
1160 first occurrence of @var{object}. Otherwise, it returns @code{nil}.
1161 The letter @samp{q} in @code{memq} says that it uses @code{eq} to
1162 compare @var{object} against the elements of the list. For example:
1166 (memq 'b '(a b c b a))
1170 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1176 @defun delq object list
1177 @cindex deleting list elements
1178 This function destructively removes all elements @code{eq} to
1179 @var{object} from @var{list}, and returns the resulting list. The
1180 letter @samp{q} in @code{delq} says that it uses @code{eq} to compare
1181 @var{object} against the elements of the list, like @code{memq} and
1184 Typically, when you invoke @code{delq}, you should use the return
1185 value by assigning it to the variable which held the original list.
1186 The reason for this is explained below.
1189 The @code{delq} function deletes elements from the front of the list
1190 by simply advancing down the list, and returning a sublist that starts
1191 after those elements. For example:
1195 (delq 'a '(a b c)) @equiv{} (cdr '(a b c))
1200 When an element to be deleted appears in the middle of the list,
1201 removing it involves changing the @sc{cdr}s (@pxref{Setcdr}).
1205 (setq sample-list '(a b c (4)))
1206 @result{} (a b c (4))
1209 (delq 'a sample-list)
1214 @result{} (a b c (4))
1217 (delq 'c sample-list)
1226 Note that @code{(delq 'c sample-list)} modifies @code{sample-list} to
1227 splice out the third element, but @code{(delq 'a sample-list)} does not
1228 splice anything---it just returns a shorter list. Don't assume that a
1229 variable which formerly held the argument @var{list} now has fewer
1230 elements, or that it still holds the original list! Instead, save the
1231 result of @code{delq} and use that. Most often we store the result back
1232 into the variable that held the original list:
1235 (setq flowers (delq 'rose flowers))
1238 In the following example, the @code{(4)} that @code{delq} attempts to match
1239 and the @code{(4)} in the @code{sample-list} are not @code{eq}:
1243 (delq '(4) sample-list)
1248 If you want to delete elements that are @code{equal} to a given value,
1249 use @code{delete} (see below).
1251 @defun remq object list
1252 This function returns a copy of @var{list}, with all elements removed
1253 which are @code{eq} to @var{object}. The letter @samp{q} in @code{remq}
1254 says that it uses @code{eq} to compare @var{object} against the elements
1259 (setq sample-list '(a b c a b c))
1260 @result{} (a b c a b c)
1263 (remq 'a sample-list)
1268 @result{} (a b c a b c)
1273 @defun memql object list
1274 The function @code{memql} tests to see whether @var{object} is a member
1275 of @var{list}, comparing members with @var{object} using @code{eql},
1276 so floating-point elements are compared by value.
1277 If @var{object} is a member, @code{memql} returns a list starting with
1278 its first occurrence in @var{list}. Otherwise, it returns @code{nil}.
1280 Compare this with @code{memq}:
1284 (memql 1.2 '(1.1 1.2 1.3)) ; @r{@code{1.2} and @code{1.2} are @code{eql}.}
1288 (memq 1.2 '(1.1 1.2 1.3)) ; @r{@code{1.2} and @code{1.2} are not @code{eq}.}
1294 The following three functions are like @code{memq}, @code{delq} and
1295 @code{remq}, but use @code{equal} rather than @code{eq} to compare
1296 elements. @xref{Equality Predicates}.
1298 @defun member object list
1299 The function @code{member} tests to see whether @var{object} is a member
1300 of @var{list}, comparing members with @var{object} using @code{equal}.
1301 If @var{object} is a member, @code{member} returns a list starting with
1302 its first occurrence in @var{list}. Otherwise, it returns @code{nil}.
1304 Compare this with @code{memq}:
1308 (member '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are @code{equal}.}
1312 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1316 ;; @r{Two strings with the same contents are @code{equal}.}
1317 (member "foo" '("foo" "bar"))
1318 @result{} ("foo" "bar")
1323 @defun delete object sequence
1324 This function removes all elements @code{equal} to @var{object} from
1325 @var{sequence}, and returns the resulting sequence.
1327 If @var{sequence} is a list, @code{delete} is to @code{delq} as
1328 @code{member} is to @code{memq}: it uses @code{equal} to compare
1329 elements with @var{object}, like @code{member}; when it finds an
1330 element that matches, it cuts the element out just as @code{delq}
1331 would. As with @code{delq}, you should typically use the return value
1332 by assigning it to the variable which held the original list.
1334 If @code{sequence} is a vector or string, @code{delete} returns a copy
1335 of @code{sequence} with all elements @code{equal} to @code{object}
1342 (setq l '((2) (1) (2)))
1347 ;; @r{If you want to change @code{l} reliably,}
1348 ;; @r{write @code{(setq l (delete '(2) l))}.}
1351 (setq l '((2) (1) (2)))
1356 ;; @r{In this case, it makes no difference whether you set @code{l},}
1357 ;; @r{but you should do so for the sake of the other case.}
1360 (delete '(2) [(2) (1) (2)])
1366 @defun remove object sequence
1367 This function is the non-destructive counterpart of @code{delete}. It
1368 returns a copy of @code{sequence}, a list, vector, or string, with
1369 elements @code{equal} to @code{object} removed. For example:
1373 (remove '(2) '((2) (1) (2)))
1377 (remove '(2) [(2) (1) (2)])
1384 @b{Common Lisp note:} The functions @code{member}, @code{delete} and
1385 @code{remove} in GNU Emacs Lisp are derived from Maclisp, not Common
1386 Lisp. The Common Lisp versions do not use @code{equal} to compare
1390 @defun member-ignore-case object list
1391 This function is like @code{member}, except that @var{object} should
1392 be a string and that it ignores differences in letter-case and text
1393 representation: upper-case and lower-case letters are treated as
1394 equal, and unibyte strings are converted to multibyte prior to
1398 @defun delete-dups list
1399 This function destructively removes all @code{equal} duplicates from
1400 @var{list}, stores the result in @var{list} and returns it. Of
1401 several @code{equal} occurrences of an element in @var{list},
1402 @code{delete-dups} keeps the first one.
1405 See also the function @code{add-to-list}, in @ref{List Variables},
1406 for a way to add an element to a list stored in a variable and used as a
1409 @node Association Lists
1410 @section Association Lists
1411 @cindex association list
1414 An @dfn{association list}, or @dfn{alist} for short, records a mapping
1415 from keys to values. It is a list of cons cells called
1416 @dfn{associations}: the @sc{car} of each cons cell is the @dfn{key}, and the
1417 @sc{cdr} is the @dfn{associated value}.@footnote{This usage of ``key''
1418 is not related to the term ``key sequence''; it means a value used to
1419 look up an item in a table. In this case, the table is the alist, and
1420 the alist associations are the items.}
1422 Here is an example of an alist. The key @code{pine} is associated with
1423 the value @code{cones}; the key @code{oak} is associated with
1424 @code{acorns}; and the key @code{maple} is associated with @code{seeds}.
1434 Both the values and the keys in an alist may be any Lisp objects.
1435 For example, in the following alist, the symbol @code{a} is
1436 associated with the number @code{1}, and the string @code{"b"} is
1437 associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of
1444 Sometimes it is better to design an alist to store the associated
1445 value in the @sc{car} of the @sc{cdr} of the element. Here is an
1446 example of such an alist:
1449 ((rose red) (lily white) (buttercup yellow))
1453 Here we regard @code{red} as the value associated with @code{rose}. One
1454 advantage of this kind of alist is that you can store other related
1455 information---even a list of other items---in the @sc{cdr} of the
1456 @sc{cdr}. One disadvantage is that you cannot use @code{rassq} (see
1457 below) to find the element containing a given value. When neither of
1458 these considerations is important, the choice is a matter of taste, as
1459 long as you are consistent about it for any given alist.
1461 The same alist shown above could be regarded as having the
1462 associated value in the @sc{cdr} of the element; the value associated
1463 with @code{rose} would be the list @code{(red)}.
1465 Association lists are often used to record information that you might
1466 otherwise keep on a stack, since new associations may be added easily to
1467 the front of the list. When searching an association list for an
1468 association with a given key, the first one found is returned, if there
1471 In Emacs Lisp, it is @emph{not} an error if an element of an
1472 association list is not a cons cell. The alist search functions simply
1473 ignore such elements. Many other versions of Lisp signal errors in such
1476 Note that property lists are similar to association lists in several
1477 respects. A property list behaves like an association list in which
1478 each key can occur only once. @xref{Property Lists}, for a comparison
1479 of property lists and association lists.
1481 @defun assoc key alist
1482 This function returns the first association for @var{key} in
1483 @var{alist}, comparing @var{key} against the alist elements using
1484 @code{equal} (@pxref{Equality Predicates}). It returns @code{nil} if no
1485 association in @var{alist} has a @sc{car} @code{equal} to @var{key}.
1489 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1490 @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1492 @result{} (oak . acorns)
1493 (cdr (assoc 'oak trees))
1495 (assoc 'birch trees)
1499 Here is another example, in which the keys and values are not symbols:
1502 (setq needles-per-cluster
1503 '((2 "Austrian Pine" "Red Pine")
1507 (cdr (assoc 3 needles-per-cluster))
1508 @result{} ("Pitch Pine")
1509 (cdr (assoc 2 needles-per-cluster))
1510 @result{} ("Austrian Pine" "Red Pine")
1514 The function @code{assoc-string} is much like @code{assoc} except
1515 that it ignores certain differences between strings. @xref{Text
1518 @defun rassoc value alist
1519 This function returns the first association with value @var{value} in
1520 @var{alist}. It returns @code{nil} if no association in @var{alist} has
1521 a @sc{cdr} @code{equal} to @var{value}.
1523 @code{rassoc} is like @code{assoc} except that it compares the @sc{cdr} of
1524 each @var{alist} association instead of the @sc{car}. You can think of
1525 this as ``reverse @code{assoc}'', finding the key for a given value.
1528 @defun assq key alist
1529 This function is like @code{assoc} in that it returns the first
1530 association for @var{key} in @var{alist}, but it makes the comparison
1531 using @code{eq} instead of @code{equal}. @code{assq} returns @code{nil}
1532 if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}.
1533 This function is used more often than @code{assoc}, since @code{eq} is
1534 faster than @code{equal} and most alists use symbols as keys.
1535 @xref{Equality Predicates}.
1538 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1539 @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1541 @result{} (pine . cones)
1544 On the other hand, @code{assq} is not usually useful in alists where the
1545 keys may not be symbols:
1549 '(("simple leaves" . oak)
1550 ("compound leaves" . horsechestnut)))
1552 (assq "simple leaves" leaves)
1554 (assoc "simple leaves" leaves)
1555 @result{} ("simple leaves" . oak)
1559 @defun rassq value alist
1560 This function returns the first association with value @var{value} in
1561 @var{alist}. It returns @code{nil} if no association in @var{alist} has
1562 a @sc{cdr} @code{eq} to @var{value}.
1564 @code{rassq} is like @code{assq} except that it compares the @sc{cdr} of
1565 each @var{alist} association instead of the @sc{car}. You can think of
1566 this as ``reverse @code{assq}'', finding the key for a given value.
1571 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1573 (rassq 'acorns trees)
1574 @result{} (oak . acorns)
1575 (rassq 'spores trees)
1579 @code{rassq} cannot search for a value stored in the @sc{car}
1580 of the @sc{cdr} of an element:
1583 (setq colors '((rose red) (lily white) (buttercup yellow)))
1585 (rassq 'white colors)
1589 In this case, the @sc{cdr} of the association @code{(lily white)} is not
1590 the symbol @code{white}, but rather the list @code{(white)}. This
1591 becomes clearer if the association is written in dotted pair notation:
1594 (lily white) @equiv{} (lily . (white))
1598 @defun assoc-default key alist &optional test default
1599 This function searches @var{alist} for a match for @var{key}. For each
1600 element of @var{alist}, it compares the element (if it is an atom) or
1601 the element's @sc{car} (if it is a cons) against @var{key}, by calling
1602 @var{test} with two arguments: the element or its @sc{car}, and
1603 @var{key}. The arguments are passed in that order so that you can get
1604 useful results using @code{string-match} with an alist that contains
1605 regular expressions (@pxref{Regexp Search}). If @var{test} is omitted
1606 or @code{nil}, @code{equal} is used for comparison.
1608 If an alist element matches @var{key} by this criterion,
1609 then @code{assoc-default} returns a value based on this element.
1610 If the element is a cons, then the value is the element's @sc{cdr}.
1611 Otherwise, the return value is @var{default}.
1613 If no alist element matches @var{key}, @code{assoc-default} returns
1617 @defun copy-alist alist
1618 @cindex copying alists
1619 This function returns a two-level deep copy of @var{alist}: it creates a
1620 new copy of each association, so that you can alter the associations of
1621 the new alist without changing the old one.
1625 (setq needles-per-cluster
1626 '((2 . ("Austrian Pine" "Red Pine"))
1627 (3 . ("Pitch Pine"))
1629 (5 . ("White Pine"))))
1631 ((2 "Austrian Pine" "Red Pine")
1635 (setq copy (copy-alist needles-per-cluster))
1637 ((2 "Austrian Pine" "Red Pine")
1641 (eq needles-per-cluster copy)
1643 (equal needles-per-cluster copy)
1645 (eq (car needles-per-cluster) (car copy))
1647 (cdr (car (cdr needles-per-cluster)))
1648 @result{} ("Pitch Pine")
1650 (eq (cdr (car (cdr needles-per-cluster)))
1651 (cdr (car (cdr copy))))
1656 This example shows how @code{copy-alist} makes it possible to change
1657 the associations of one copy without affecting the other:
1661 (setcdr (assq 3 copy) '("Martian Vacuum Pine"))
1662 (cdr (assq 3 needles-per-cluster))
1663 @result{} ("Pitch Pine")
1668 @defun assq-delete-all key alist
1669 This function deletes from @var{alist} all the elements whose @sc{car}
1670 is @code{eq} to @var{key}, much as if you used @code{delq} to delete
1671 each such element one by one. It returns the shortened alist, and
1672 often modifies the original list structure of @var{alist}. For
1673 correct results, use the return value of @code{assq-delete-all} rather
1674 than looking at the saved value of @var{alist}.
1677 (setq alist '((foo 1) (bar 2) (foo 3) (lose 4)))
1678 @result{} ((foo 1) (bar 2) (foo 3) (lose 4))
1679 (assq-delete-all 'foo alist)
1680 @result{} ((bar 2) (lose 4))
1682 @result{} ((foo 1) (bar 2) (lose 4))
1686 @defun rassq-delete-all value alist
1687 This function deletes from @var{alist} all the elements whose @sc{cdr}
1688 is @code{eq} to @var{value}. It returns the shortened alist, and
1689 often modifies the original list structure of @var{alist}.
1690 @code{rassq-delete-all} is like @code{assq-delete-all} except that it
1691 compares the @sc{cdr} of each @var{alist} association instead of the
1695 @node Property Lists
1696 @section Property Lists
1697 @cindex property list
1700 A @dfn{property list} (@dfn{plist} for short) is a list of paired
1701 elements. Each of the pairs associates a property name (usually a
1702 symbol) with a property or value. Here is an example of a property
1706 (pine cones numbers (1 2 3) color "blue")
1710 This property list associates @code{pine} with @code{cones},
1711 @code{numbers} with @code{(1 2 3)}, and @code{color} with
1712 @code{"blue"}. The property names and values can be any Lisp objects,
1713 but the names are usually symbols (as they are in this example).
1715 Property lists are used in several contexts. For instance, the
1716 function @code{put-text-property} takes an argument which is a
1717 property list, specifying text properties and associated values which
1718 are to be applied to text in a string or buffer. @xref{Text
1721 Another prominent use of property lists is for storing symbol
1722 properties. Every symbol possesses a list of properties, used to
1723 record miscellaneous information about the symbol; these properties
1724 are stored in the form of a property list. @xref{Symbol Properties}.
1727 * Plists and Alists:: Comparison of the advantages of property
1728 lists and association lists.
1729 * Plist Access:: Accessing property lists stored elsewhere.
1732 @node Plists and Alists
1733 @subsection Property Lists and Association Lists
1734 @cindex plist vs. alist
1735 @cindex alist vs. plist
1737 @cindex property lists vs association lists
1738 Association lists (@pxref{Association Lists}) are very similar to
1739 property lists. In contrast to association lists, the order of the
1740 pairs in the property list is not significant, since the property
1741 names must be distinct.
1743 Property lists are better than association lists for attaching
1744 information to various Lisp function names or variables. If your
1745 program keeps all such information in one association list, it will
1746 typically need to search that entire list each time it checks for an
1747 association for a particular Lisp function name or variable, which
1748 could be slow. By contrast, if you keep the same information in the
1749 property lists of the function names or variables themselves, each
1750 search will scan only the length of one property list, which is
1751 usually short. This is why the documentation for a variable is
1752 recorded in a property named @code{variable-documentation}. The byte
1753 compiler likewise uses properties to record those functions needing
1756 However, association lists have their own advantages. Depending on
1757 your application, it may be faster to add an association to the front of
1758 an association list than to update a property. All properties for a
1759 symbol are stored in the same property list, so there is a possibility
1760 of a conflict between different uses of a property name. (For this
1761 reason, it is a good idea to choose property names that are probably
1762 unique, such as by beginning the property name with the program's usual
1763 name-prefix for variables and functions.) An association list may be
1764 used like a stack where associations are pushed on the front of the list
1765 and later discarded; this is not possible with a property list.
1768 @subsection Property Lists Outside Symbols
1769 @cindex plist access
1770 @cindex accessing plist properties
1772 The following functions can be used to manipulate property lists.
1773 They all compare property names using @code{eq}.
1775 @defun plist-get plist property
1776 This returns the value of the @var{property} property stored in the
1777 property list @var{plist}. It accepts a malformed @var{plist}
1778 argument. If @var{property} is not found in the @var{plist}, it
1779 returns @code{nil}. For example,
1782 (plist-get '(foo 4) 'foo)
1784 (plist-get '(foo 4 bad) 'foo)
1786 (plist-get '(foo 4 bad) 'bad)
1788 (plist-get '(foo 4 bad) 'bar)
1793 @defun plist-put plist property value
1794 This stores @var{value} as the value of the @var{property} property in
1795 the property list @var{plist}. It may modify @var{plist} destructively,
1796 or it may construct a new list structure without altering the old. The
1797 function returns the modified property list, so you can store that back
1798 in the place where you got @var{plist}. For example,
1801 (setq my-plist '(bar t foo 4))
1802 @result{} (bar t foo 4)
1803 (setq my-plist (plist-put my-plist 'foo 69))
1804 @result{} (bar t foo 69)
1805 (setq my-plist (plist-put my-plist 'quux '(a)))
1806 @result{} (bar t foo 69 quux (a))
1810 @defun lax-plist-get plist property
1811 Like @code{plist-get} except that it compares properties
1812 using @code{equal} instead of @code{eq}.
1815 @defun lax-plist-put plist property value
1816 Like @code{plist-put} except that it compares properties
1817 using @code{equal} instead of @code{eq}.
1820 @defun plist-member plist property
1821 This returns non-@code{nil} if @var{plist} contains the given
1822 @var{property}. Unlike @code{plist-get}, this allows you to distinguish
1823 between a missing property and a property with the value @code{nil}.
1824 The value is actually the tail of @var{plist} whose @code{car} is