2 @c This is part of the GNU Emacs Lisp Reference Manual.
3 @c Copyright (C) 1990-1995, 1998-1999, 2001-2012 Free Software Foundation, Inc.
4 @c See the file elisp.texi for copying conditions.
5 @setfilename ../../info/lists
6 @node Lists, Sequences Arrays Vectors, Strings and Characters, Top
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.
29 @section Lists and Cons Cells
30 @cindex lists and cons cells
32 Lists in Lisp are not a primitive data type; they are built up from
33 @dfn{cons cells} (@pxref{Cons Cell Type}). A cons cell is a data
34 object that represents an ordered pair. That is, it has two slots,
35 and each slot @dfn{holds}, or @dfn{refers to}, some Lisp object. One
36 slot is known as the @sc{car}, and the other is known as the @sc{cdr}.
37 (These names are traditional; see @ref{Cons Cell Type}.) @sc{cdr} is
38 pronounced ``could-er''.
40 We say that ``the @sc{car} of this cons cell is'' whatever object
41 its @sc{car} slot currently holds, and likewise for the @sc{cdr}.
43 A list is a series of cons cells ``chained together'', so that each
44 cell refers to the next one. There is one cons cell for each element
45 of the list. By convention, the @sc{car}s of the cons cells hold the
46 elements of the list, and the @sc{cdr}s are used to chain the list
47 (this asymmetry between @sc{car} and @sc{cdr} is entirely a matter of
48 convention; at the level of cons cells, the @sc{car} and @sc{cdr}
49 slots have similar properties). Hence, the @sc{cdr} slot of each cons
50 cell in a list refers to the following cons cell.
53 Also by convention, the @sc{cdr} of the last cons cell in a list is
54 @code{nil}. We call such a @code{nil}-terminated structure a
55 @dfn{true list}. In Emacs Lisp, the symbol @code{nil} is both a
56 symbol and a list with no elements. For convenience, the symbol
57 @code{nil} is considered to have @code{nil} as its @sc{cdr} (and also
60 Hence, the @sc{cdr} of a true list is always a true list. The
61 @sc{cdr} of a nonempty true list is a true list containing all the
62 elements except the first.
66 If the @sc{cdr} of a list's last cons cell is some value other than
67 @code{nil}, we call the structure a @dfn{dotted list}, since its
68 printed representation would use dotted pair notation (@pxref{Dotted
69 Pair Notation}). There is one other possibility: some cons cell's
70 @sc{cdr} could point to one of the previous cons cells in the list.
71 We call that structure a @dfn{circular list}.
73 For some purposes, it does not matter whether a list is true,
74 circular or dotted. If a program doesn't look far enough down the
75 list to see the @sc{cdr} of the final cons cell, it won't care.
76 However, some functions that operate on lists demand true lists and
77 signal errors if given a dotted list. Most functions that try to find
78 the end of a list enter infinite loops if given a circular list.
80 @cindex list structure
81 Because most cons cells are used as part of lists, we refer to any
82 structure made out of cons cells as a @dfn{list structure}.
84 @node List-related Predicates
85 @section Predicates on Lists
87 The following predicates test whether a Lisp object is an atom,
88 whether it is a cons cell or is a list, or whether it is the
89 distinguished object @code{nil}. (Many of these predicates can be
90 defined in terms of the others, but they are used so often that it is
91 worth having all of them.)
94 This function returns @code{t} if @var{object} is a cons cell, @code{nil}
95 otherwise. @code{nil} is not a cons cell, although it @emph{is} a list.
99 This function returns @code{t} if @var{object} is an atom, @code{nil}
100 otherwise. All objects except cons cells are atoms. The symbol
101 @code{nil} is an atom and is also a list; it is the only Lisp object
105 (atom @var{object}) @equiv{} (not (consp @var{object}))
110 This function returns @code{t} if @var{object} is a cons cell or
111 @code{nil}. Otherwise, it returns @code{nil}.
126 This function is the opposite of @code{listp}: it returns @code{t} if
127 @var{object} is not a list. Otherwise, it returns @code{nil}.
130 (listp @var{object}) @equiv{} (not (nlistp @var{object}))
135 This function returns @code{t} if @var{object} is @code{nil}, and
136 returns @code{nil} otherwise. This function is identical to @code{not},
137 but as a matter of clarity we use @code{null} when @var{object} is
138 considered a list and @code{not} when it is considered a truth value
139 (see @code{not} in @ref{Combining Conditions}).
155 @section Accessing Elements of Lists
156 @cindex list elements
159 This function returns the value referred to by the first slot of the
160 cons cell @var{cons-cell}. In other words, it returns the @sc{car} of
163 As a special case, if @var{cons-cell} is @code{nil}, this function
164 returns @code{nil}. Therefore, any list is a valid argument. An
165 error is signaled if the argument is not a cons cell or @code{nil}.
180 This function returns the value referred to by the second slot of the
181 cons cell @var{cons-cell}. In other words, it returns the @sc{cdr} of
184 As a special case, if @var{cons-cell} is @code{nil}, this function
185 returns @code{nil}; therefore, any list is a valid argument. An error
186 is signaled if the argument is not a cons cell or @code{nil}.
200 @defun car-safe object
201 This function lets you take the @sc{car} of a cons cell while avoiding
202 errors for other data types. It returns the @sc{car} of @var{object} if
203 @var{object} is a cons cell, @code{nil} otherwise. This is in contrast
204 to @code{car}, which signals an error if @var{object} is not a list.
208 (car-safe @var{object})
210 (let ((x @var{object}))
218 @defun cdr-safe object
219 This function lets you take the @sc{cdr} of a cons cell while
220 avoiding errors for other data types. It returns the @sc{cdr} of
221 @var{object} if @var{object} is a cons cell, @code{nil} otherwise.
222 This is in contrast to @code{cdr}, which signals an error if
223 @var{object} is not a list.
227 (cdr-safe @var{object})
229 (let ((x @var{object}))
238 This macro is a way of examining the @sc{car} of a list,
239 and taking it off the list, all at once.
241 It operates on the list which is stored in the symbol @var{listname}.
242 It removes this element from the list by setting @var{listname}
243 to the @sc{cdr} of its old value---but it also returns the @sc{car}
244 of that list, which is the element being removed.
256 For the @code{pop} macro, which removes an element from a list,
257 @xref{List Variables}.
261 @anchor{Definition of nth}
262 This function returns the @var{n}th element of @var{list}. Elements
263 are numbered starting with zero, so the @sc{car} of @var{list} is
264 element number zero. If the length of @var{list} is @var{n} or less,
265 the value is @code{nil}.
267 If @var{n} is negative, @code{nth} returns the first element of
283 (nth n x) @equiv{} (car (nthcdr n x))
287 The function @code{elt} is similar, but applies to any kind of sequence.
288 For historical reasons, it takes its arguments in the opposite order.
289 @xref{Sequence Functions}.
293 This function returns the @var{n}th @sc{cdr} of @var{list}. In other
294 words, it skips past the first @var{n} links of @var{list} and returns
297 If @var{n} is zero or negative, @code{nthcdr} returns all of
298 @var{list}. If the length of @var{list} is @var{n} or less,
299 @code{nthcdr} returns @code{nil}.
303 (nthcdr 1 '(1 2 3 4))
307 (nthcdr 10 '(1 2 3 4))
311 (nthcdr -3 '(1 2 3 4))
317 @defun last list &optional n
318 This function returns the last link of @var{list}. The @code{car} of
319 this link is the list's last element. If @var{list} is null,
320 @code{nil} is returned. If @var{n} is non-@code{nil}, the
321 @var{n}th-to-last link is returned instead, or the whole of @var{list}
322 if @var{n} is bigger than @var{list}'s length.
325 @defun safe-length list
326 @anchor{Definition of safe-length}
327 This function returns the length of @var{list}, with no risk of either
328 an error or an infinite loop. It generally returns the number of
329 distinct cons cells in the list. However, for circular lists,
330 the value is just an upper bound; it is often too large.
332 If @var{list} is not @code{nil} or a cons cell, @code{safe-length}
336 The most common way to compute the length of a list, when you are not
337 worried that it may be circular, is with @code{length}. @xref{Sequence
340 @defun caar cons-cell
341 This is the same as @code{(car (car @var{cons-cell}))}.
344 @defun cadr cons-cell
345 This is the same as @code{(car (cdr @var{cons-cell}))}
346 or @code{(nth 1 @var{cons-cell})}.
349 @defun cdar cons-cell
350 This is the same as @code{(cdr (car @var{cons-cell}))}.
353 @defun cddr cons-cell
354 This is the same as @code{(cdr (cdr @var{cons-cell}))}
355 or @code{(nthcdr 2 @var{cons-cell})}.
358 @defun butlast x &optional n
359 This function returns the list @var{x} with the last element,
360 or the last @var{n} elements, removed. If @var{n} is greater
361 than zero it makes a copy of the list so as not to damage the
362 original list. In general, @code{(append (butlast @var{x} @var{n})
363 (last @var{x} @var{n}))} will return a list equal to @var{x}.
366 @defun nbutlast x &optional n
367 This is a version of @code{butlast} that works by destructively
368 modifying the @code{cdr} of the appropriate element, rather than
369 making a copy of the list.
373 @comment node-name, next, previous, up
374 @section Building Cons Cells and Lists
376 @cindex building lists
378 Many functions build lists, as lists reside at the very heart of Lisp.
379 @code{cons} is the fundamental list-building function; however, it is
380 interesting to note that @code{list} is used more times in the source
381 code for Emacs than @code{cons}.
383 @defun cons object1 object2
384 This function is the most basic function for building new list
385 structure. It creates a new cons cell, making @var{object1} the
386 @sc{car}, and @var{object2} the @sc{cdr}. It then returns the new
387 cons cell. The arguments @var{object1} and @var{object2} may be any
388 Lisp objects, but most often @var{object2} is a list.
406 @code{cons} is often used to add a single element to the front of a
407 list. This is called @dfn{consing the element onto the list}.
408 @footnote{There is no strictly equivalent way to add an element to
409 the end of a list. You can use @code{(append @var{listname} (list
410 @var{newelt}))}, which creates a whole new list by copying @var{listname}
411 and adding @var{newelt} to its end. Or you can use @code{(nconc
412 @var{listname} (list @var{newelt}))}, which modifies @var{listname}
413 by following all the @sc{cdr}s and then replacing the terminating
414 @code{nil}. Compare this to adding an element to the beginning of a
415 list with @code{cons}, which neither copies nor modifies the list.}
419 (setq list (cons newelt list))
422 Note that there is no conflict between the variable named @code{list}
423 used in this example and the function named @code{list} described below;
424 any symbol can serve both purposes.
427 @defun list &rest objects
428 This function creates a list with @var{objects} as its elements. The
429 resulting list is always @code{nil}-terminated. If no @var{objects}
430 are given, the empty list is returned.
435 @result{} (1 2 3 4 5)
438 (list 1 2 '(3 4 5) 'foo)
439 @result{} (1 2 (3 4 5) foo)
448 @defun make-list length object
449 This function creates a list of @var{length} elements, in which each
450 element is @var{object}. Compare @code{make-list} with
451 @code{make-string} (@pxref{Creating Strings}).
456 @result{} (pigs pigs pigs)
463 (setq l (make-list 3 '(a b)))
464 @result{} ((a b) (a b) (a b))
465 (eq (car l) (cadr l))
471 @defun append &rest sequences
472 @cindex copying lists
473 This function returns a list containing all the elements of
474 @var{sequences}. The @var{sequences} may be lists, vectors,
475 bool-vectors, or strings, but the last one should usually be a list.
476 All arguments except the last one are copied, so none of the arguments
477 is altered. (See @code{nconc} in @ref{Rearrangement}, for a way to join
478 lists with no copying.)
480 More generally, the final argument to @code{append} may be any Lisp
481 object. The final argument is not copied or converted; it becomes the
482 @sc{cdr} of the last cons cell in the new list. If the final argument
483 is itself a list, then its elements become in effect elements of the
484 result list. If the final element is not a list, the result is a
485 dotted list since its final @sc{cdr} is not @code{nil} as required
489 Here is an example of using @code{append}:
493 (setq trees '(pine oak))
495 (setq more-trees (append '(maple birch) trees))
496 @result{} (maple birch pine oak)
503 @result{} (maple birch pine oak)
506 (eq trees (cdr (cdr more-trees)))
511 You can see how @code{append} works by looking at a box diagram. The
512 variable @code{trees} is set to the list @code{(pine oak)} and then the
513 variable @code{more-trees} is set to the list @code{(maple birch pine
514 oak)}. However, the variable @code{trees} continues to refer to the
521 | --- --- --- --- -> --- --- --- ---
522 --> | | |--> | | |--> | | |--> | | |--> nil
523 --- --- --- --- --- --- --- ---
526 --> maple -->birch --> pine --> oak
530 An empty sequence contributes nothing to the value returned by
531 @code{append}. As a consequence of this, a final @code{nil} argument
532 forces a copy of the previous argument:
540 (setq wood (append trees nil))
554 This once was the usual way to copy a list, before the function
555 @code{copy-sequence} was invented. @xref{Sequences Arrays Vectors}.
557 Here we show the use of vectors and strings as arguments to @code{append}:
561 (append [a b] "cd" nil)
562 @result{} (a b 99 100)
566 With the help of @code{apply} (@pxref{Calling Functions}), we can append
567 all the lists in a list of lists:
571 (apply 'append '((a b c) nil (x y z) nil))
572 @result{} (a b c x y z)
576 If no @var{sequences} are given, @code{nil} is returned:
585 Here are some examples where the final argument is not a list:
591 @result{} (x y . [z])
595 The second example shows that when the final argument is a sequence but
596 not a list, the sequence's elements do not become elements of the
597 resulting list. Instead, the sequence becomes the final @sc{cdr}, like
598 any other non-list final argument.
601 This function creates a new list whose elements are the elements of
602 @var{list}, but in reverse order. The original argument @var{list} is
619 @defun copy-tree tree &optional vecp
620 This function returns a copy of the tree @code{tree}. If @var{tree} is a
621 cons cell, this makes a new cons cell with the same @sc{car} and
622 @sc{cdr}, then recursively copies the @sc{car} and @sc{cdr} in the
625 Normally, when @var{tree} is anything other than a cons cell,
626 @code{copy-tree} simply returns @var{tree}. However, if @var{vecp} is
627 non-@code{nil}, it copies vectors too (and operates recursively on
631 @defun number-sequence from &optional to separation
632 This returns a list of numbers starting with @var{from} and
633 incrementing by @var{separation}, and ending at or just before
634 @var{to}. @var{separation} can be positive or negative and defaults
635 to 1. If @var{to} is @code{nil} or numerically equal to @var{from},
636 the value is the one-element list @code{(@var{from})}. If @var{to} is
637 less than @var{from} with a positive @var{separation}, or greater than
638 @var{from} with a negative @var{separation}, the value is @code{nil}
639 because those arguments specify an empty sequence.
641 If @var{separation} is 0 and @var{to} is neither @code{nil} nor
642 numerically equal to @var{from}, @code{number-sequence} signals an
643 error, since those arguments specify an infinite sequence.
645 All arguments can be integers or floating point numbers. However,
646 floating point arguments can be tricky, because floating point
647 arithmetic is inexact. For instance, depending on the machine, it may
648 quite well happen that @code{(number-sequence 0.4 0.6 0.2)} returns
649 the one element list @code{(0.4)}, whereas
650 @code{(number-sequence 0.4 0.8 0.2)} returns a list with three
651 elements. The @var{n}th element of the list is computed by the exact
652 formula @code{(+ @var{from} (* @var{n} @var{separation}))}. Thus, if
653 one wants to make sure that @var{to} is included in the list, one can
654 pass an expression of this exact type for @var{to}. Alternatively,
655 one can replace @var{to} with a slightly larger value (or a slightly
656 more negative value if @var{separation} is negative).
661 (number-sequence 4 9)
662 @result{} (4 5 6 7 8 9)
663 (number-sequence 9 4 -1)
664 @result{} (9 8 7 6 5 4)
665 (number-sequence 9 4 -2)
669 (number-sequence 8 5)
671 (number-sequence 5 8 -1)
673 (number-sequence 1.5 6 2)
674 @result{} (1.5 3.5 5.5)
679 @section Modifying List Variables
681 These functions, and one macro, provide convenient ways
682 to modify a list which is stored in a variable.
684 @defmac push newelt listname
685 This macro provides an alternative way to write
686 @code{(setq @var{listname} (cons @var{newelt} @var{listname}))}.
698 For the @code{pop} macro, which removes the first element from a list,
699 @xref{List Elements}.
702 Two functions modify lists that are the values of variables.
704 @defun add-to-list symbol element &optional append compare-fn
705 This function sets the variable @var{symbol} by consing @var{element}
706 onto the old value, if @var{element} is not already a member of that
707 value. It returns the resulting list, whether updated or not. The
708 value of @var{symbol} had better be a list already before the call.
709 @code{add-to-list} uses @var{compare-fn} to compare @var{element}
710 against existing list members; if @var{compare-fn} is @code{nil}, it
713 Normally, if @var{element} is added, it is added to the front of
714 @var{symbol}, but if the optional argument @var{append} is
715 non-@code{nil}, it is added at the end.
717 The argument @var{symbol} is not implicitly quoted; @code{add-to-list}
718 is an ordinary function, like @code{set} and unlike @code{setq}. Quote
719 the argument yourself if that is what you want.
722 Here's a scenario showing how to use @code{add-to-list}:
728 (add-to-list 'foo 'c) ;; @r{Add @code{c}.}
731 (add-to-list 'foo 'b) ;; @r{No effect.}
734 foo ;; @r{@code{foo} was changed.}
738 An equivalent expression for @code{(add-to-list '@var{var}
739 @var{value})} is this:
742 (or (member @var{value} @var{var})
743 (setq @var{var} (cons @var{value} @var{var})))
746 @defun add-to-ordered-list symbol element &optional order
747 This function sets the variable @var{symbol} by inserting
748 @var{element} into the old value, which must be a list, at the
749 position specified by @var{order}. If @var{element} is already a
750 member of the list, its position in the list is adjusted according
751 to @var{order}. Membership is tested using @code{eq}.
752 This function returns the resulting list, whether updated or not.
754 The @var{order} is typically a number (integer or float), and the
755 elements of the list are sorted in non-decreasing numerical order.
757 @var{order} may also be omitted or @code{nil}. Then the numeric order
758 of @var{element} stays unchanged if it already has one; otherwise,
759 @var{element} has no numeric order. Elements without a numeric list
760 order are placed at the end of the list, in no particular order.
762 Any other value for @var{order} removes the numeric order of @var{element}
763 if it already has one; otherwise, it is equivalent to @code{nil}.
765 The argument @var{symbol} is not implicitly quoted;
766 @code{add-to-ordered-list} is an ordinary function, like @code{set}
767 and unlike @code{setq}. Quote the argument yourself if that is what
770 The ordering information is stored in a hash table on @var{symbol}'s
771 @code{list-order} property.
774 Here's a scenario showing how to use @code{add-to-ordered-list}:
780 (add-to-ordered-list 'foo 'a 1) ;; @r{Add @code{a}.}
783 (add-to-ordered-list 'foo 'c 3) ;; @r{Add @code{c}.}
786 (add-to-ordered-list 'foo 'b 2) ;; @r{Add @code{b}.}
789 (add-to-ordered-list 'foo 'b 4) ;; @r{Move @code{b}.}
792 (add-to-ordered-list 'foo 'd) ;; @r{Append @code{d}.}
795 (add-to-ordered-list 'foo 'e) ;; @r{Add @code{e}}.
796 @result{} (a c b e d)
798 foo ;; @r{@code{foo} was changed.}
799 @result{} (a c b e d)
802 @node Modifying Lists
803 @section Modifying Existing List Structure
804 @cindex destructive list operations
806 You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the
807 primitives @code{setcar} and @code{setcdr}. We call these ``destructive''
808 operations because they change existing list structure.
810 @cindex CL note---@code{rplaca} vs @code{setcar}
814 @b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and
815 @code{rplacd} to alter list structure; they change structure the same
816 way as @code{setcar} and @code{setcdr}, but the Common Lisp functions
817 return the cons cell while @code{setcar} and @code{setcdr} return the
818 new @sc{car} or @sc{cdr}.
822 * Setcar:: Replacing an element in a list.
823 * Setcdr:: Replacing part of the list backbone.
824 This can be used to remove or add elements.
825 * Rearrangement:: Reordering the elements in a list; combining lists.
829 @subsection Altering List Elements with @code{setcar}
831 Changing the @sc{car} of a cons cell is done with @code{setcar}. When
832 used on a list, @code{setcar} replaces one element of a list with a
835 @defun setcar cons object
836 This function stores @var{object} as the new @sc{car} of @var{cons},
837 replacing its previous @sc{car}. In other words, it changes the
838 @sc{car} slot of @var{cons} to refer to @var{object}. It returns the
839 value @var{object}. For example:
857 When a cons cell is part of the shared structure of several lists,
858 storing a new @sc{car} into the cons changes one element of each of
859 these lists. Here is an example:
863 ;; @r{Create two lists that are partly shared.}
866 (setq x2 (cons 'z (cdr x1)))
871 ;; @r{Replace the @sc{car} of a shared link.}
872 (setcar (cdr x1) 'foo)
874 x1 ; @r{Both lists are changed.}
881 ;; @r{Replace the @sc{car} of a link that is not shared.}
884 x1 ; @r{Only one list is changed.}
885 @result{} (baz foo c)
891 Here is a graphical depiction of the shared structure of the two lists
892 in the variables @code{x1} and @code{x2}, showing why replacing @code{b}
897 --- --- --- --- --- ---
898 x1---> | | |----> | | |--> | | |--> nil
899 --- --- --- --- --- ---
913 Here is an alternative form of box diagram, showing the same relationship:
918 -------------- -------------- --------------
919 | car | cdr | | car | cdr | | car | cdr |
920 | a | o------->| b | o------->| c | nil |
922 -------------- | -------------- --------------
934 @subsection Altering the CDR of a List
936 The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}:
938 @defun setcdr cons object
939 This function stores @var{object} as the new @sc{cdr} of @var{cons},
940 replacing its previous @sc{cdr}. In other words, it changes the
941 @sc{cdr} slot of @var{cons} to refer to @var{object}. It returns the
945 Here is an example of replacing the @sc{cdr} of a list with a
946 different list. All but the first element of the list are removed in
947 favor of a different sequence of elements. The first element is
948 unchanged, because it resides in the @sc{car} of the list, and is not
949 reached via the @sc{cdr}.
966 You can delete elements from the middle of a list by altering the
967 @sc{cdr}s of the cons cells in the list. For example, here we delete
968 the second element, @code{b}, from the list @code{(a b c)}, by changing
969 the @sc{cdr} of the first cons cell:
975 (setcdr x1 (cdr (cdr x1)))
982 Here is the result in box notation:
988 -------------- | -------------- | --------------
989 | car | cdr | | | car | cdr | -->| car | cdr |
990 | a | o----- | b | o-------->| c | nil |
992 -------------- -------------- --------------
997 The second cons cell, which previously held the element @code{b}, still
998 exists and its @sc{car} is still @code{b}, but it no longer forms part
1001 It is equally easy to insert a new element by changing @sc{cdr}s:
1007 (setcdr x1 (cons 'd (cdr x1)))
1014 Here is this result in box notation:
1018 -------------- ------------- -------------
1019 | car | cdr | | car | cdr | | car | cdr |
1020 | a | o | -->| b | o------->| c | nil |
1021 | | | | | | | | | | |
1022 --------- | -- | ------------- -------------
1035 @subsection Functions that Rearrange Lists
1036 @cindex rearrangement of lists
1037 @cindex modification of lists
1039 Here are some functions that rearrange lists ``destructively'' by
1040 modifying the @sc{cdr}s of their component cons cells. We call these
1041 functions ``destructive'' because they chew up the original lists passed
1042 to them as arguments, relinking their cons cells to form a new list that
1043 is the returned value.
1046 See @code{delq}, in @ref{Sets And Lists}, for another function
1047 that modifies cons cells.
1050 The function @code{delq} in the following section is another example
1051 of destructive list manipulation.
1054 @defun nconc &rest lists
1055 @cindex concatenating lists
1056 @cindex joining lists
1057 This function returns a list containing all the elements of @var{lists}.
1058 Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are
1059 @emph{not} copied. Instead, the last @sc{cdr} of each of the
1060 @var{lists} is changed to refer to the following list. The last of the
1061 @var{lists} is not altered. For example:
1070 @result{} (1 2 3 4 5)
1074 @result{} (1 2 3 4 5)
1078 Since the last argument of @code{nconc} is not itself modified, it is
1079 reasonable to use a constant list, such as @code{'(4 5)}, as in the
1080 above example. For the same reason, the last argument need not be a
1090 @result{} (1 2 3 . z)
1094 @result{} (1 2 3 . z)
1098 However, the other arguments (all but the last) must be lists.
1100 A common pitfall is to use a quoted constant list as a non-last
1101 argument to @code{nconc}. If you do this, your program will change
1102 each time you run it! Here is what happens:
1106 (defun add-foo (x) ; @r{We want this function to add}
1107 (nconc '(foo) x)) ; @r{@code{foo} to the front of its arg.}
1111 (symbol-function 'add-foo)
1112 @result{} (lambda (x) (nconc (quote (foo)) x))
1116 (setq xx (add-foo '(1 2))) ; @r{It seems to work.}
1120 (setq xy (add-foo '(3 4))) ; @r{What happened?}
1121 @result{} (foo 1 2 3 4)
1129 (symbol-function 'add-foo)
1130 @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x)))
1135 @defun nreverse list
1136 @cindex reversing a list
1137 This function reverses the order of the elements of @var{list}.
1138 Unlike @code{reverse}, @code{nreverse} alters its argument by reversing
1139 the @sc{cdr}s in the cons cells forming the list. The cons cell that
1140 used to be the last one in @var{list} becomes the first cons cell of the
1157 ;; @r{The cons cell that was first is now last.}
1163 To avoid confusion, we usually store the result of @code{nreverse}
1164 back in the same variable which held the original list:
1167 (setq x (nreverse x))
1170 Here is the @code{nreverse} of our favorite example, @code{(a b c)},
1171 presented graphically:
1175 @r{Original list head:} @r{Reversed list:}
1176 ------------- ------------- ------------
1177 | car | cdr | | car | cdr | | car | cdr |
1178 | a | nil |<-- | b | o |<-- | c | o |
1179 | | | | | | | | | | | | |
1180 ------------- | --------- | - | -------- | -
1182 ------------- ------------
1187 @defun sort list predicate
1189 @cindex sorting lists
1190 This function sorts @var{list} stably, though destructively, and
1191 returns the sorted list. It compares elements using @var{predicate}. A
1192 stable sort is one in which elements with equal sort keys maintain their
1193 relative order before and after the sort. Stability is important when
1194 successive sorts are used to order elements according to different
1197 The argument @var{predicate} must be a function that accepts two
1198 arguments. It is called with two elements of @var{list}. To get an
1199 increasing order sort, the @var{predicate} should return non-@code{nil} if the
1200 first element is ``less than'' the second, or @code{nil} if not.
1202 The comparison function @var{predicate} must give reliable results for
1203 any given pair of arguments, at least within a single call to
1204 @code{sort}. It must be @dfn{antisymmetric}; that is, if @var{a} is
1205 less than @var{b}, @var{b} must not be less than @var{a}. It must be
1206 @dfn{transitive}---that is, if @var{a} is less than @var{b}, and @var{b}
1207 is less than @var{c}, then @var{a} must be less than @var{c}. If you
1208 use a comparison function which does not meet these requirements, the
1209 result of @code{sort} is unpredictable.
1211 The destructive aspect of @code{sort} is that it rearranges the cons
1212 cells forming @var{list} by changing @sc{cdr}s. A nondestructive sort
1213 function would create new cons cells to store the elements in their
1214 sorted order. If you wish to make a sorted copy without destroying the
1215 original, copy it first with @code{copy-sequence} and then sort.
1217 Sorting does not change the @sc{car}s of the cons cells in @var{list};
1218 the cons cell that originally contained the element @code{a} in
1219 @var{list} still has @code{a} in its @sc{car} after sorting, but it now
1220 appears in a different position in the list due to the change of
1221 @sc{cdr}s. For example:
1225 (setq nums '(1 3 2 6 5 4 0))
1226 @result{} (1 3 2 6 5 4 0)
1230 @result{} (0 1 2 3 4 5 6)
1234 @result{} (1 2 3 4 5 6)
1239 @strong{Warning}: Note that the list in @code{nums} no longer contains
1240 0; this is the same cons cell that it was before, but it is no longer
1241 the first one in the list. Don't assume a variable that formerly held
1242 the argument now holds the entire sorted list! Instead, save the result
1243 of @code{sort} and use that. Most often we store the result back into
1244 the variable that held the original list:
1247 (setq nums (sort nums '<))
1250 @xref{Sorting}, for more functions that perform sorting.
1251 See @code{documentation} in @ref{Accessing Documentation}, for a
1252 useful example of @code{sort}.
1255 @node Sets And Lists
1256 @section Using Lists as Sets
1257 @cindex lists as sets
1260 A list can represent an unordered mathematical set---simply consider a
1261 value an element of a set if it appears in the list, and ignore the
1262 order of the list. To form the union of two sets, use @code{append} (as
1263 long as you don't mind having duplicate elements). You can remove
1264 @code{equal} duplicates using @code{delete-dups}. Other useful
1265 functions for sets include @code{memq} and @code{delq}, and their
1266 @code{equal} versions, @code{member} and @code{delete}.
1268 @cindex CL note---lack @code{union}, @code{intersection}
1270 @b{Common Lisp note:} Common Lisp has functions @code{union} (which
1271 avoids duplicate elements) and @code{intersection} for set operations.
1272 Although standard GNU Emacs Lisp does not have them, the @file{cl}
1273 library provides versions. @inforef{Top, Overview, cl}.
1276 @defun memq object list
1277 @cindex membership in a list
1278 This function tests to see whether @var{object} is a member of
1279 @var{list}. If it is, @code{memq} returns a list starting with the
1280 first occurrence of @var{object}. Otherwise, it returns @code{nil}.
1281 The letter @samp{q} in @code{memq} says that it uses @code{eq} to
1282 compare @var{object} against the elements of the list. For example:
1286 (memq 'b '(a b c b a))
1290 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1296 @defun delq object list
1297 @cindex deleting list elements
1298 This function destructively removes all elements @code{eq} to
1299 @var{object} from @var{list}. The letter @samp{q} in @code{delq} says
1300 that it uses @code{eq} to compare @var{object} against the elements of
1301 the list, like @code{memq} and @code{remq}.
1304 When @code{delq} deletes elements from the front of the list, it does so
1305 simply by advancing down the list and returning a sublist that starts
1306 after those elements:
1310 (delq 'a '(a b c)) @equiv{} (cdr '(a b c))
1314 When an element to be deleted appears in the middle of the list,
1315 removing it involves changing the @sc{cdr}s (@pxref{Setcdr}).
1319 (setq sample-list '(a b c (4)))
1320 @result{} (a b c (4))
1323 (delq 'a sample-list)
1328 @result{} (a b c (4))
1331 (delq 'c sample-list)
1340 Note that @code{(delq 'c sample-list)} modifies @code{sample-list} to
1341 splice out the third element, but @code{(delq 'a sample-list)} does not
1342 splice anything---it just returns a shorter list. Don't assume that a
1343 variable which formerly held the argument @var{list} now has fewer
1344 elements, or that it still holds the original list! Instead, save the
1345 result of @code{delq} and use that. Most often we store the result back
1346 into the variable that held the original list:
1349 (setq flowers (delq 'rose flowers))
1352 In the following example, the @code{(4)} that @code{delq} attempts to match
1353 and the @code{(4)} in the @code{sample-list} are not @code{eq}:
1357 (delq '(4) sample-list)
1362 If you want to delete elements that are @code{equal} to a given value,
1363 use @code{delete} (see below).
1365 @defun remq object list
1366 This function returns a copy of @var{list}, with all elements removed
1367 which are @code{eq} to @var{object}. The letter @samp{q} in @code{remq}
1368 says that it uses @code{eq} to compare @var{object} against the elements
1373 (setq sample-list '(a b c a b c))
1374 @result{} (a b c a b c)
1377 (remq 'a sample-list)
1382 @result{} (a b c a b c)
1387 @defun memql object list
1388 The function @code{memql} tests to see whether @var{object} is a member
1389 of @var{list}, comparing members with @var{object} using @code{eql},
1390 so floating point elements are compared by value.
1391 If @var{object} is a member, @code{memql} returns a list starting with
1392 its first occurrence in @var{list}. Otherwise, it returns @code{nil}.
1394 Compare this with @code{memq}:
1398 (memql 1.2 '(1.1 1.2 1.3)) ; @r{@code{1.2} and @code{1.2} are @code{eql}.}
1402 (memq 1.2 '(1.1 1.2 1.3)) ; @r{@code{1.2} and @code{1.2} are not @code{eq}.}
1408 The following three functions are like @code{memq}, @code{delq} and
1409 @code{remq}, but use @code{equal} rather than @code{eq} to compare
1410 elements. @xref{Equality Predicates}.
1412 @defun member object list
1413 The function @code{member} tests to see whether @var{object} is a member
1414 of @var{list}, comparing members with @var{object} using @code{equal}.
1415 If @var{object} is a member, @code{member} returns a list starting with
1416 its first occurrence in @var{list}. Otherwise, it returns @code{nil}.
1418 Compare this with @code{memq}:
1422 (member '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are @code{equal}.}
1426 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1430 ;; @r{Two strings with the same contents are @code{equal}.}
1431 (member "foo" '("foo" "bar"))
1432 @result{} ("foo" "bar")
1437 @defun delete object sequence
1438 If @code{sequence} is a list, this function destructively removes all
1439 elements @code{equal} to @var{object} from @var{sequence}. For lists,
1440 @code{delete} is to @code{delq} as @code{member} is to @code{memq}: it
1441 uses @code{equal} to compare elements with @var{object}, like
1442 @code{member}; when it finds an element that matches, it cuts the
1443 element out just as @code{delq} would.
1445 If @code{sequence} is a vector or string, @code{delete} returns a copy
1446 of @code{sequence} with all elements @code{equal} to @code{object}
1453 (setq l '((2) (1) (2)))
1458 ;; @r{If you want to change @code{l} reliably,}
1459 ;; @r{write @code{(setq l (delete '(2) l))}.}
1462 (setq l '((2) (1) (2)))
1467 ;; @r{In this case, it makes no difference whether you set @code{l},}
1468 ;; @r{but you should do so for the sake of the other case.}
1471 (delete '(2) [(2) (1) (2)])
1477 @defun remove object sequence
1478 This function is the non-destructive counterpart of @code{delete}. It
1479 returns a copy of @code{sequence}, a list, vector, or string, with
1480 elements @code{equal} to @code{object} removed. For example:
1484 (remove '(2) '((2) (1) (2)))
1488 (remove '(2) [(2) (1) (2)])
1495 @b{Common Lisp note:} The functions @code{member}, @code{delete} and
1496 @code{remove} in GNU Emacs Lisp are derived from Maclisp, not Common
1497 Lisp. The Common Lisp versions do not use @code{equal} to compare
1501 @defun member-ignore-case object list
1502 This function is like @code{member}, except that @var{object} should
1503 be a string and that it ignores differences in letter-case and text
1504 representation: upper-case and lower-case letters are treated as
1505 equal, and unibyte strings are converted to multibyte prior to
1509 @defun delete-dups list
1510 This function destructively removes all @code{equal} duplicates from
1511 @var{list}, stores the result in @var{list} and returns it. Of
1512 several @code{equal} occurrences of an element in @var{list},
1513 @code{delete-dups} keeps the first one.
1516 See also the function @code{add-to-list}, in @ref{List Variables},
1517 for a way to add an element to a list stored in a variable and used as a
1520 @node Association Lists
1521 @section Association Lists
1522 @cindex association list
1525 An @dfn{association list}, or @dfn{alist} for short, records a mapping
1526 from keys to values. It is a list of cons cells called
1527 @dfn{associations}: the @sc{car} of each cons cell is the @dfn{key}, and the
1528 @sc{cdr} is the @dfn{associated value}.@footnote{This usage of ``key''
1529 is not related to the term ``key sequence''; it means a value used to
1530 look up an item in a table. In this case, the table is the alist, and
1531 the alist associations are the items.}
1533 Here is an example of an alist. The key @code{pine} is associated with
1534 the value @code{cones}; the key @code{oak} is associated with
1535 @code{acorns}; and the key @code{maple} is associated with @code{seeds}.
1545 Both the values and the keys in an alist may be any Lisp objects.
1546 For example, in the following alist, the symbol @code{a} is
1547 associated with the number @code{1}, and the string @code{"b"} is
1548 associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of
1555 Sometimes it is better to design an alist to store the associated
1556 value in the @sc{car} of the @sc{cdr} of the element. Here is an
1557 example of such an alist:
1560 ((rose red) (lily white) (buttercup yellow))
1564 Here we regard @code{red} as the value associated with @code{rose}. One
1565 advantage of this kind of alist is that you can store other related
1566 information---even a list of other items---in the @sc{cdr} of the
1567 @sc{cdr}. One disadvantage is that you cannot use @code{rassq} (see
1568 below) to find the element containing a given value. When neither of
1569 these considerations is important, the choice is a matter of taste, as
1570 long as you are consistent about it for any given alist.
1572 The same alist shown above could be regarded as having the
1573 associated value in the @sc{cdr} of the element; the value associated
1574 with @code{rose} would be the list @code{(red)}.
1576 Association lists are often used to record information that you might
1577 otherwise keep on a stack, since new associations may be added easily to
1578 the front of the list. When searching an association list for an
1579 association with a given key, the first one found is returned, if there
1582 In Emacs Lisp, it is @emph{not} an error if an element of an
1583 association list is not a cons cell. The alist search functions simply
1584 ignore such elements. Many other versions of Lisp signal errors in such
1587 Note that property lists are similar to association lists in several
1588 respects. A property list behaves like an association list in which
1589 each key can occur only once. @xref{Property Lists}, for a comparison
1590 of property lists and association lists.
1592 @defun assoc key alist
1593 This function returns the first association for @var{key} in
1594 @var{alist}, comparing @var{key} against the alist elements using
1595 @code{equal} (@pxref{Equality Predicates}). It returns @code{nil} if no
1596 association in @var{alist} has a @sc{car} @code{equal} to @var{key}.
1600 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1601 @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1603 @result{} (oak . acorns)
1604 (cdr (assoc 'oak trees))
1606 (assoc 'birch trees)
1610 Here is another example, in which the keys and values are not symbols:
1613 (setq needles-per-cluster
1614 '((2 "Austrian Pine" "Red Pine")
1618 (cdr (assoc 3 needles-per-cluster))
1619 @result{} ("Pitch Pine")
1620 (cdr (assoc 2 needles-per-cluster))
1621 @result{} ("Austrian Pine" "Red Pine")
1625 The function @code{assoc-string} is much like @code{assoc} except
1626 that it ignores certain differences between strings. @xref{Text
1629 @defun rassoc value alist
1630 This function returns the first association with value @var{value} in
1631 @var{alist}. It returns @code{nil} if no association in @var{alist} has
1632 a @sc{cdr} @code{equal} to @var{value}.
1634 @code{rassoc} is like @code{assoc} except that it compares the @sc{cdr} of
1635 each @var{alist} association instead of the @sc{car}. You can think of
1636 this as ``reverse @code{assoc}'', finding the key for a given value.
1639 @defun assq key alist
1640 This function is like @code{assoc} in that it returns the first
1641 association for @var{key} in @var{alist}, but it makes the comparison
1642 using @code{eq} instead of @code{equal}. @code{assq} returns @code{nil}
1643 if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}.
1644 This function is used more often than @code{assoc}, since @code{eq} is
1645 faster than @code{equal} and most alists use symbols as keys.
1646 @xref{Equality Predicates}.
1649 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1650 @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1652 @result{} (pine . cones)
1655 On the other hand, @code{assq} is not usually useful in alists where the
1656 keys may not be symbols:
1660 '(("simple leaves" . oak)
1661 ("compound leaves" . horsechestnut)))
1663 (assq "simple leaves" leaves)
1665 (assoc "simple leaves" leaves)
1666 @result{} ("simple leaves" . oak)
1670 @defun rassq value alist
1671 This function returns the first association with value @var{value} in
1672 @var{alist}. It returns @code{nil} if no association in @var{alist} has
1673 a @sc{cdr} @code{eq} to @var{value}.
1675 @code{rassq} is like @code{assq} except that it compares the @sc{cdr} of
1676 each @var{alist} association instead of the @sc{car}. You can think of
1677 this as ``reverse @code{assq}'', finding the key for a given value.
1682 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1684 (rassq 'acorns trees)
1685 @result{} (oak . acorns)
1686 (rassq 'spores trees)
1690 @code{rassq} cannot search for a value stored in the @sc{car}
1691 of the @sc{cdr} of an element:
1694 (setq colors '((rose red) (lily white) (buttercup yellow)))
1696 (rassq 'white colors)
1700 In this case, the @sc{cdr} of the association @code{(lily white)} is not
1701 the symbol @code{white}, but rather the list @code{(white)}. This
1702 becomes clearer if the association is written in dotted pair notation:
1705 (lily white) @equiv{} (lily . (white))
1709 @defun assoc-default key alist &optional test default
1710 This function searches @var{alist} for a match for @var{key}. For each
1711 element of @var{alist}, it compares the element (if it is an atom) or
1712 the element's @sc{car} (if it is a cons) against @var{key}, by calling
1713 @var{test} with two arguments: the element or its @sc{car}, and
1714 @var{key}. The arguments are passed in that order so that you can get
1715 useful results using @code{string-match} with an alist that contains
1716 regular expressions (@pxref{Regexp Search}). If @var{test} is omitted
1717 or @code{nil}, @code{equal} is used for comparison.
1719 If an alist element matches @var{key} by this criterion,
1720 then @code{assoc-default} returns a value based on this element.
1721 If the element is a cons, then the value is the element's @sc{cdr}.
1722 Otherwise, the return value is @var{default}.
1724 If no alist element matches @var{key}, @code{assoc-default} returns
1728 @defun copy-alist alist
1729 @cindex copying alists
1730 This function returns a two-level deep copy of @var{alist}: it creates a
1731 new copy of each association, so that you can alter the associations of
1732 the new alist without changing the old one.
1736 (setq needles-per-cluster
1737 '((2 . ("Austrian Pine" "Red Pine"))
1738 (3 . ("Pitch Pine"))
1740 (5 . ("White Pine"))))
1742 ((2 "Austrian Pine" "Red Pine")
1746 (setq copy (copy-alist needles-per-cluster))
1748 ((2 "Austrian Pine" "Red Pine")
1752 (eq needles-per-cluster copy)
1754 (equal needles-per-cluster copy)
1756 (eq (car needles-per-cluster) (car copy))
1758 (cdr (car (cdr needles-per-cluster)))
1759 @result{} ("Pitch Pine")
1761 (eq (cdr (car (cdr needles-per-cluster)))
1762 (cdr (car (cdr copy))))
1767 This example shows how @code{copy-alist} makes it possible to change
1768 the associations of one copy without affecting the other:
1772 (setcdr (assq 3 copy) '("Martian Vacuum Pine"))
1773 (cdr (assq 3 needles-per-cluster))
1774 @result{} ("Pitch Pine")
1779 @defun assq-delete-all key alist
1780 This function deletes from @var{alist} all the elements whose @sc{car}
1781 is @code{eq} to @var{key}, much as if you used @code{delq} to delete
1782 each such element one by one. It returns the shortened alist, and
1783 often modifies the original list structure of @var{alist}. For
1784 correct results, use the return value of @code{assq-delete-all} rather
1785 than looking at the saved value of @var{alist}.
1788 (setq alist '((foo 1) (bar 2) (foo 3) (lose 4)))
1789 @result{} ((foo 1) (bar 2) (foo 3) (lose 4))
1790 (assq-delete-all 'foo alist)
1791 @result{} ((bar 2) (lose 4))
1793 @result{} ((foo 1) (bar 2) (lose 4))
1797 @defun rassq-delete-all value alist
1798 This function deletes from @var{alist} all the elements whose @sc{cdr}
1799 is @code{eq} to @var{value}. It returns the shortened alist, and
1800 often modifies the original list structure of @var{alist}.
1801 @code{rassq-delete-all} is like @code{assq-delete-all} except that it
1802 compares the @sc{cdr} of each @var{alist} association instead of the