2 @c This is part of the GNU Emacs Lisp Reference Manual.
3 @c Copyright (C) 1990-1995, 1998-1999, 2001-2011 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.
26 * Rings:: Managing a fixed-size ring of objects.
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}. A cons cell is a data object that represents an
35 ordered pair. That is, it has two slots, and each slot @dfn{holds}, or
36 @dfn{refers to}, some Lisp object. One slot is known as the @sc{car},
37 and the other is known as the @sc{cdr}. (These names are traditional;
38 see @ref{Cons Cell Type}.) @sc{cdr} is 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 of
45 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: the
47 @sc{cdr} slot of each cons cell refers to the following cons cell. The
48 @sc{cdr} of the last cons cell is @code{nil}. This asymmetry between
49 the @sc{car} and the @sc{cdr} is entirely a matter of convention; at the
50 level of cons cells, the @sc{car} and @sc{cdr} slots have the same
54 Since @code{nil} is the conventional value to put in the @sc{cdr} of
55 the last cons cell in the list, we call that case a @dfn{true list}.
57 In Lisp, we consider the symbol @code{nil} a list as well as a
58 symbol; it is the list with no elements. For convenience, the symbol
59 @code{nil} is considered to have @code{nil} as its @sc{cdr} (and also
60 as its @sc{car}). Therefore, the @sc{cdr} of a true list is always a
65 If the @sc{cdr} of a list's last cons cell is some other value,
66 neither @code{nil} nor another cons cell, we call the structure a
67 @dfn{dotted list}, since its printed representation would use
68 @samp{.}. There is one other possibility: some cons cell's @sc{cdr}
69 could point to one of the previous cons cells in the list. We call
70 that structure a @dfn{circular list}.
72 For some purposes, it does not matter whether a list is true,
73 circular or dotted. If the program doesn't look far enough down the
74 list to see the @sc{cdr} of the final cons cell, it won't care.
75 However, some functions that operate on lists demand true lists and
76 signal errors if given a dotted list. Most functions that try to find
77 the end of a list enter infinite loops if given a circular list.
79 @cindex list structure
80 Because most cons cells are used as part of lists, the phrase
81 @dfn{list structure} has come to mean any structure made out of cons
84 The @sc{cdr} of any nonempty true list @var{l} is a list containing all the
85 elements of @var{l} except the first.
87 @xref{Cons Cell Type}, for the read and print syntax of cons cells and
88 lists, and for ``box and arrow'' illustrations of lists.
90 @node List-related Predicates
91 @section Predicates on Lists
93 The following predicates test whether a Lisp object is an atom,
94 whether it is a cons cell or is a list, or whether it is the
95 distinguished object @code{nil}. (Many of these predicates can be
96 defined in terms of the others, but they are used so often that it is
97 worth having all of them.)
100 This function returns @code{t} if @var{object} is a cons cell, @code{nil}
101 otherwise. @code{nil} is not a cons cell, although it @emph{is} a list.
105 This function returns @code{t} if @var{object} is an atom, @code{nil}
106 otherwise. All objects except cons cells are atoms. The symbol
107 @code{nil} is an atom and is also a list; it is the only Lisp object
111 (atom @var{object}) @equiv{} (not (consp @var{object}))
116 This function returns @code{t} if @var{object} is a cons cell or
117 @code{nil}. Otherwise, it returns @code{nil}.
132 This function is the opposite of @code{listp}: it returns @code{t} if
133 @var{object} is not a list. Otherwise, it returns @code{nil}.
136 (listp @var{object}) @equiv{} (not (nlistp @var{object}))
141 This function returns @code{t} if @var{object} is @code{nil}, and
142 returns @code{nil} otherwise. This function is identical to @code{not},
143 but as a matter of clarity we use @code{null} when @var{object} is
144 considered a list and @code{not} when it is considered a truth value
145 (see @code{not} in @ref{Combining Conditions}).
161 @section Accessing Elements of Lists
162 @cindex list elements
165 This function returns the value referred to by the first slot of the
166 cons cell @var{cons-cell}. In other words, it returns the @sc{car} of
169 As a special case, if @var{cons-cell} is @code{nil}, this function
170 returns @code{nil}. Therefore, any list is a valid argument. An
171 error is signaled if the argument is not a cons cell or @code{nil}.
186 This function returns the value referred to by the second slot of the
187 cons cell @var{cons-cell}. In other words, it returns the @sc{cdr} of
190 As a special case, if @var{cons-cell} is @code{nil}, this function
191 returns @code{nil}; therefore, any list is a valid argument. An error
192 is signaled if the argument is not a cons cell or @code{nil}.
206 @defun car-safe object
207 This function lets you take the @sc{car} of a cons cell while avoiding
208 errors for other data types. It returns the @sc{car} of @var{object} if
209 @var{object} is a cons cell, @code{nil} otherwise. This is in contrast
210 to @code{car}, which signals an error if @var{object} is not a list.
214 (car-safe @var{object})
216 (let ((x @var{object}))
224 @defun cdr-safe object
225 This function lets you take the @sc{cdr} of a cons cell while
226 avoiding errors for other data types. It returns the @sc{cdr} of
227 @var{object} if @var{object} is a cons cell, @code{nil} otherwise.
228 This is in contrast to @code{cdr}, which signals an error if
229 @var{object} is not a list.
233 (cdr-safe @var{object})
235 (let ((x @var{object}))
244 This macro is a way of examining the @sc{car} of a list,
245 and taking it off the list, all at once.
247 It operates on the list which is stored in the symbol @var{listname}.
248 It removes this element from the list by setting @var{listname}
249 to the @sc{cdr} of its old value---but it also returns the @sc{car}
250 of that list, which is the element being removed.
263 @anchor{Definition of nth}
264 This function returns the @var{n}th element of @var{list}. Elements
265 are numbered starting with zero, so the @sc{car} of @var{list} is
266 element number zero. If the length of @var{list} is @var{n} or less,
267 the value is @code{nil}.
269 If @var{n} is negative, @code{nth} returns the first element of
285 (nth n x) @equiv{} (car (nthcdr n x))
289 The function @code{elt} is similar, but applies to any kind of sequence.
290 For historical reasons, it takes its arguments in the opposite order.
291 @xref{Sequence Functions}.
295 This function returns the @var{n}th @sc{cdr} of @var{list}. In other
296 words, it skips past the first @var{n} links of @var{list} and returns
299 If @var{n} is zero or negative, @code{nthcdr} returns all of
300 @var{list}. If the length of @var{list} is @var{n} or less,
301 @code{nthcdr} returns @code{nil}.
305 (nthcdr 1 '(1 2 3 4))
309 (nthcdr 10 '(1 2 3 4))
313 (nthcdr -3 '(1 2 3 4))
319 @defun last list &optional n
320 This function returns the last link of @var{list}. The @code{car} of
321 this link is the list's last element. If @var{list} is null,
322 @code{nil} is returned. If @var{n} is non-@code{nil}, the
323 @var{n}th-to-last link is returned instead, or the whole of @var{list}
324 if @var{n} is bigger than @var{list}'s length.
327 @defun safe-length list
328 @anchor{Definition of safe-length}
329 This function returns the length of @var{list}, with no risk of either
330 an error or an infinite loop. It generally returns the number of
331 distinct cons cells in the list. However, for circular lists,
332 the value is just an upper bound; it is often too large.
334 If @var{list} is not @code{nil} or a cons cell, @code{safe-length}
338 The most common way to compute the length of a list, when you are not
339 worried that it may be circular, is with @code{length}. @xref{Sequence
342 @defun caar cons-cell
343 This is the same as @code{(car (car @var{cons-cell}))}.
346 @defun cadr cons-cell
347 This is the same as @code{(car (cdr @var{cons-cell}))}
348 or @code{(nth 1 @var{cons-cell})}.
351 @defun cdar cons-cell
352 This is the same as @code{(cdr (car @var{cons-cell}))}.
355 @defun cddr cons-cell
356 This is the same as @code{(cdr (cdr @var{cons-cell}))}
357 or @code{(nthcdr 2 @var{cons-cell})}.
360 @defun butlast x &optional n
361 This function returns the list @var{x} with the last element,
362 or the last @var{n} elements, removed. If @var{n} is greater
363 than zero it makes a copy of the list so as not to damage the
364 original list. In general, @code{(append (butlast @var{x} @var{n})
365 (last @var{x} @var{n}))} will return a list equal to @var{x}.
368 @defun nbutlast x &optional n
369 This is a version of @code{butlast} that works by destructively
370 modifying the @code{cdr} of the appropriate element, rather than
371 making a copy of the list.
375 @comment node-name, next, previous, up
376 @section Building Cons Cells and Lists
378 @cindex building lists
380 Many functions build lists, as lists reside at the very heart of Lisp.
381 @code{cons} is the fundamental list-building function; however, it is
382 interesting to note that @code{list} is used more times in the source
383 code for Emacs than @code{cons}.
385 @defun cons object1 object2
386 This function is the most basic function for building new list
387 structure. It creates a new cons cell, making @var{object1} the
388 @sc{car}, and @var{object2} the @sc{cdr}. It then returns the new
389 cons cell. The arguments @var{object1} and @var{object2} may be any
390 Lisp objects, but most often @var{object2} is a list.
408 @code{cons} is often used to add a single element to the front of a
409 list. This is called @dfn{consing the element onto the list}.
410 @footnote{There is no strictly equivalent way to add an element to
411 the end of a list. You can use @code{(append @var{listname} (list
412 @var{newelt}))}, which creates a whole new list by copying @var{listname}
413 and adding @var{newelt} to its end. Or you can use @code{(nconc
414 @var{listname} (list @var{newelt}))}, which modifies @var{listname}
415 by following all the @sc{cdr}s and then replacing the terminating
416 @code{nil}. Compare this to adding an element to the beginning of a
417 list with @code{cons}, which neither copies nor modifies the list.}
421 (setq list (cons newelt list))
424 Note that there is no conflict between the variable named @code{list}
425 used in this example and the function named @code{list} described below;
426 any symbol can serve both purposes.
429 @defun list &rest objects
430 This function creates a list with @var{objects} as its elements. The
431 resulting list is always @code{nil}-terminated. If no @var{objects}
432 are given, the empty list is returned.
437 @result{} (1 2 3 4 5)
440 (list 1 2 '(3 4 5) 'foo)
441 @result{} (1 2 (3 4 5) foo)
450 @defun make-list length object
451 This function creates a list of @var{length} elements, in which each
452 element is @var{object}. Compare @code{make-list} with
453 @code{make-string} (@pxref{Creating Strings}).
458 @result{} (pigs pigs pigs)
465 (setq l (make-list 3 '(a b))
466 @result{} ((a b) (a b) (a b))
467 (eq (car l) (cadr l))
473 @defun append &rest sequences
474 @cindex copying lists
475 This function returns a list containing all the elements of
476 @var{sequences}. The @var{sequences} may be lists, vectors,
477 bool-vectors, or strings, but the last one should usually be a list.
478 All arguments except the last one are copied, so none of the arguments
479 is altered. (See @code{nconc} in @ref{Rearrangement}, for a way to join
480 lists with no copying.)
482 More generally, the final argument to @code{append} may be any Lisp
483 object. The final argument is not copied or converted; it becomes the
484 @sc{cdr} of the last cons cell in the new list. If the final argument
485 is itself a list, then its elements become in effect elements of the
486 result list. If the final element is not a list, the result is a
487 dotted list since its final @sc{cdr} is not @code{nil} as required
491 Here is an example of using @code{append}:
495 (setq trees '(pine oak))
497 (setq more-trees (append '(maple birch) trees))
498 @result{} (maple birch pine oak)
505 @result{} (maple birch pine oak)
508 (eq trees (cdr (cdr more-trees)))
513 You can see how @code{append} works by looking at a box diagram. The
514 variable @code{trees} is set to the list @code{(pine oak)} and then the
515 variable @code{more-trees} is set to the list @code{(maple birch pine
516 oak)}. However, the variable @code{trees} continues to refer to the
523 | --- --- --- --- -> --- --- --- ---
524 --> | | |--> | | |--> | | |--> | | |--> nil
525 --- --- --- --- --- --- --- ---
528 --> maple -->birch --> pine --> oak
532 An empty sequence contributes nothing to the value returned by
533 @code{append}. As a consequence of this, a final @code{nil} argument
534 forces a copy of the previous argument:
542 (setq wood (append trees nil))
556 This once was the usual way to copy a list, before the function
557 @code{copy-sequence} was invented. @xref{Sequences Arrays Vectors}.
559 Here we show the use of vectors and strings as arguments to @code{append}:
563 (append [a b] "cd" nil)
564 @result{} (a b 99 100)
568 With the help of @code{apply} (@pxref{Calling Functions}), we can append
569 all the lists in a list of lists:
573 (apply 'append '((a b c) nil (x y z) nil))
574 @result{} (a b c x y z)
578 If no @var{sequences} are given, @code{nil} is returned:
587 Here are some examples where the final argument is not a list:
593 @result{} (x y . [z])
597 The second example shows that when the final argument is a sequence but
598 not a list, the sequence's elements do not become elements of the
599 resulting list. Instead, the sequence becomes the final @sc{cdr}, like
600 any other non-list final argument.
603 This function creates a new list whose elements are the elements of
604 @var{list}, but in reverse order. The original argument @var{list} is
621 @defun copy-tree tree &optional vecp
622 This function returns a copy of the tree @code{tree}. If @var{tree} is a
623 cons cell, this makes a new cons cell with the same @sc{car} and
624 @sc{cdr}, then recursively copies the @sc{car} and @sc{cdr} in the
627 Normally, when @var{tree} is anything other than a cons cell,
628 @code{copy-tree} simply returns @var{tree}. However, if @var{vecp} is
629 non-@code{nil}, it copies vectors too (and operates recursively on
633 @defun number-sequence from &optional to separation
634 This returns a list of numbers starting with @var{from} and
635 incrementing by @var{separation}, and ending at or just before
636 @var{to}. @var{separation} can be positive or negative and defaults
637 to 1. If @var{to} is @code{nil} or numerically equal to @var{from},
638 the value is the one-element list @code{(@var{from})}. If @var{to} is
639 less than @var{from} with a positive @var{separation}, or greater than
640 @var{from} with a negative @var{separation}, the value is @code{nil}
641 because those arguments specify an empty sequence.
643 If @var{separation} is 0 and @var{to} is neither @code{nil} nor
644 numerically equal to @var{from}, @code{number-sequence} signals an
645 error, since those arguments specify an infinite sequence.
647 All arguments can be integers or floating point numbers. However,
648 floating point arguments can be tricky, because floating point
649 arithmetic is inexact. For instance, depending on the machine, it may
650 quite well happen that @code{(number-sequence 0.4 0.6 0.2)} returns
651 the one element list @code{(0.4)}, whereas
652 @code{(number-sequence 0.4 0.8 0.2)} returns a list with three
653 elements. The @var{n}th element of the list is computed by the exact
654 formula @code{(+ @var{from} (* @var{n} @var{separation}))}. Thus, if
655 one wants to make sure that @var{to} is included in the list, one can
656 pass an expression of this exact type for @var{to}. Alternatively,
657 one can replace @var{to} with a slightly larger value (or a slightly
658 more negative value if @var{separation} is negative).
663 (number-sequence 4 9)
664 @result{} (4 5 6 7 8 9)
665 (number-sequence 9 4 -1)
666 @result{} (9 8 7 6 5 4)
667 (number-sequence 9 4 -2)
671 (number-sequence 8 5)
673 (number-sequence 5 8 -1)
675 (number-sequence 1.5 6 2)
676 @result{} (1.5 3.5 5.5)
681 @section Modifying List Variables
683 These functions, and one macro, provide convenient ways
684 to modify a list which is stored in a variable.
686 @defmac push newelt listname
687 This macro provides an alternative way to write
688 @code{(setq @var{listname} (cons @var{newelt} @var{listname}))}.
700 Two functions modify lists that are the values of variables.
702 @defun add-to-list symbol element &optional append compare-fn
703 This function sets the variable @var{symbol} by consing @var{element}
704 onto the old value, if @var{element} is not already a member of that
705 value. It returns the resulting list, whether updated or not. The
706 value of @var{symbol} had better be a list already before the call.
707 @code{add-to-list} uses @var{compare-fn} to compare @var{element}
708 against existing list members; if @var{compare-fn} is @code{nil}, it
711 Normally, if @var{element} is added, it is added to the front of
712 @var{symbol}, but if the optional argument @var{append} is
713 non-@code{nil}, it is added at the end.
715 The argument @var{symbol} is not implicitly quoted; @code{add-to-list}
716 is an ordinary function, like @code{set} and unlike @code{setq}. Quote
717 the argument yourself if that is what you want.
720 Here's a scenario showing how to use @code{add-to-list}:
726 (add-to-list 'foo 'c) ;; @r{Add @code{c}.}
729 (add-to-list 'foo 'b) ;; @r{No effect.}
732 foo ;; @r{@code{foo} was changed.}
736 An equivalent expression for @code{(add-to-list '@var{var}
737 @var{value})} is this:
740 (or (member @var{value} @var{var})
741 (setq @var{var} (cons @var{value} @var{var})))
744 @defun add-to-ordered-list symbol element &optional order
745 This function sets the variable @var{symbol} by inserting
746 @var{element} into the old value, which must be a list, at the
747 position specified by @var{order}. If @var{element} is already a
748 member of the list, its position in the list is adjusted according
749 to @var{order}. Membership is tested using @code{eq}.
750 This function returns the resulting list, whether updated or not.
752 The @var{order} is typically a number (integer or float), and the
753 elements of the list are sorted in non-decreasing numerical order.
755 @var{order} may also be omitted or @code{nil}. Then the numeric order
756 of @var{element} stays unchanged if it already has one; otherwise,
757 @var{element} has no numeric order. Elements without a numeric list
758 order are placed at the end of the list, in no particular order.
760 Any other value for @var{order} removes the numeric order of @var{element}
761 if it already has one; otherwise, it is equivalent to @code{nil}.
763 The argument @var{symbol} is not implicitly quoted;
764 @code{add-to-ordered-list} is an ordinary function, like @code{set}
765 and unlike @code{setq}. Quote the argument yourself if that is what
768 The ordering information is stored in a hash table on @var{symbol}'s
769 @code{list-order} property.
772 Here's a scenario showing how to use @code{add-to-ordered-list}:
778 (add-to-ordered-list 'foo 'a 1) ;; @r{Add @code{a}.}
781 (add-to-ordered-list 'foo 'c 3) ;; @r{Add @code{c}.}
784 (add-to-ordered-list 'foo 'b 2) ;; @r{Add @code{b}.}
787 (add-to-ordered-list 'foo 'b 4) ;; @r{Move @code{b}.}
790 (add-to-ordered-list 'foo 'd) ;; @r{Append @code{d}.}
793 (add-to-ordered-list 'foo 'e) ;; @r{Add @code{e}}.
794 @result{} (a c b e d)
796 foo ;; @r{@code{foo} was changed.}
797 @result{} (a c b e d)
800 @node Modifying Lists
801 @section Modifying Existing List Structure
802 @cindex destructive list operations
804 You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the
805 primitives @code{setcar} and @code{setcdr}. We call these ``destructive''
806 operations because they change existing list structure.
808 @cindex CL note---@code{rplaca} vs @code{setcar}
812 @b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and
813 @code{rplacd} to alter list structure; they change structure the same
814 way as @code{setcar} and @code{setcdr}, but the Common Lisp functions
815 return the cons cell while @code{setcar} and @code{setcdr} return the
816 new @sc{car} or @sc{cdr}.
820 * Setcar:: Replacing an element in a list.
821 * Setcdr:: Replacing part of the list backbone.
822 This can be used to remove or add elements.
823 * Rearrangement:: Reordering the elements in a list; combining lists.
827 @subsection Altering List Elements with @code{setcar}
829 Changing the @sc{car} of a cons cell is done with @code{setcar}. When
830 used on a list, @code{setcar} replaces one element of a list with a
833 @defun setcar cons object
834 This function stores @var{object} as the new @sc{car} of @var{cons},
835 replacing its previous @sc{car}. In other words, it changes the
836 @sc{car} slot of @var{cons} to refer to @var{object}. It returns the
837 value @var{object}. For example:
855 When a cons cell is part of the shared structure of several lists,
856 storing a new @sc{car} into the cons changes one element of each of
857 these lists. Here is an example:
861 ;; @r{Create two lists that are partly shared.}
864 (setq x2 (cons 'z (cdr x1)))
869 ;; @r{Replace the @sc{car} of a shared link.}
870 (setcar (cdr x1) 'foo)
872 x1 ; @r{Both lists are changed.}
879 ;; @r{Replace the @sc{car} of a link that is not shared.}
882 x1 ; @r{Only one list is changed.}
883 @result{} (baz foo c)
889 Here is a graphical depiction of the shared structure of the two lists
890 in the variables @code{x1} and @code{x2}, showing why replacing @code{b}
895 --- --- --- --- --- ---
896 x1---> | | |----> | | |--> | | |--> nil
897 --- --- --- --- --- ---
911 Here is an alternative form of box diagram, showing the same relationship:
916 -------------- -------------- --------------
917 | car | cdr | | car | cdr | | car | cdr |
918 | a | o------->| b | o------->| c | nil |
920 -------------- | -------------- --------------
932 @subsection Altering the CDR of a 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 modification of lists
1037 Here are some functions that rearrange lists ``destructively'' by
1038 modifying the @sc{cdr}s of their component cons cells. We call these
1039 functions ``destructive'' because they chew up the original lists passed
1040 to them as arguments, relinking their cons cells to form a new list that
1041 is the returned value.
1044 See @code{delq}, in @ref{Sets And Lists}, for another function
1045 that modifies cons cells.
1048 The function @code{delq} in the following section is another example
1049 of destructive list manipulation.
1052 @defun nconc &rest lists
1053 @cindex concatenating lists
1054 @cindex joining lists
1055 This function returns a list containing all the elements of @var{lists}.
1056 Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are
1057 @emph{not} copied. Instead, the last @sc{cdr} of each of the
1058 @var{lists} is changed to refer to the following list. The last of the
1059 @var{lists} is not altered. For example:
1068 @result{} (1 2 3 4 5)
1072 @result{} (1 2 3 4 5)
1076 Since the last argument of @code{nconc} is not itself modified, it is
1077 reasonable to use a constant list, such as @code{'(4 5)}, as in the
1078 above example. For the same reason, the last argument need not be a
1088 @result{} (1 2 3 . z)
1092 @result{} (1 2 3 . z)
1096 However, the other arguments (all but the last) must be lists.
1098 A common pitfall is to use a quoted constant list as a non-last
1099 argument to @code{nconc}. If you do this, your program will change
1100 each time you run it! Here is what happens:
1104 (defun add-foo (x) ; @r{We want this function to add}
1105 (nconc '(foo) x)) ; @r{@code{foo} to the front of its arg.}
1109 (symbol-function 'add-foo)
1110 @result{} (lambda (x) (nconc (quote (foo)) x))
1114 (setq xx (add-foo '(1 2))) ; @r{It seems to work.}
1118 (setq xy (add-foo '(3 4))) ; @r{What happened?}
1119 @result{} (foo 1 2 3 4)
1127 (symbol-function 'add-foo)
1128 @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x)))
1133 @defun nreverse list
1134 @cindex reversing a list
1135 This function reverses the order of the elements of @var{list}.
1136 Unlike @code{reverse}, @code{nreverse} alters its argument by reversing
1137 the @sc{cdr}s in the cons cells forming the list. The cons cell that
1138 used to be the last one in @var{list} becomes the first cons cell of the
1155 ;; @r{The cons cell that was first is now last.}
1161 To avoid confusion, we usually store the result of @code{nreverse}
1162 back in the same variable which held the original list:
1165 (setq x (nreverse x))
1168 Here is the @code{nreverse} of our favorite example, @code{(a b c)},
1169 presented graphically:
1173 @r{Original list head:} @r{Reversed list:}
1174 ------------- ------------- ------------
1175 | car | cdr | | car | cdr | | car | cdr |
1176 | a | nil |<-- | b | o |<-- | c | o |
1177 | | | | | | | | | | | | |
1178 ------------- | --------- | - | -------- | -
1180 ------------- ------------
1185 @defun sort list predicate
1187 @cindex sorting lists
1188 This function sorts @var{list} stably, though destructively, and
1189 returns the sorted list. It compares elements using @var{predicate}. A
1190 stable sort is one in which elements with equal sort keys maintain their
1191 relative order before and after the sort. Stability is important when
1192 successive sorts are used to order elements according to different
1195 The argument @var{predicate} must be a function that accepts two
1196 arguments. It is called with two elements of @var{list}. To get an
1197 increasing order sort, the @var{predicate} should return non-@code{nil} if the
1198 first element is ``less than'' the second, or @code{nil} if not.
1200 The comparison function @var{predicate} must give reliable results for
1201 any given pair of arguments, at least within a single call to
1202 @code{sort}. It must be @dfn{antisymmetric}; that is, if @var{a} is
1203 less than @var{b}, @var{b} must not be less than @var{a}. It must be
1204 @dfn{transitive}---that is, if @var{a} is less than @var{b}, and @var{b}
1205 is less than @var{c}, then @var{a} must be less than @var{c}. If you
1206 use a comparison function which does not meet these requirements, the
1207 result of @code{sort} is unpredictable.
1209 The destructive aspect of @code{sort} is that it rearranges the cons
1210 cells forming @var{list} by changing @sc{cdr}s. A nondestructive sort
1211 function would create new cons cells to store the elements in their
1212 sorted order. If you wish to make a sorted copy without destroying the
1213 original, copy it first with @code{copy-sequence} and then sort.
1215 Sorting does not change the @sc{car}s of the cons cells in @var{list};
1216 the cons cell that originally contained the element @code{a} in
1217 @var{list} still has @code{a} in its @sc{car} after sorting, but it now
1218 appears in a different position in the list due to the change of
1219 @sc{cdr}s. For example:
1223 (setq nums '(1 3 2 6 5 4 0))
1224 @result{} (1 3 2 6 5 4 0)
1228 @result{} (0 1 2 3 4 5 6)
1232 @result{} (1 2 3 4 5 6)
1237 @strong{Warning}: Note that the list in @code{nums} no longer contains
1238 0; this is the same cons cell that it was before, but it is no longer
1239 the first one in the list. Don't assume a variable that formerly held
1240 the argument now holds the entire sorted list! Instead, save the result
1241 of @code{sort} and use that. Most often we store the result back into
1242 the variable that held the original list:
1245 (setq nums (sort nums '<))
1248 @xref{Sorting}, for more functions that perform sorting.
1249 See @code{documentation} in @ref{Accessing Documentation}, for a
1250 useful example of @code{sort}.
1253 @node Sets And Lists
1254 @section Using Lists as Sets
1255 @cindex lists as sets
1258 A list can represent an unordered mathematical set---simply consider a
1259 value an element of a set if it appears in the list, and ignore the
1260 order of the list. To form the union of two sets, use @code{append} (as
1261 long as you don't mind having duplicate elements). You can remove
1262 @code{equal} duplicates using @code{delete-dups}. Other useful
1263 functions for sets include @code{memq} and @code{delq}, and their
1264 @code{equal} versions, @code{member} and @code{delete}.
1266 @cindex CL note---lack @code{union}, @code{intersection}
1268 @b{Common Lisp note:} Common Lisp has functions @code{union} (which
1269 avoids duplicate elements) and @code{intersection} for set operations.
1270 Although standard GNU Emacs Lisp does not have them, the @file{cl}
1271 library provides versions. @inforef{Top, Overview, cl}.
1274 @defun memq object list
1275 @cindex membership in a list
1276 This function tests to see whether @var{object} is a member of
1277 @var{list}. If it is, @code{memq} returns a list starting with the
1278 first occurrence of @var{object}. Otherwise, it returns @code{nil}.
1279 The letter @samp{q} in @code{memq} says that it uses @code{eq} to
1280 compare @var{object} against the elements of the list. For example:
1284 (memq 'b '(a b c b a))
1288 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1294 @defun delq object list
1295 @cindex deleting list elements
1296 This function destructively removes all elements @code{eq} to
1297 @var{object} from @var{list}. The letter @samp{q} in @code{delq} says
1298 that it uses @code{eq} to compare @var{object} against the elements of
1299 the list, like @code{memq} and @code{remq}.
1302 When @code{delq} deletes elements from the front of the list, it does so
1303 simply by advancing down the list and returning a sublist that starts
1304 after those elements:
1308 (delq 'a '(a b c)) @equiv{} (cdr '(a b c))
1312 When an element to be deleted appears in the middle of the list,
1313 removing it involves changing the @sc{cdr}s (@pxref{Setcdr}).
1317 (setq sample-list '(a b c (4)))
1318 @result{} (a b c (4))
1321 (delq 'a sample-list)
1326 @result{} (a b c (4))
1329 (delq 'c sample-list)
1338 Note that @code{(delq 'c sample-list)} modifies @code{sample-list} to
1339 splice out the third element, but @code{(delq 'a sample-list)} does not
1340 splice anything---it just returns a shorter list. Don't assume that a
1341 variable which formerly held the argument @var{list} now has fewer
1342 elements, or that it still holds the original list! Instead, save the
1343 result of @code{delq} and use that. Most often we store the result back
1344 into the variable that held the original list:
1347 (setq flowers (delq 'rose flowers))
1350 In the following example, the @code{(4)} that @code{delq} attempts to match
1351 and the @code{(4)} in the @code{sample-list} are not @code{eq}:
1355 (delq '(4) sample-list)
1360 If you want to delete elements that are @code{equal} to a given value,
1361 use @code{delete} (see below).
1363 @defun remq object list
1364 This function returns a copy of @var{list}, with all elements removed
1365 which are @code{eq} to @var{object}. The letter @samp{q} in @code{remq}
1366 says that it uses @code{eq} to compare @var{object} against the elements
1371 (setq sample-list '(a b c a b c))
1372 @result{} (a b c a b c)
1375 (remq 'a sample-list)
1380 @result{} (a b c a b c)
1385 @defun memql object list
1386 The function @code{memql} tests to see whether @var{object} is a member
1387 of @var{list}, comparing members with @var{object} using @code{eql},
1388 so floating point elements are compared by value.
1389 If @var{object} is a member, @code{memql} returns a list starting with
1390 its first occurrence in @var{list}. Otherwise, it returns @code{nil}.
1392 Compare this with @code{memq}:
1396 (memql 1.2 '(1.1 1.2 1.3)) ; @r{@code{1.2} and @code{1.2} are @code{eql}.}
1400 (memq 1.2 '(1.1 1.2 1.3)) ; @r{@code{1.2} and @code{1.2} are not @code{eq}.}
1406 The following three functions are like @code{memq}, @code{delq} and
1407 @code{remq}, but use @code{equal} rather than @code{eq} to compare
1408 elements. @xref{Equality Predicates}.
1410 @defun member object list
1411 The function @code{member} tests to see whether @var{object} is a member
1412 of @var{list}, comparing members with @var{object} using @code{equal}.
1413 If @var{object} is a member, @code{member} returns a list starting with
1414 its first occurrence in @var{list}. Otherwise, it returns @code{nil}.
1416 Compare this with @code{memq}:
1420 (member '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are @code{equal}.}
1424 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1428 ;; @r{Two strings with the same contents are @code{equal}.}
1429 (member "foo" '("foo" "bar"))
1430 @result{} ("foo" "bar")
1435 @defun delete object sequence
1436 If @code{sequence} is a list, this function destructively removes all
1437 elements @code{equal} to @var{object} from @var{sequence}. For lists,
1438 @code{delete} is to @code{delq} as @code{member} is to @code{memq}: it
1439 uses @code{equal} to compare elements with @var{object}, like
1440 @code{member}; when it finds an element that matches, it cuts the
1441 element out just as @code{delq} would.
1443 If @code{sequence} is a vector or string, @code{delete} returns a copy
1444 of @code{sequence} with all elements @code{equal} to @code{object}
1451 (setq l '((2) (1) (2)))
1456 ;; @r{If you want to change @code{l} reliably,}
1457 ;; @r{write @code{(setq l (delete elt l))}.}
1460 (setq l '((2) (1) (2)))
1465 ;; @r{In this case, it makes no difference whether you set @code{l},}
1466 ;; @r{but you should do so for the sake of the other case.}
1469 (delete '(2) [(2) (1) (2)])
1475 @defun remove object sequence
1476 This function is the non-destructive counterpart of @code{delete}. It
1477 returns a copy of @code{sequence}, a list, vector, or string, with
1478 elements @code{equal} to @code{object} removed. For example:
1482 (remove '(2) '((2) (1) (2)))
1486 (remove '(2) [(2) (1) (2)])
1493 @b{Common Lisp note:} The functions @code{member}, @code{delete} and
1494 @code{remove} in GNU Emacs Lisp are derived from Maclisp, not Common
1495 Lisp. The Common Lisp versions do not use @code{equal} to compare
1499 @defun member-ignore-case object list
1500 This function is like @code{member}, except that @var{object} should
1501 be a string and that it ignores differences in letter-case and text
1502 representation: upper-case and lower-case letters are treated as
1503 equal, and unibyte strings are converted to multibyte prior to
1507 @defun delete-dups list
1508 This function destructively removes all @code{equal} duplicates from
1509 @var{list}, stores the result in @var{list} and returns it. Of
1510 several @code{equal} occurrences of an element in @var{list},
1511 @code{delete-dups} keeps the first one.
1514 See also the function @code{add-to-list}, in @ref{List Variables},
1515 for a way to add an element to a list stored in a variable and used as a
1518 @node Association Lists
1519 @section Association Lists
1520 @cindex association list
1523 An @dfn{association list}, or @dfn{alist} for short, records a mapping
1524 from keys to values. It is a list of cons cells called
1525 @dfn{associations}: the @sc{car} of each cons cell is the @dfn{key}, and the
1526 @sc{cdr} is the @dfn{associated value}.@footnote{This usage of ``key''
1527 is not related to the term ``key sequence''; it means a value used to
1528 look up an item in a table. In this case, the table is the alist, and
1529 the alist associations are the items.}
1531 Here is an example of an alist. The key @code{pine} is associated with
1532 the value @code{cones}; the key @code{oak} is associated with
1533 @code{acorns}; and the key @code{maple} is associated with @code{seeds}.
1543 Both the values and the keys in an alist may be any Lisp objects.
1544 For example, in the following alist, the symbol @code{a} is
1545 associated with the number @code{1}, and the string @code{"b"} is
1546 associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of
1553 Sometimes it is better to design an alist to store the associated
1554 value in the @sc{car} of the @sc{cdr} of the element. Here is an
1555 example of such an alist:
1558 ((rose red) (lily white) (buttercup yellow))
1562 Here we regard @code{red} as the value associated with @code{rose}. One
1563 advantage of this kind of alist is that you can store other related
1564 information---even a list of other items---in the @sc{cdr} of the
1565 @sc{cdr}. One disadvantage is that you cannot use @code{rassq} (see
1566 below) to find the element containing a given value. When neither of
1567 these considerations is important, the choice is a matter of taste, as
1568 long as you are consistent about it for any given alist.
1570 The same alist shown above could be regarded as having the
1571 associated value in the @sc{cdr} of the element; the value associated
1572 with @code{rose} would be the list @code{(red)}.
1574 Association lists are often used to record information that you might
1575 otherwise keep on a stack, since new associations may be added easily to
1576 the front of the list. When searching an association list for an
1577 association with a given key, the first one found is returned, if there
1580 In Emacs Lisp, it is @emph{not} an error if an element of an
1581 association list is not a cons cell. The alist search functions simply
1582 ignore such elements. Many other versions of Lisp signal errors in such
1585 Note that property lists are similar to association lists in several
1586 respects. A property list behaves like an association list in which
1587 each key can occur only once. @xref{Property Lists}, for a comparison
1588 of property lists and association lists.
1590 @defun assoc key alist
1591 This function returns the first association for @var{key} in
1592 @var{alist}, comparing @var{key} against the alist elements using
1593 @code{equal} (@pxref{Equality Predicates}). It returns @code{nil} if no
1594 association in @var{alist} has a @sc{car} @code{equal} to @var{key}.
1598 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1599 @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1601 @result{} (oak . acorns)
1602 (cdr (assoc 'oak trees))
1604 (assoc 'birch trees)
1608 Here is another example, in which the keys and values are not symbols:
1611 (setq needles-per-cluster
1612 '((2 "Austrian Pine" "Red Pine")
1616 (cdr (assoc 3 needles-per-cluster))
1617 @result{} ("Pitch Pine")
1618 (cdr (assoc 2 needles-per-cluster))
1619 @result{} ("Austrian Pine" "Red Pine")
1623 The function @code{assoc-string} is much like @code{assoc} except
1624 that it ignores certain differences between strings. @xref{Text
1627 @defun rassoc value alist
1628 This function returns the first association with value @var{value} in
1629 @var{alist}. It returns @code{nil} if no association in @var{alist} has
1630 a @sc{cdr} @code{equal} to @var{value}.
1632 @code{rassoc} is like @code{assoc} except that it compares the @sc{cdr} of
1633 each @var{alist} association instead of the @sc{car}. You can think of
1634 this as ``reverse @code{assoc},'' finding the key for a given value.
1637 @defun assq key alist
1638 This function is like @code{assoc} in that it returns the first
1639 association for @var{key} in @var{alist}, but it makes the comparison
1640 using @code{eq} instead of @code{equal}. @code{assq} returns @code{nil}
1641 if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}.
1642 This function is used more often than @code{assoc}, since @code{eq} is
1643 faster than @code{equal} and most alists use symbols as keys.
1644 @xref{Equality Predicates}.
1647 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1648 @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1650 @result{} (pine . cones)
1653 On the other hand, @code{assq} is not usually useful in alists where the
1654 keys may not be symbols:
1658 '(("simple leaves" . oak)
1659 ("compound leaves" . horsechestnut)))
1661 (assq "simple leaves" leaves)
1663 (assoc "simple leaves" leaves)
1664 @result{} ("simple leaves" . oak)
1668 @defun rassq value alist
1669 This function returns the first association with value @var{value} in
1670 @var{alist}. It returns @code{nil} if no association in @var{alist} has
1671 a @sc{cdr} @code{eq} to @var{value}.
1673 @code{rassq} is like @code{assq} except that it compares the @sc{cdr} of
1674 each @var{alist} association instead of the @sc{car}. You can think of
1675 this as ``reverse @code{assq},'' finding the key for a given value.
1680 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1682 (rassq 'acorns trees)
1683 @result{} (oak . acorns)
1684 (rassq 'spores trees)
1688 @code{rassq} cannot search for a value stored in the @sc{car}
1689 of the @sc{cdr} of an element:
1692 (setq colors '((rose red) (lily white) (buttercup yellow)))
1694 (rassq 'white colors)
1698 In this case, the @sc{cdr} of the association @code{(lily white)} is not
1699 the symbol @code{white}, but rather the list @code{(white)}. This
1700 becomes clearer if the association is written in dotted pair notation:
1703 (lily white) @equiv{} (lily . (white))
1707 @defun assoc-default key alist &optional test default
1708 This function searches @var{alist} for a match for @var{key}. For each
1709 element of @var{alist}, it compares the element (if it is an atom) or
1710 the element's @sc{car} (if it is a cons) against @var{key}, by calling
1711 @var{test} with two arguments: the element or its @sc{car}, and
1712 @var{key}. The arguments are passed in that order so that you can get
1713 useful results using @code{string-match} with an alist that contains
1714 regular expressions (@pxref{Regexp Search}). If @var{test} is omitted
1715 or @code{nil}, @code{equal} is used for comparison.
1717 If an alist element matches @var{key} by this criterion,
1718 then @code{assoc-default} returns a value based on this element.
1719 If the element is a cons, then the value is the element's @sc{cdr}.
1720 Otherwise, the return value is @var{default}.
1722 If no alist element matches @var{key}, @code{assoc-default} returns
1726 @defun copy-alist alist
1727 @cindex copying alists
1728 This function returns a two-level deep copy of @var{alist}: it creates a
1729 new copy of each association, so that you can alter the associations of
1730 the new alist without changing the old one.
1734 (setq needles-per-cluster
1735 '((2 . ("Austrian Pine" "Red Pine"))
1736 (3 . ("Pitch Pine"))
1738 (5 . ("White Pine"))))
1740 ((2 "Austrian Pine" "Red Pine")
1744 (setq copy (copy-alist needles-per-cluster))
1746 ((2 "Austrian Pine" "Red Pine")
1750 (eq needles-per-cluster copy)
1752 (equal needles-per-cluster copy)
1754 (eq (car needles-per-cluster) (car copy))
1756 (cdr (car (cdr needles-per-cluster)))
1757 @result{} ("Pitch Pine")
1759 (eq (cdr (car (cdr needles-per-cluster)))
1760 (cdr (car (cdr copy))))
1765 This example shows how @code{copy-alist} makes it possible to change
1766 the associations of one copy without affecting the other:
1770 (setcdr (assq 3 copy) '("Martian Vacuum Pine"))
1771 (cdr (assq 3 needles-per-cluster))
1772 @result{} ("Pitch Pine")
1777 @defun assq-delete-all key alist
1778 This function deletes from @var{alist} all the elements whose @sc{car}
1779 is @code{eq} to @var{key}, much as if you used @code{delq} to delete
1780 each such element one by one. It returns the shortened alist, and
1781 often modifies the original list structure of @var{alist}. For
1782 correct results, use the return value of @code{assq-delete-all} rather
1783 than looking at the saved value of @var{alist}.
1786 (setq alist '((foo 1) (bar 2) (foo 3) (lose 4)))
1787 @result{} ((foo 1) (bar 2) (foo 3) (lose 4))
1788 (assq-delete-all 'foo alist)
1789 @result{} ((bar 2) (lose 4))
1791 @result{} ((foo 1) (bar 2) (lose 4))
1795 @defun rassq-delete-all value alist
1796 This function deletes from @var{alist} all the elements whose @sc{cdr}
1797 is @code{eq} to @var{value}. It returns the shortened alist, and
1798 often modifies the original list structure of @var{alist}.
1799 @code{rassq-delete-all} is like @code{assq-delete-all} except that it
1800 compares the @sc{cdr} of each @var{alist} association instead of the
1805 @section Managing a Fixed-Size Ring of Objects
1807 @cindex ring data structure
1808 This section describes functions for operating on rings. A
1809 @dfn{ring} is a fixed-size data structure that supports insertion,
1810 deletion, rotation, and modulo-indexed reference and traversal.
1812 @defun make-ring size
1813 This returns a new ring capable of holding @var{size} objects.
1814 @var{size} should be an integer.
1817 @defun ring-p object
1818 This returns @code{t} if @var{object} is a ring, @code{nil} otherwise.
1821 @defun ring-size ring
1822 This returns the maximum capacity of the @var{ring}.
1825 @defun ring-length ring
1826 This returns the number of objects that @var{ring} currently contains.
1827 The value will never exceed that returned by @code{ring-size}.
1830 @defun ring-elements ring
1831 This returns a list of the objects in @var{ring}, in order, newest first.
1834 @defun ring-copy ring
1835 This returns a new ring which is a copy of @var{ring}.
1836 The new ring contains the same (@code{eq}) objects as @var{ring}.
1839 @defun ring-empty-p ring
1840 This returns @code{t} if @var{ring} is empty, @code{nil} otherwise.
1843 The newest element in the ring always has index 0. Higher indices
1844 correspond to older elements. Indices are computed modulo the ring
1845 length. Index @minus{}1 corresponds to the oldest element, @minus{}2
1846 to the next-oldest, and so forth.
1848 @defun ring-ref ring index
1849 This returns the object in @var{ring} found at index @var{index}.
1850 @var{index} may be negative or greater than the ring length. If
1851 @var{ring} is empty, @code{ring-ref} signals an error.
1854 @defun ring-insert ring object
1855 This inserts @var{object} into @var{ring}, making it the newest
1856 element, and returns @var{object}.
1858 If the ring is full, insertion removes the oldest element to
1859 make room for the new element.
1862 @defun ring-remove ring &optional index
1863 Remove an object from @var{ring}, and return that object. The
1864 argument @var{index} specifies which item to remove; if it is
1865 @code{nil}, that means to remove the oldest item. If @var{ring} is
1866 empty, @code{ring-remove} signals an error.
1869 @defun ring-insert-at-beginning ring object
1870 This inserts @var{object} into @var{ring}, treating it as the oldest
1871 element. The return value is not significant.
1873 If the ring is full, this function removes the newest element to make
1874 room for the inserted element.
1877 @cindex fifo data structure
1878 If you are careful not to exceed the ring size, you can
1879 use the ring as a first-in-first-out queue. For example:
1882 (let ((fifo (make-ring 5)))
1883 (mapc (lambda (obj) (ring-insert fifo obj))
1885 (list (ring-remove fifo) t
1886 (ring-remove fifo) t
1887 (ring-remove fifo)))
1888 @result{} (0 t one t "two")