2 @c This is part of the GNU Emacs Lisp Reference Manual.
3 @c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998, 1999, 2002, 2003,
4 @c 2004, 2005, 2006 Free Software Foundation, Inc.
5 @c See the file elisp.texi for copying conditions.
6 @setfilename ../info/lists
7 @node Lists, Sequences Arrays Vectors, Strings and Characters, Top
10 @cindex element (of list)
12 A @dfn{list} represents a sequence of zero or more elements (which may
13 be any Lisp objects). The important difference between lists and
14 vectors is that two or more lists can share part of their structure; in
15 addition, you can insert or delete elements in a list without copying
19 * Cons Cells:: How lists are made out of cons cells.
20 * List-related Predicates:: Is this object a list? Comparing two lists.
21 * List Elements:: Extracting the pieces of a list.
22 * Building Lists:: Creating list structure.
23 * List Variables:: Modifying lists stored in variables.
24 * Modifying Lists:: Storing new pieces into an existing list.
25 * Sets And Lists:: A list can represent a finite mathematical set.
26 * Association Lists:: A list can represent a finite relation or mapping.
27 * Rings:: Managing a fixed-size ring of objects.
31 @section Lists and Cons Cells
32 @cindex lists and cons cells
33 @cindex @code{nil} and lists
35 Lists in Lisp are not a primitive data type; they are built up from
36 @dfn{cons cells}. A cons cell is a data object that represents an
37 ordered pair. That is, it has two slots, and each slot @dfn{holds}, or
38 @dfn{refers to}, some Lisp object. One slot is known as the @sc{car},
39 and the other is known as the @sc{cdr}. (These names are traditional;
40 see @ref{Cons Cell Type}.) @sc{cdr} is pronounced ``could-er.''
42 We say that ``the @sc{car} of this cons cell is'' whatever object
43 its @sc{car} slot currently holds, and likewise for the @sc{cdr}.
45 A list is a series of cons cells ``chained together,'' so that each
46 cell refers to the next one. There is one cons cell for each element of
47 the list. By convention, the @sc{car}s of the cons cells hold the
48 elements of the list, and the @sc{cdr}s are used to chain the list: the
49 @sc{cdr} slot of each cons cell refers to the following cons cell. The
50 @sc{cdr} of the last cons cell is @code{nil}. This asymmetry between
51 the @sc{car} and the @sc{cdr} is entirely a matter of convention; at the
52 level of cons cells, the @sc{car} and @sc{cdr} slots have the same
56 Since @code{nil} is the conventional value to put in the @sc{cdr} of
57 the last cons cell in the list, we call that case a @dfn{true list}.
59 In Lisp, we consider the symbol @code{nil} a list as well as a
60 symbol; it is the list with no elements. For convenience, the symbol
61 @code{nil} is considered to have @code{nil} as its @sc{cdr} (and also
62 as its @sc{car}). Therefore, the @sc{cdr} of a true list is always a
67 If the @sc{cdr} of a list's last cons cell is some other value,
68 neither @code{nil} nor another cons cell, we call the structure a
69 @dfn{dotted list}, since its printed representation would use
70 @samp{.}. There is one other possibility: some cons cell's @sc{cdr}
71 could point to one of the previous cons cells in the list. We call
72 that structure a @dfn{circular list}.
74 For some purposes, it does not matter whether a list is true,
75 circular or dotted. If the program doesn't look far enough down the
76 list to see the @sc{cdr} of the final cons cell, it won't care.
77 However, some functions that operate on lists demand true lists and
78 signal errors if given a dotted list. Most functions that try to find
79 the end of a list enter infinite loops if given a circular list.
81 @cindex list structure
82 Because most cons cells are used as part of lists, the phrase
83 @dfn{list structure} has come to mean any structure made out of cons
86 The @sc{cdr} of any nonempty true list @var{l} is a list containing all the
87 elements of @var{l} except the first.
89 @xref{Cons Cell Type}, for the read and print syntax of cons cells and
90 lists, and for ``box and arrow'' illustrations of lists.
92 @node List-related Predicates
93 @section Predicates on Lists
95 The following predicates test whether a Lisp object is an atom,
96 whether it is a cons cell or is a list, or whether it is the
97 distinguished object @code{nil}. (Many of these predicates can be
98 defined in terms of the others, but they are used so often that it is
99 worth having all of them.)
102 This function returns @code{t} if @var{object} is a cons cell, @code{nil}
103 otherwise. @code{nil} is not a cons cell, although it @emph{is} a list.
108 This function returns @code{t} if @var{object} is an atom, @code{nil}
109 otherwise. All objects except cons cells are atoms. The symbol
110 @code{nil} is an atom and is also a list; it is the only Lisp object
114 (atom @var{object}) @equiv{} (not (consp @var{object}))
119 This function returns @code{t} if @var{object} is a cons cell or
120 @code{nil}. Otherwise, it returns @code{nil}.
135 This function is the opposite of @code{listp}: it returns @code{t} if
136 @var{object} is not a list. Otherwise, it returns @code{nil}.
139 (listp @var{object}) @equiv{} (not (nlistp @var{object}))
144 This function returns @code{t} if @var{object} is @code{nil}, and
145 returns @code{nil} otherwise. This function is identical to @code{not},
146 but as a matter of clarity we use @code{null} when @var{object} is
147 considered a list and @code{not} when it is considered a truth value
148 (see @code{not} in @ref{Combining Conditions}).
165 @section Accessing Elements of Lists
166 @cindex list elements
169 This function returns the value referred to by the first slot of the
170 cons cell @var{cons-cell}. Expressed another way, this function
171 returns the @sc{car} of @var{cons-cell}.
173 As a special case, if @var{cons-cell} is @code{nil}, then @code{car}
174 is defined to return @code{nil}; therefore, any list is a valid argument
175 for @code{car}. An error is signaled if the argument is not a cons cell
191 This function returns the value referred to by the second slot of
192 the cons cell @var{cons-cell}. Expressed another way, this function
193 returns the @sc{cdr} of @var{cons-cell}.
195 As a special case, if @var{cons-cell} is @code{nil}, then @code{cdr}
196 is defined to return @code{nil}; therefore, any list is a valid argument
197 for @code{cdr}. An error is signaled if the argument is not a cons cell
212 @defun car-safe object
213 This function lets you take the @sc{car} of a cons cell while avoiding
214 errors for other data types. It returns the @sc{car} of @var{object} if
215 @var{object} is a cons cell, @code{nil} otherwise. This is in contrast
216 to @code{car}, which signals an error if @var{object} is not a list.
220 (car-safe @var{object})
222 (let ((x @var{object}))
230 @defun cdr-safe object
231 This function lets you take the @sc{cdr} of a cons cell while
232 avoiding errors for other data types. It returns the @sc{cdr} of
233 @var{object} if @var{object} is a cons cell, @code{nil} otherwise.
234 This is in contrast to @code{cdr}, which signals an error if
235 @var{object} is not a list.
239 (cdr-safe @var{object})
241 (let ((x @var{object}))
250 This macro is a way of examining the @sc{car} of a list,
251 and taking it off the list, all at once.
253 It operates on the list which is stored in the symbol @var{listname}.
254 It removes this element from the list by setting @var{listname}
255 to the @sc{cdr} of its old value---but it also returns the @sc{car}
256 of that list, which is the element being removed.
269 @anchor{Definition of nth}
270 This function returns the @var{n}th element of @var{list}. Elements
271 are numbered starting with zero, so the @sc{car} of @var{list} is
272 element number zero. If the length of @var{list} is @var{n} or less,
273 the value is @code{nil}.
275 If @var{n} is negative, @code{nth} returns the first element of
291 (nth n x) @equiv{} (car (nthcdr n x))
295 The function @code{elt} is similar, but applies to any kind of sequence.
296 For historical reasons, it takes its arguments in the opposite order.
297 @xref{Sequence Functions}.
301 This function returns the @var{n}th @sc{cdr} of @var{list}. In other
302 words, it skips past the first @var{n} links of @var{list} and returns
305 If @var{n} is zero or negative, @code{nthcdr} returns all of
306 @var{list}. If the length of @var{list} is @var{n} or less,
307 @code{nthcdr} returns @code{nil}.
311 (nthcdr 1 '(1 2 3 4))
315 (nthcdr 10 '(1 2 3 4))
319 (nthcdr -3 '(1 2 3 4))
325 @defun last list &optional n
326 This function returns the last link of @var{list}. The @code{car} of
327 this link is the list's last element. If @var{list} is null,
328 @code{nil} is returned. If @var{n} is non-@code{nil}, the
329 @var{n}th-to-last link is returned instead, or the whole of @var{list}
330 if @var{n} is bigger than @var{list}'s length.
333 @defun safe-length list
334 @anchor{Definition of safe-length}
335 This function returns the length of @var{list}, with no risk of either
336 an error or an infinite loop. It generally returns the number of
337 distinct cons cells in the list. However, for circular lists,
338 the value is just an upper bound; it is often too large.
340 If @var{list} is not @code{nil} or a cons cell, @code{safe-length}
344 The most common way to compute the length of a list, when you are not
345 worried that it may be circular, is with @code{length}. @xref{Sequence
348 @defun caar cons-cell
349 This is the same as @code{(car (car @var{cons-cell}))}.
352 @defun cadr cons-cell
353 This is the same as @code{(car (cdr @var{cons-cell}))}
354 or @code{(nth 1 @var{cons-cell})}.
357 @defun cdar cons-cell
358 This is the same as @code{(cdr (car @var{cons-cell}))}.
361 @defun cddr cons-cell
362 This is the same as @code{(cdr (cdr @var{cons-cell}))}
363 or @code{(nthcdr 2 @var{cons-cell})}.
366 @defun butlast x &optional n
367 This function returns the list @var{x} with the last element,
368 or the last @var{n} elements, removed. If @var{n} is greater
369 than zero it makes a copy of the list so as not to damage the
370 original list. In general, @code{(append (butlast @var{x} @var{n})
371 (last @var{x} @var{n}))} will return a list equal to @var{x}.
374 @defun nbutlast x &optional n
375 This is a version of @code{butlast} that works by destructively
376 modifying the @code{cdr} of the appropriate element, rather than
377 making a copy of the list.
381 @comment node-name, next, previous, up
382 @section Building Cons Cells and Lists
384 @cindex building lists
386 Many functions build lists, as lists reside at the very heart of Lisp.
387 @code{cons} is the fundamental list-building function; however, it is
388 interesting to note that @code{list} is used more times in the source
389 code for Emacs than @code{cons}.
391 @defun cons object1 object2
392 This function is the most basic function for building new list
393 structure. It creates a new cons cell, making @var{object1} the
394 @sc{car}, and @var{object2} the @sc{cdr}. It then returns the new
395 cons cell. The arguments @var{object1} and @var{object2} may be any
396 Lisp objects, but most often @var{object2} is a list.
414 @code{cons} is often used to add a single element to the front of a
415 list. This is called @dfn{consing the element onto the list}.
416 @footnote{There is no strictly equivalent way to add an element to
417 the end of a list. You can use @code{(append @var{listname} (list
418 @var{newelt}))}, which creates a whole new list by copying @var{listname}
419 and adding @var{newelt} to its end. Or you can use @code{(nconc
420 @var{listname} (list @var{newelt}))}, which modifies @var{listname}
421 by following all the @sc{cdr}s and then replacing the terminating
422 @code{nil}. Compare this to adding an element to the beginning of a
423 list with @code{cons}, which neither copies nor modifies the list.}
427 (setq list (cons newelt list))
430 Note that there is no conflict between the variable named @code{list}
431 used in this example and the function named @code{list} described below;
432 any symbol can serve both purposes.
435 @defun list &rest objects
436 This function creates a list with @var{objects} as its elements. The
437 resulting list is always @code{nil}-terminated. If no @var{objects}
438 are given, the empty list is returned.
443 @result{} (1 2 3 4 5)
446 (list 1 2 '(3 4 5) 'foo)
447 @result{} (1 2 (3 4 5) foo)
456 @defun make-list length object
457 This function creates a list of @var{length} elements, in which each
458 element is @var{object}. Compare @code{make-list} with
459 @code{make-string} (@pxref{Creating Strings}).
464 @result{} (pigs pigs pigs)
471 (setq l (make-list 3 '(a b))
472 @result{} ((a b) (a b) (a b))
473 (eq (car l) (cadr l))
479 @defun append &rest sequences
480 @cindex copying lists
481 This function returns a list containing all the elements of
482 @var{sequences}. The @var{sequences} may be lists, vectors,
483 bool-vectors, or strings, but the last one should usually be a list.
484 All arguments except the last one are copied, so none of the arguments
485 is altered. (See @code{nconc} in @ref{Rearrangement}, for a way to join
486 lists with no copying.)
488 More generally, the final argument to @code{append} may be any Lisp
489 object. The final argument is not copied or converted; it becomes the
490 @sc{cdr} of the last cons cell in the new list. If the final argument
491 is itself a list, then its elements become in effect elements of the
492 result list. If the final element is not a list, the result is a
493 dotted list since its final @sc{cdr} is not @code{nil} as required
496 In Emacs 20 and before, the @code{append} function also allowed
497 integers as (non last) arguments. It converted them to strings of
498 digits, making up the decimal print representation of the integer, and
499 then used the strings instead of the original integers. This obsolete
500 usage no longer works. The proper way to convert an integer to a
501 decimal number in this way is with @code{format} (@pxref{Formatting
502 Strings}) or @code{number-to-string} (@pxref{String Conversion}).
505 Here is an example of using @code{append}:
509 (setq trees '(pine oak))
511 (setq more-trees (append '(maple birch) trees))
512 @result{} (maple birch pine oak)
519 @result{} (maple birch pine oak)
522 (eq trees (cdr (cdr more-trees)))
527 You can see how @code{append} works by looking at a box diagram. The
528 variable @code{trees} is set to the list @code{(pine oak)} and then the
529 variable @code{more-trees} is set to the list @code{(maple birch pine
530 oak)}. However, the variable @code{trees} continues to refer to the
537 | --- --- --- --- -> --- --- --- ---
538 --> | | |--> | | |--> | | |--> | | |--> nil
539 --- --- --- --- --- --- --- ---
542 --> maple -->birch --> pine --> oak
546 An empty sequence contributes nothing to the value returned by
547 @code{append}. As a consequence of this, a final @code{nil} argument
548 forces a copy of the previous argument:
556 (setq wood (append trees nil))
570 This once was the usual way to copy a list, before the function
571 @code{copy-sequence} was invented. @xref{Sequences Arrays Vectors}.
573 Here we show the use of vectors and strings as arguments to @code{append}:
577 (append [a b] "cd" nil)
578 @result{} (a b 99 100)
582 With the help of @code{apply} (@pxref{Calling Functions}), we can append
583 all the lists in a list of lists:
587 (apply 'append '((a b c) nil (x y z) nil))
588 @result{} (a b c x y z)
592 If no @var{sequences} are given, @code{nil} is returned:
601 Here are some examples where the final argument is not a list:
607 @result{} (x y . [z])
611 The second example shows that when the final argument is a sequence but
612 not a list, the sequence's elements do not become elements of the
613 resulting list. Instead, the sequence becomes the final @sc{cdr}, like
614 any other non-list final argument.
617 This function creates a new list whose elements are the elements of
618 @var{list}, but in reverse order. The original argument @var{list} is
635 @defun copy-tree tree &optional vecp
636 This function returns a copy of the tree @code{tree}. If @var{tree} is a
637 cons cell, this makes a new cons cell with the same @sc{car} and
638 @sc{cdr}, then recursively copies the @sc{car} and @sc{cdr} in the
641 Normally, when @var{tree} is anything other than a cons cell,
642 @code{copy-tree} simply returns @var{tree}. However, if @var{vecp} is
643 non-@code{nil}, it copies vectors too (and operates recursively on
647 @defun number-sequence from &optional to separation
648 This returns a list of numbers starting with @var{from} and
649 incrementing by @var{separation}, and ending at or just before
650 @var{to}. @var{separation} can be positive or negative and defaults
651 to 1. If @var{to} is @code{nil} or numerically equal to @var{from},
652 the value is the one-element list @code{(@var{from})}. If @var{to} is
653 less than @var{from} with a positive @var{separation}, or greater than
654 @var{from} with a negative @var{separation}, the value is @code{nil}
655 because those arguments specify an empty sequence.
657 If @var{separation} is 0 and @var{to} is neither @code{nil} nor
658 numerically equal to @var{from}, @code{number-sequence} signals an
659 error, since those arguments specify an infinite sequence.
661 All arguments can be integers or floating point numbers. However,
662 floating point arguments can be tricky, because floating point
663 arithmetic is inexact. For instance, depending on the machine, it may
664 quite well happen that @code{(number-sequence 0.4 0.6 0.2)} returns
665 the one element list @code{(0.4)}, whereas
666 @code{(number-sequence 0.4 0.8 0.2)} returns a list with three
667 elements. The @var{n}th element of the list is computed by the exact
668 formula @code{(+ @var{from} (* @var{n} @var{separation}))}. Thus, if
669 one wants to make sure that @var{to} is included in the list, one can
670 pass an expression of this exact type for @var{to}. Alternatively,
671 one can replace @var{to} with a slightly larger value (or a slightly
672 more negative value if @var{separation} is negative).
677 (number-sequence 4 9)
678 @result{} (4 5 6 7 8 9)
679 (number-sequence 9 4 -1)
680 @result{} (9 8 7 6 5 4)
681 (number-sequence 9 4 -2)
685 (number-sequence 8 5)
687 (number-sequence 5 8 -1)
689 (number-sequence 1.5 6 2)
690 @result{} (1.5 3.5 5.5)
695 @section Modifying List Variables
697 These functions, and one macro, provide convenient ways
698 to modify a list which is stored in a variable.
700 @defmac push newelt listname
701 This macro provides an alternative way to write
702 @code{(setq @var{listname} (cons @var{newelt} @var{listname}))}.
714 Two functions modify lists that are the values of variables.
716 @defun add-to-list symbol element &optional append
717 This function sets the variable @var{symbol} by consing @var{element}
718 onto the old value, if @var{element} is not already a member of that
719 value. It returns the resulting list, whether updated or not. The
720 value of @var{symbol} had better be a list already before the call.
721 Membership is tested using @code{equal}.
723 Normally, if @var{element} is added, it is added to the front of
724 @var{symbol}, but if the optional argument @var{append} is
725 non-@code{nil}, it is added at the end.
727 The argument @var{symbol} is not implicitly quoted; @code{add-to-list}
728 is an ordinary function, like @code{set} and unlike @code{setq}. Quote
729 the argument yourself if that is what you want.
732 Here's a scenario showing how to use @code{add-to-list}:
738 (add-to-list 'foo 'c) ;; @r{Add @code{c}.}
741 (add-to-list 'foo 'b) ;; @r{No effect.}
744 foo ;; @r{@code{foo} was changed.}
748 An equivalent expression for @code{(add-to-list '@var{var}
749 @var{value})} is this:
752 (or (member @var{value} @var{var})
753 (setq @var{var} (cons @var{value} @var{var})))
756 @defun add-to-ordered-list symbol element &optional order
757 This function sets the variable @var{symbol} by inserting
758 @var{element} into the old value, which must be a list, at the
759 position specified by @var{order}. If @var{element} is already a
760 member of the list, its position in the list is adjusted according
761 to @var{order}. Membership is tested using @code{eq}.
762 This function returns the resulting list, whether updated or not.
764 The @var{order} is typically a number (integer or float), and the
765 elements of the list are sorted in non-decreasing numerical order.
767 @var{order} may also be omitted or @code{nil}. Then the numeric order
768 of @var{element} stays unchanged if it already has one; otherwise,
769 @var{element} has no numeric order. Elements without a numeric list
770 order are placed at the end of the list, in no particular order.
772 Any other value for @var{order} removes the numeric order of @var{element}
773 if it already has one; otherwise, it is equivalent to @code{nil}.
775 The argument @var{symbol} is not implicitly quoted;
776 @code{add-to-ordered-list} is an ordinary function, like @code{set}
777 and unlike @code{setq}. Quote the argument yourself if that is what
780 The ordering information is stored in a hash table on @var{symbol}'s
781 @code{list-order} property.
784 Here's a scenario showing how to use @code{add-to-ordered-list}:
790 (add-to-ordered-list 'foo 'a 1) ;; @r{Add @code{a}.}
793 (add-to-ordered-list 'foo 'c 3) ;; @r{Add @code{c}.}
796 (add-to-ordered-list 'foo 'b 2) ;; @r{Add @code{b}.}
799 (add-to-ordered-list 'foo 'b 4) ;; @r{Move @code{b}.}
802 (add-to-ordered-list 'foo 'd) ;; @r{Append @code{d}.}
805 (add-to-ordered-list 'foo 'e) ;; @r{Add @code{e}}.
806 @result{} (a c b e d)
808 foo ;; @r{@code{foo} was changed.}
809 @result{} (a c b e d)
812 @node Modifying Lists
813 @section Modifying Existing List Structure
814 @cindex destructive list operations
816 You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the
817 primitives @code{setcar} and @code{setcdr}. We call these ``destructive''
818 operations because they change existing list structure.
820 @cindex CL note---@code{rplaca} vs @code{setcar}
824 @b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and
825 @code{rplacd} to alter list structure; they change structure the same
826 way as @code{setcar} and @code{setcdr}, but the Common Lisp functions
827 return the cons cell while @code{setcar} and @code{setcdr} return the
828 new @sc{car} or @sc{cdr}.
832 * Setcar:: Replacing an element in a list.
833 * Setcdr:: Replacing part of the list backbone.
834 This can be used to remove or add elements.
835 * Rearrangement:: Reordering the elements in a list; combining lists.
839 @subsection Altering List Elements with @code{setcar}
841 Changing the @sc{car} of a cons cell is done with @code{setcar}. When
842 used on a list, @code{setcar} replaces one element of a list with a
845 @defun setcar cons object
846 This function stores @var{object} as the new @sc{car} of @var{cons},
847 replacing its previous @sc{car}. In other words, it changes the
848 @sc{car} slot of @var{cons} to refer to @var{object}. It returns the
849 value @var{object}. For example:
867 When a cons cell is part of the shared structure of several lists,
868 storing a new @sc{car} into the cons changes one element of each of
869 these lists. Here is an example:
873 ;; @r{Create two lists that are partly shared.}
876 (setq x2 (cons 'z (cdr x1)))
881 ;; @r{Replace the @sc{car} of a shared link.}
882 (setcar (cdr x1) 'foo)
884 x1 ; @r{Both lists are changed.}
891 ;; @r{Replace the @sc{car} of a link that is not shared.}
894 x1 ; @r{Only one list is changed.}
895 @result{} (baz foo c)
901 Here is a graphical depiction of the shared structure of the two lists
902 in the variables @code{x1} and @code{x2}, showing why replacing @code{b}
907 --- --- --- --- --- ---
908 x1---> | | |----> | | |--> | | |--> nil
909 --- --- --- --- --- ---
923 Here is an alternative form of box diagram, showing the same relationship:
928 -------------- -------------- --------------
929 | car | cdr | | car | cdr | | car | cdr |
930 | a | o------->| b | o------->| c | nil |
932 -------------- | -------------- --------------
944 @subsection Altering the CDR of a List
946 The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}:
948 @defun setcdr cons object
949 This function stores @var{object} as the new @sc{cdr} of @var{cons},
950 replacing its previous @sc{cdr}. In other words, it changes the
951 @sc{cdr} slot of @var{cons} to refer to @var{object}. It returns the
955 Here is an example of replacing the @sc{cdr} of a list with a
956 different list. All but the first element of the list are removed in
957 favor of a different sequence of elements. The first element is
958 unchanged, because it resides in the @sc{car} of the list, and is not
959 reached via the @sc{cdr}.
976 You can delete elements from the middle of a list by altering the
977 @sc{cdr}s of the cons cells in the list. For example, here we delete
978 the second element, @code{b}, from the list @code{(a b c)}, by changing
979 the @sc{cdr} of the first cons cell:
985 (setcdr x1 (cdr (cdr x1)))
993 Here is the result in box notation:
999 -------------- | -------------- | --------------
1000 | car | cdr | | | car | cdr | -->| car | cdr |
1001 | a | o----- | b | o-------->| c | nil |
1003 -------------- -------------- --------------
1008 The second cons cell, which previously held the element @code{b}, still
1009 exists and its @sc{car} is still @code{b}, but it no longer forms part
1012 It is equally easy to insert a new element by changing @sc{cdr}s:
1018 (setcdr x1 (cons 'd (cdr x1)))
1025 Here is this result in box notation:
1029 -------------- ------------- -------------
1030 | car | cdr | | car | cdr | | car | cdr |
1031 | a | o | -->| b | o------->| c | nil |
1032 | | | | | | | | | | |
1033 --------- | -- | ------------- -------------
1046 @subsection Functions that Rearrange Lists
1047 @cindex rearrangement of lists
1048 @cindex modification of lists
1050 Here are some functions that rearrange lists ``destructively'' by
1051 modifying the @sc{cdr}s of their component cons cells. We call these
1052 functions ``destructive'' because they chew up the original lists passed
1053 to them as arguments, relinking their cons cells to form a new list that
1054 is the returned value.
1057 See @code{delq}, in @ref{Sets And Lists}, for another function
1058 that modifies cons cells.
1061 The function @code{delq} in the following section is another example
1062 of destructive list manipulation.
1065 @defun nconc &rest lists
1066 @cindex concatenating lists
1067 @cindex joining lists
1068 This function returns a list containing all the elements of @var{lists}.
1069 Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are
1070 @emph{not} copied. Instead, the last @sc{cdr} of each of the
1071 @var{lists} is changed to refer to the following list. The last of the
1072 @var{lists} is not altered. For example:
1081 @result{} (1 2 3 4 5)
1085 @result{} (1 2 3 4 5)
1089 Since the last argument of @code{nconc} is not itself modified, it is
1090 reasonable to use a constant list, such as @code{'(4 5)}, as in the
1091 above example. For the same reason, the last argument need not be a
1101 @result{} (1 2 3 . z)
1105 @result{} (1 2 3 . z)
1109 However, the other arguments (all but the last) must be lists.
1111 A common pitfall is to use a quoted constant list as a non-last
1112 argument to @code{nconc}. If you do this, your program will change
1113 each time you run it! Here is what happens:
1117 (defun add-foo (x) ; @r{We want this function to add}
1118 (nconc '(foo) x)) ; @r{@code{foo} to the front of its arg.}
1122 (symbol-function 'add-foo)
1123 @result{} (lambda (x) (nconc (quote (foo)) x))
1127 (setq xx (add-foo '(1 2))) ; @r{It seems to work.}
1131 (setq xy (add-foo '(3 4))) ; @r{What happened?}
1132 @result{} (foo 1 2 3 4)
1140 (symbol-function 'add-foo)
1141 @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x)))
1146 @defun nreverse list
1147 @cindex reversing a list
1148 This function reverses the order of the elements of @var{list}.
1149 Unlike @code{reverse}, @code{nreverse} alters its argument by reversing
1150 the @sc{cdr}s in the cons cells forming the list. The cons cell that
1151 used to be the last one in @var{list} becomes the first cons cell of the
1168 ;; @r{The cons cell that was first is now last.}
1174 To avoid confusion, we usually store the result of @code{nreverse}
1175 back in the same variable which held the original list:
1178 (setq x (nreverse x))
1181 Here is the @code{nreverse} of our favorite example, @code{(a b c)},
1182 presented graphically:
1186 @r{Original list head:} @r{Reversed list:}
1187 ------------- ------------- ------------
1188 | car | cdr | | car | cdr | | car | cdr |
1189 | a | nil |<-- | b | o |<-- | c | o |
1190 | | | | | | | | | | | | |
1191 ------------- | --------- | - | -------- | -
1193 ------------- ------------
1198 @defun sort list predicate
1200 @cindex sorting lists
1201 This function sorts @var{list} stably, though destructively, and
1202 returns the sorted list. It compares elements using @var{predicate}. A
1203 stable sort is one in which elements with equal sort keys maintain their
1204 relative order before and after the sort. Stability is important when
1205 successive sorts are used to order elements according to different
1208 The argument @var{predicate} must be a function that accepts two
1209 arguments. It is called with two elements of @var{list}. To get an
1210 increasing order sort, the @var{predicate} should return non-@code{nil} if the
1211 first element is ``less than'' the second, or @code{nil} if not.
1213 The comparison function @var{predicate} must give reliable results for
1214 any given pair of arguments, at least within a single call to
1215 @code{sort}. It must be @dfn{antisymmetric}; that is, if @var{a} is
1216 less than @var{b}, @var{b} must not be less than @var{a}. It must be
1217 @dfn{transitive}---that is, if @var{a} is less than @var{b}, and @var{b}
1218 is less than @var{c}, then @var{a} must be less than @var{c}. If you
1219 use a comparison function which does not meet these requirements, the
1220 result of @code{sort} is unpredictable.
1222 The destructive aspect of @code{sort} is that it rearranges the cons
1223 cells forming @var{list} by changing @sc{cdr}s. A nondestructive sort
1224 function would create new cons cells to store the elements in their
1225 sorted order. If you wish to make a sorted copy without destroying the
1226 original, copy it first with @code{copy-sequence} and then sort.
1228 Sorting does not change the @sc{car}s of the cons cells in @var{list};
1229 the cons cell that originally contained the element @code{a} in
1230 @var{list} still has @code{a} in its @sc{car} after sorting, but it now
1231 appears in a different position in the list due to the change of
1232 @sc{cdr}s. For example:
1236 (setq nums '(1 3 2 6 5 4 0))
1237 @result{} (1 3 2 6 5 4 0)
1241 @result{} (0 1 2 3 4 5 6)
1245 @result{} (1 2 3 4 5 6)
1250 @strong{Warning}: Note that the list in @code{nums} no longer contains
1251 0; this is the same cons cell that it was before, but it is no longer
1252 the first one in the list. Don't assume a variable that formerly held
1253 the argument now holds the entire sorted list! Instead, save the result
1254 of @code{sort} and use that. Most often we store the result back into
1255 the variable that held the original list:
1258 (setq nums (sort nums '<))
1261 @xref{Sorting}, for more functions that perform sorting.
1262 See @code{documentation} in @ref{Accessing Documentation}, for a
1263 useful example of @code{sort}.
1266 @node Sets And Lists
1267 @section Using Lists as Sets
1268 @cindex lists as sets
1271 A list can represent an unordered mathematical set---simply consider a
1272 value an element of a set if it appears in the list, and ignore the
1273 order of the list. To form the union of two sets, use @code{append} (as
1274 long as you don't mind having duplicate elements). You can remove
1275 @code{equal} duplicates using @code{delete-dups}. Other useful
1276 functions for sets include @code{memq} and @code{delq}, and their
1277 @code{equal} versions, @code{member} and @code{delete}.
1279 @cindex CL note---lack @code{union}, @code{intersection}
1281 @b{Common Lisp note:} Common Lisp has functions @code{union} (which
1282 avoids duplicate elements) and @code{intersection} for set operations,
1283 but GNU Emacs Lisp does not have them. You can write them in Lisp if
1287 @defun memq object list
1288 @cindex membership in a list
1289 This function tests to see whether @var{object} is a member of
1290 @var{list}. If it is, @code{memq} returns a list starting with the
1291 first occurrence of @var{object}. Otherwise, it returns @code{nil}.
1292 The letter @samp{q} in @code{memq} says that it uses @code{eq} to
1293 compare @var{object} against the elements of the list. For example:
1297 (memq 'b '(a b c b a))
1301 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1307 @defun delq object list
1308 @cindex deletion of elements
1309 This function destructively removes all elements @code{eq} to
1310 @var{object} from @var{list}. The letter @samp{q} in @code{delq} says
1311 that it uses @code{eq} to compare @var{object} against the elements of
1312 the list, like @code{memq} and @code{remq}.
1315 When @code{delq} deletes elements from the front of the list, it does so
1316 simply by advancing down the list and returning a sublist that starts
1317 after those elements:
1321 (delq 'a '(a b c)) @equiv{} (cdr '(a b c))
1325 When an element to be deleted appears in the middle of the list,
1326 removing it involves changing the @sc{cdr}s (@pxref{Setcdr}).
1330 (setq sample-list '(a b c (4)))
1331 @result{} (a b c (4))
1334 (delq 'a sample-list)
1339 @result{} (a b c (4))
1342 (delq 'c sample-list)
1351 Note that @code{(delq 'c sample-list)} modifies @code{sample-list} to
1352 splice out the third element, but @code{(delq 'a sample-list)} does not
1353 splice anything---it just returns a shorter list. Don't assume that a
1354 variable which formerly held the argument @var{list} now has fewer
1355 elements, or that it still holds the original list! Instead, save the
1356 result of @code{delq} and use that. Most often we store the result back
1357 into the variable that held the original list:
1360 (setq flowers (delq 'rose flowers))
1363 In the following example, the @code{(4)} that @code{delq} attempts to match
1364 and the @code{(4)} in the @code{sample-list} are not @code{eq}:
1368 (delq '(4) sample-list)
1373 @defun remq object list
1374 This function returns a copy of @var{list}, with all elements removed
1375 which are @code{eq} to @var{object}. The letter @samp{q} in @code{remq}
1376 says that it uses @code{eq} to compare @var{object} against the elements
1381 (setq sample-list '(a b c a b c))
1382 @result{} (a b c a b c)
1385 (remq 'a sample-list)
1390 @result{} (a b c a b c)
1394 The function @code{delq} offers a way to perform this operation
1395 destructively. See @ref{Sets And Lists}.
1398 @defun memql object list
1399 The function @code{member} tests to see whether @var{object} is a member
1400 of @var{list}, comparing members with @var{object} using @code{eql},
1401 so floating point elements are compared by value.
1402 If @var{object} is a member, @code{memql} returns a list starting with
1403 its first occurrence in @var{list}. Otherwise, it returns @code{nil}.
1405 Compare this with @code{memq}:
1409 (memql 1.2 '(1.1 1.2 1.3) ; @r{@code{1.2} and @code{1.2} are @code{eql}.}
1413 (memq 1.2 '(1.1 1.2 1.3) ; @r{@code{1.2} and @code{1.2} are not @code{eq}.}
1419 The following three functions are like @code{memq}, @code{delq} and
1420 @code{remq}, but use @code{equal} rather than @code{eq} to compare
1421 elements. @xref{Equality Predicates}.
1423 @defun member object list
1424 The function @code{member} tests to see whether @var{object} is a member
1425 of @var{list}, comparing members with @var{object} using @code{equal}.
1426 If @var{object} is a member, @code{member} returns a list starting with
1427 its first occurrence in @var{list}. Otherwise, it returns @code{nil}.
1429 Compare this with @code{memq}:
1433 (member '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are @code{equal}.}
1437 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1441 ;; @r{Two strings with the same contents are @code{equal}.}
1442 (member "foo" '("foo" "bar"))
1443 @result{} ("foo" "bar")
1448 @defun delete object sequence
1449 If @code{sequence} is a list, this function destructively removes all
1450 elements @code{equal} to @var{object} from @var{sequence}. For lists,
1451 @code{delete} is to @code{delq} as @code{member} is to @code{memq}: it
1452 uses @code{equal} to compare elements with @var{object}, like
1453 @code{member}; when it finds an element that matches, it removes the
1454 element just as @code{delq} would.
1456 If @code{sequence} is a vector or string, @code{delete} returns a copy
1457 of @code{sequence} with all elements @code{equal} to @code{object}
1464 (delete '(2) '((2) (1) (2)))
1468 (delete '(2) [(2) (1) (2)])
1474 @defun remove object sequence
1475 This function is the non-destructive counterpart of @code{delete}. If
1476 returns a copy of @code{sequence}, a list, vector, or string, with
1477 elements @code{equal} to @code{object} removed. For example:
1481 (remove '(2) '((2) (1) (2)))
1485 (remove '(2) [(2) (1) (2)])
1492 @b{Common Lisp note:} The functions @code{member}, @code{delete} and
1493 @code{remove} in GNU Emacs Lisp are derived from Maclisp, not Common
1494 Lisp. The Common Lisp versions do not use @code{equal} to compare
1498 @defun member-ignore-case object list
1499 This function is like @code{member}, except that @var{object} should
1500 be a string and that it ignores differences in letter-case and text
1501 representation: upper-case and lower-case letters are treated as
1502 equal, and unibyte strings are converted to multibyte prior to
1506 @defun delete-dups list
1507 This function destructively removes all @code{equal} duplicates from
1508 @var{list}, stores the result in @var{list} and returns it. Of
1509 several @code{equal} occurrences of an element in @var{list},
1510 @code{delete-dups} keeps the first one.
1513 See also the function @code{add-to-list}, in @ref{List Variables},
1514 for another way to add an element to a list stored in a variable.
1516 @node Association Lists
1517 @section Association Lists
1518 @cindex association list
1521 An @dfn{association list}, or @dfn{alist} for short, records a mapping
1522 from keys to values. It is a list of cons cells called
1523 @dfn{associations}: the @sc{car} of each cons cell is the @dfn{key}, and the
1524 @sc{cdr} is the @dfn{associated value}.@footnote{This usage of ``key''
1525 is not related to the term ``key sequence''; it means a value used to
1526 look up an item in a table. In this case, the table is the alist, and
1527 the alist associations are the items.}
1529 Here is an example of an alist. The key @code{pine} is associated with
1530 the value @code{cones}; the key @code{oak} is associated with
1531 @code{acorns}; and the key @code{maple} is associated with @code{seeds}.
1541 Both the values and the keys in an alist may be any Lisp objects.
1542 For example, in the following alist, the symbol @code{a} is
1543 associated with the number @code{1}, and the string @code{"b"} is
1544 associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of
1551 Sometimes it is better to design an alist to store the associated
1552 value in the @sc{car} of the @sc{cdr} of the element. Here is an
1553 example of such an alist:
1556 ((rose red) (lily white) (buttercup yellow))
1560 Here we regard @code{red} as the value associated with @code{rose}. One
1561 advantage of this kind of alist is that you can store other related
1562 information---even a list of other items---in the @sc{cdr} of the
1563 @sc{cdr}. One disadvantage is that you cannot use @code{rassq} (see
1564 below) to find the element containing a given value. When neither of
1565 these considerations is important, the choice is a matter of taste, as
1566 long as you are consistent about it for any given alist.
1568 The same alist shown above could be regarded as having the
1569 associated value in the @sc{cdr} of the element; the value associated
1570 with @code{rose} would be the list @code{(red)}.
1572 Association lists are often used to record information that you might
1573 otherwise keep on a stack, since new associations may be added easily to
1574 the front of the list. When searching an association list for an
1575 association with a given key, the first one found is returned, if there
1578 In Emacs Lisp, it is @emph{not} an error if an element of an
1579 association list is not a cons cell. The alist search functions simply
1580 ignore such elements. Many other versions of Lisp signal errors in such
1583 Note that property lists are similar to association lists in several
1584 respects. A property list behaves like an association list in which
1585 each key can occur only once. @xref{Property Lists}, for a comparison
1586 of property lists and association lists.
1588 @defun assoc key alist
1589 This function returns the first association for @var{key} in
1590 @var{alist}. It compares @var{key} against the alist elements using
1591 @code{equal} (@pxref{Equality Predicates}). It returns @code{nil} if no
1592 association in @var{alist} has a @sc{car} @code{equal} to @var{key}.
1596 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1597 @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1599 @result{} (oak . acorns)
1600 (cdr (assoc 'oak trees))
1602 (assoc 'birch trees)
1606 Here is another example, in which the keys and values are not symbols:
1609 (setq needles-per-cluster
1610 '((2 "Austrian Pine" "Red Pine")
1614 (cdr (assoc 3 needles-per-cluster))
1615 @result{} ("Pitch Pine")
1616 (cdr (assoc 2 needles-per-cluster))
1617 @result{} ("Austrian Pine" "Red Pine")
1621 The function @code{assoc-string} is much like @code{assoc} except
1622 that it ignores certain differences between strings. @xref{Text
1625 @defun rassoc value alist
1626 This function returns the first association with value @var{value} in
1627 @var{alist}. It returns @code{nil} if no association in @var{alist} has
1628 a @sc{cdr} @code{equal} to @var{value}.
1630 @code{rassoc} is like @code{assoc} except that it compares the @sc{cdr} of
1631 each @var{alist} association instead of the @sc{car}. You can think of
1632 this as ``reverse @code{assoc},'' finding the key for a given value.
1635 @defun assq key alist
1636 This function is like @code{assoc} in that it returns the first
1637 association for @var{key} in @var{alist}, but it makes the comparison
1638 using @code{eq} instead of @code{equal}. @code{assq} returns @code{nil}
1639 if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}.
1640 This function is used more often than @code{assoc}, since @code{eq} is
1641 faster than @code{equal} and most alists use symbols as keys.
1642 @xref{Equality Predicates}.
1645 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1646 @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1648 @result{} (pine . cones)
1651 On the other hand, @code{assq} is not usually useful in alists where the
1652 keys may not be symbols:
1656 '(("simple leaves" . oak)
1657 ("compound leaves" . horsechestnut)))
1659 (assq "simple leaves" leaves)
1661 (assoc "simple leaves" leaves)
1662 @result{} ("simple leaves" . oak)
1666 @defun rassq value alist
1667 This function returns the first association with value @var{value} in
1668 @var{alist}. It returns @code{nil} if no association in @var{alist} has
1669 a @sc{cdr} @code{eq} to @var{value}.
1671 @code{rassq} is like @code{assq} except that it compares the @sc{cdr} of
1672 each @var{alist} association instead of the @sc{car}. You can think of
1673 this as ``reverse @code{assq},'' finding the key for a given value.
1678 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1680 (rassq 'acorns trees)
1681 @result{} (oak . acorns)
1682 (rassq 'spores trees)
1686 @code{rassq} cannot search for a value stored in the @sc{car}
1687 of the @sc{cdr} of an element:
1690 (setq colors '((rose red) (lily white) (buttercup yellow)))
1692 (rassq 'white colors)
1696 In this case, the @sc{cdr} of the association @code{(lily white)} is not
1697 the symbol @code{white}, but rather the list @code{(white)}. This
1698 becomes clearer if the association is written in dotted pair notation:
1701 (lily white) @equiv{} (lily . (white))
1705 @defun assoc-default key alist &optional test default
1706 This function searches @var{alist} for a match for @var{key}. For each
1707 element of @var{alist}, it compares the element (if it is an atom) or
1708 the element's @sc{car} (if it is a cons) against @var{key}, by calling
1709 @var{test} with two arguments: the element or its @sc{car}, and
1710 @var{key}. The arguments are passed in that order so that you can get
1711 useful results using @code{string-match} with an alist that contains
1712 regular expressions (@pxref{Regexp Search}). If @var{test} is omitted
1713 or @code{nil}, @code{equal} is used for comparison.
1715 If an alist element matches @var{key} by this criterion,
1716 then @code{assoc-default} returns a value based on this element.
1717 If the element is a cons, then the value is the element's @sc{cdr}.
1718 Otherwise, the return value is @var{default}.
1720 If no alist element matches @var{key}, @code{assoc-default} returns
1724 @defun copy-alist alist
1725 @cindex copying alists
1726 This function returns a two-level deep copy of @var{alist}: it creates a
1727 new copy of each association, so that you can alter the associations of
1728 the new alist without changing the old one.
1732 (setq needles-per-cluster
1733 '((2 . ("Austrian Pine" "Red Pine"))
1734 (3 . ("Pitch Pine"))
1736 (5 . ("White Pine"))))
1738 ((2 "Austrian Pine" "Red Pine")
1742 (setq copy (copy-alist needles-per-cluster))
1744 ((2 "Austrian Pine" "Red Pine")
1748 (eq needles-per-cluster copy)
1750 (equal needles-per-cluster copy)
1752 (eq (car needles-per-cluster) (car copy))
1754 (cdr (car (cdr needles-per-cluster)))
1755 @result{} ("Pitch Pine")
1757 (eq (cdr (car (cdr needles-per-cluster)))
1758 (cdr (car (cdr copy))))
1763 This example shows how @code{copy-alist} makes it possible to change
1764 the associations of one copy without affecting the other:
1768 (setcdr (assq 3 copy) '("Martian Vacuum Pine"))
1769 (cdr (assq 3 needles-per-cluster))
1770 @result{} ("Pitch Pine")
1775 @defun assq-delete-all key alist
1776 This function deletes from @var{alist} all the elements whose @sc{car}
1777 is @code{eq} to @var{key}, much as if you used @code{delq} to delete
1778 each such element one by one. It returns the shortened alist, and
1779 often modifies the original list structure of @var{alist}. For
1780 correct results, use the return value of @code{assq-delete-all} rather
1781 than looking at the saved value of @var{alist}.
1784 (setq alist '((foo 1) (bar 2) (foo 3) (lose 4)))
1785 @result{} ((foo 1) (bar 2) (foo 3) (lose 4))
1786 (assq-delete-all 'foo alist)
1787 @result{} ((bar 2) (lose 4))
1789 @result{} ((foo 1) (bar 2) (lose 4))
1793 @defun rassq-delete-all value alist
1794 This function deletes from @var{alist} all the elements whose @sc{cdr}
1795 is @code{eq} to @var{value}. It returns the shortened alist, and
1796 often modifies the original list structure of @var{alist}.
1797 @code{rassq-delete-all} is like @code{assq-delete-all} except that it
1798 compares the @sc{cdr} of each @var{alist} association instead of the
1803 @section Managing a Fixed-Size Ring of Objects
1805 @cindex ring data structure
1806 This section describes functions for operating on rings. A
1807 @dfn{ring} is a fixed-size data structure that supports insertion,
1808 deletion, rotation, and modulo-indexed reference and traversal.
1810 @defun make-ring size
1811 This returns a new ring capable of holding @var{size} objects.
1812 @var{size} should be an integer.
1815 @defun ring-p object
1816 This returns @code{t} if @var{object} is a ring, @code{nil} otherwise.
1819 @defun ring-size ring
1820 This returns the maximum capacity of the @var{ring}.
1823 @defun ring-length ring
1824 This returns the number of objects that @var{ring} currently contains.
1825 The value will never exceed that returned by @code{ring-size}.
1828 @defun ring-elements ring
1829 This returns a list of the objects in @var{ring}, in order, newest first.
1832 @defun ring-copy ring
1833 This returns a new ring which is a copy of @var{ring}.
1834 The new ring contains the same (@code{eq}) objects as @var{ring}.
1837 @defun ring-empty-p ring
1838 This returns @code{t} if @var{ring} is empty, @code{nil} otherwise.
1841 The newest element in the ring always has index 0. Higher indices
1842 correspond to older elements. Indices are computed modulo the ring
1843 length. Index @minus{}1 corresponds to the oldest element, @minus{}2
1844 to the next-oldest, and so forth.
1846 @defun ring-ref ring index
1847 This returns the object in @var{ring} found at index @var{index}.
1848 @var{index} may be negative or greater than the ring length. If
1849 @var{ring} is empty, @code{ring-ref} signals an error.
1852 @defun ring-insert ring object
1853 This inserts @var{object} into @var{ring}, making it the newest
1854 element, and returns @var{object}.
1856 If the ring is full, insertion removes the oldest element to
1857 make room for the new element.
1860 @defun ring-remove ring &optional index
1861 Remove an object from @var{ring}, and return that object. The
1862 argument @var{index} specifies which item to remove; if it is
1863 @code{nil}, that means to remove the oldest item. If @var{ring} is
1864 empty, @code{ring-remove} signals an error.
1867 @defun ring-insert-at-beginning ring object
1868 This inserts @var{object} into @var{ring}, treating it as the oldest
1869 element. The return value is not significant.
1871 If the ring is full, this function removes the newest element to make
1872 room for the inserted element.
1875 @cindex fifo data structure
1876 If you are careful not to exceed the ring size, you can
1877 use the ring as a first-in-first-out queue. For example:
1880 (let ((fifo (make-ring 5)))
1881 (mapc (lambda (obj) (ring-insert fifo obj))
1883 (list (ring-remove fifo) t
1884 (ring-remove fifo) t
1885 (ring-remove fifo)))
1886 @result{} (0 t one t "two")
1890 arch-tag: 31fb8a4e-4aa8-4a74-a206-aa00451394d4