2 @c This is part of the GNU Emacs Lisp Reference Manual.
3 @c Copyright (C) 1990-1995, 1998-1999, 2001-2012 Free Software Foundation, Inc.
4 @c See the file elisp.texi for copying conditions.
8 @cindex element (of list)
10 A @dfn{list} represents a sequence of zero or more elements (which may
11 be any Lisp objects). The important difference between lists and
12 vectors is that two or more lists can share part of their structure; in
13 addition, you can insert or delete elements in a list without copying
17 * Cons Cells:: How lists are made out of cons cells.
18 * List-related Predicates:: Is this object a list? Comparing two lists.
19 * List Elements:: Extracting the pieces of a list.
20 * Building Lists:: Creating list structure.
21 * List Variables:: Modifying lists stored in variables.
22 * Modifying Lists:: Storing new pieces into an existing list.
23 * Sets And Lists:: A list can represent a finite mathematical set.
24 * Association Lists:: A list can represent a finite relation or mapping.
28 @section Lists and Cons Cells
29 @cindex lists and cons cells
31 Lists in Lisp are not a primitive data type; they are built up from
32 @dfn{cons cells} (@pxref{Cons Cell Type}). A cons cell is a data
33 object that represents an ordered pair. That is, it has two slots,
34 and each slot @dfn{holds}, or @dfn{refers to}, some Lisp object. One
35 slot is known as the @sc{car}, and the other is known as the @sc{cdr}.
36 (These names are traditional; see @ref{Cons Cell Type}.) @sc{cdr} is
37 pronounced ``could-er''.
39 We say that ``the @sc{car} of this cons cell is'' whatever object
40 its @sc{car} slot currently holds, and likewise for the @sc{cdr}.
42 A list is a series of cons cells ``chained together'', so that each
43 cell refers to the next one. There is one cons cell for each element
44 of the list. By convention, the @sc{car}s of the cons cells hold the
45 elements of the list, and the @sc{cdr}s are used to chain the list
46 (this asymmetry between @sc{car} and @sc{cdr} is entirely a matter of
47 convention; at the level of cons cells, the @sc{car} and @sc{cdr}
48 slots have similar properties). Hence, the @sc{cdr} slot of each cons
49 cell in a list refers to the following cons cell.
52 Also by convention, the @sc{cdr} of the last cons cell in a list is
53 @code{nil}. We call such a @code{nil}-terminated structure a
54 @dfn{true list}. In Emacs Lisp, the symbol @code{nil} is both a
55 symbol and a list with no elements. For convenience, the symbol
56 @code{nil} is considered to have @code{nil} as its @sc{cdr} (and also
59 Hence, the @sc{cdr} of a true list is always a true list. The
60 @sc{cdr} of a nonempty true list is a true list containing all the
61 elements except the first.
65 If the @sc{cdr} of a list's last cons cell is some value other than
66 @code{nil}, we call the structure a @dfn{dotted list}, since its
67 printed representation would use dotted pair notation (@pxref{Dotted
68 Pair Notation}). There is one other possibility: some cons cell's
69 @sc{cdr} could point to one of the previous cons cells in the list.
70 We call that structure a @dfn{circular list}.
72 For some purposes, it does not matter whether a list is true,
73 circular or dotted. If a 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, we refer to any
81 structure made out of cons cells as a @dfn{list structure}.
83 @node List-related Predicates
84 @section Predicates on Lists
86 The following predicates test whether a Lisp object is an atom,
87 whether it is a cons cell or is a list, or whether it is the
88 distinguished object @code{nil}. (Many of these predicates can be
89 defined in terms of the others, but they are used so often that it is
93 This function returns @code{t} if @var{object} is a cons cell, @code{nil}
94 otherwise. @code{nil} is not a cons cell, although it @emph{is} a list.
98 This function returns @code{t} if @var{object} is an atom, @code{nil}
99 otherwise. All objects except cons cells are atoms. The symbol
100 @code{nil} is an atom and is also a list; it is the only Lisp object
104 (atom @var{object}) @equiv{} (not (consp @var{object}))
109 This function returns @code{t} if @var{object} is a cons cell or
110 @code{nil}. Otherwise, it returns @code{nil}.
125 This function is the opposite of @code{listp}: it returns @code{t} if
126 @var{object} is not a list. Otherwise, it returns @code{nil}.
129 (listp @var{object}) @equiv{} (not (nlistp @var{object}))
134 This function returns @code{t} if @var{object} is @code{nil}, and
135 returns @code{nil} otherwise. This function is identical to @code{not},
136 but as a matter of clarity we use @code{null} when @var{object} is
137 considered a list and @code{not} when it is considered a truth value
138 (see @code{not} in @ref{Combining Conditions}).
154 @section Accessing Elements of Lists
155 @cindex list elements
158 This function returns the value referred to by the first slot of the
159 cons cell @var{cons-cell}. In other words, it returns the @sc{car} of
162 As a special case, if @var{cons-cell} is @code{nil}, this function
163 returns @code{nil}. Therefore, any list is a valid argument. An
164 error is signaled if the argument is not a cons cell or @code{nil}.
179 This function returns the value referred to by the second slot of the
180 cons cell @var{cons-cell}. In other words, it returns the @sc{cdr} of
183 As a special case, if @var{cons-cell} is @code{nil}, this function
184 returns @code{nil}; therefore, any list is a valid argument. An error
185 is signaled if the argument is not a cons cell or @code{nil}.
199 @defun car-safe object
200 This function lets you take the @sc{car} of a cons cell while avoiding
201 errors for other data types. It returns the @sc{car} of @var{object} if
202 @var{object} is a cons cell, @code{nil} otherwise. This is in contrast
203 to @code{car}, which signals an error if @var{object} is not a list.
207 (car-safe @var{object})
209 (let ((x @var{object}))
217 @defun cdr-safe object
218 This function lets you take the @sc{cdr} of a cons cell while
219 avoiding errors for other data types. It returns the @sc{cdr} of
220 @var{object} if @var{object} is a cons cell, @code{nil} otherwise.
221 This is in contrast to @code{cdr}, which signals an error if
222 @var{object} is not a list.
226 (cdr-safe @var{object})
228 (let ((x @var{object}))
237 This macro provides a convenient way to examine the @sc{car} of a
238 list, and take it off the list, all at once. It operates on the list
239 stored in @var{listname}. It removes the first element from the list,
240 saves the @sc{cdr} into @var{listname}, then returns the removed
243 In the simplest case, @var{listname} is an unquoted symbol naming a
244 list; in that case, this macro is equivalent to @w{@code{(prog1
245 (car listname) (setq listname (cdr listname)))}}.
256 More generally, @var{listname} can be a generalized variable. In that
257 case, this macro saves into @var{listname} using @code{setf}.
258 @xref{Generalized Variables}.
260 For the @code{push} macro, which adds an element to a list,
261 @xref{List Variables}.
265 @anchor{Definition of nth}
266 This function returns the @var{n}th element of @var{list}. Elements
267 are numbered starting with zero, so the @sc{car} of @var{list} is
268 element number zero. If the length of @var{list} is @var{n} or less,
269 the value is @code{nil}.
271 If @var{n} is negative, @code{nth} returns the first element of
287 (nth n x) @equiv{} (car (nthcdr n x))
291 The function @code{elt} is similar, but applies to any kind of sequence.
292 For historical reasons, it takes its arguments in the opposite order.
293 @xref{Sequence Functions}.
297 This function returns the @var{n}th @sc{cdr} of @var{list}. In other
298 words, it skips past the first @var{n} links of @var{list} and returns
301 If @var{n} is zero or negative, @code{nthcdr} returns all of
302 @var{list}. If the length of @var{list} is @var{n} or less,
303 @code{nthcdr} returns @code{nil}.
307 (nthcdr 1 '(1 2 3 4))
311 (nthcdr 10 '(1 2 3 4))
315 (nthcdr -3 '(1 2 3 4))
321 @defun last list &optional n
322 This function returns the last link of @var{list}. The @code{car} of
323 this link is the list's last element. If @var{list} is null,
324 @code{nil} is returned. If @var{n} is non-@code{nil}, the
325 @var{n}th-to-last link is returned instead, or the whole of @var{list}
326 if @var{n} is bigger than @var{list}'s length.
329 @defun safe-length list
330 @anchor{Definition of safe-length}
331 This function returns the length of @var{list}, with no risk of either
332 an error or an infinite loop. It generally returns the number of
333 distinct cons cells in the list. However, for circular lists,
334 the value is just an upper bound; it is often too large.
336 If @var{list} is not @code{nil} or a cons cell, @code{safe-length}
340 The most common way to compute the length of a list, when you are not
341 worried that it may be circular, is with @code{length}. @xref{Sequence
344 @defun caar cons-cell
345 This is the same as @code{(car (car @var{cons-cell}))}.
348 @defun cadr cons-cell
349 This is the same as @code{(car (cdr @var{cons-cell}))}
350 or @code{(nth 1 @var{cons-cell})}.
353 @defun cdar cons-cell
354 This is the same as @code{(cdr (car @var{cons-cell}))}.
357 @defun cddr cons-cell
358 This is the same as @code{(cdr (cdr @var{cons-cell}))}
359 or @code{(nthcdr 2 @var{cons-cell})}.
362 @defun butlast x &optional n
363 This function returns the list @var{x} with the last element,
364 or the last @var{n} elements, removed. If @var{n} is greater
365 than zero it makes a copy of the list so as not to damage the
366 original list. In general, @code{(append (butlast @var{x} @var{n})
367 (last @var{x} @var{n}))} will return a list equal to @var{x}.
370 @defun nbutlast x &optional n
371 This is a version of @code{butlast} that works by destructively
372 modifying the @code{cdr} of the appropriate element, rather than
373 making a copy of the list.
377 @section Building Cons Cells and Lists
379 @cindex building lists
381 Many functions build lists, as lists reside at the very heart of Lisp.
382 @code{cons} is the fundamental list-building function; however, it is
383 interesting to note that @code{list} is used more times in the source
384 code for Emacs than @code{cons}.
386 @defun cons object1 object2
387 This function is the most basic function for building new list
388 structure. It creates a new cons cell, making @var{object1} the
389 @sc{car}, and @var{object2} the @sc{cdr}. It then returns the new
390 cons cell. The arguments @var{object1} and @var{object2} may be any
391 Lisp objects, but most often @var{object2} is a list.
409 @code{cons} is often used to add a single element to the front of a
410 list. This is called @dfn{consing the element onto the list}.
411 @footnote{There is no strictly equivalent way to add an element to
412 the end of a list. You can use @code{(append @var{listname} (list
413 @var{newelt}))}, which creates a whole new list by copying @var{listname}
414 and adding @var{newelt} to its end. Or you can use @code{(nconc
415 @var{listname} (list @var{newelt}))}, which modifies @var{listname}
416 by following all the @sc{cdr}s and then replacing the terminating
417 @code{nil}. Compare this to adding an element to the beginning of a
418 list with @code{cons}, which neither copies nor modifies the list.}
422 (setq list (cons newelt list))
425 Note that there is no conflict between the variable named @code{list}
426 used in this example and the function named @code{list} described below;
427 any symbol can serve both purposes.
430 @defun list &rest objects
431 This function creates a list with @var{objects} as its elements. The
432 resulting list is always @code{nil}-terminated. If no @var{objects}
433 are given, the empty list is returned.
438 @result{} (1 2 3 4 5)
441 (list 1 2 '(3 4 5) 'foo)
442 @result{} (1 2 (3 4 5) foo)
451 @defun make-list length object
452 This function creates a list of @var{length} elements, in which each
453 element is @var{object}. Compare @code{make-list} with
454 @code{make-string} (@pxref{Creating Strings}).
459 @result{} (pigs pigs pigs)
466 (setq l (make-list 3 '(a b)))
467 @result{} ((a b) (a b) (a b))
468 (eq (car l) (cadr l))
474 @defun append &rest sequences
475 @cindex copying lists
476 This function returns a list containing all the elements of
477 @var{sequences}. The @var{sequences} may be lists, vectors,
478 bool-vectors, or strings, but the last one should usually be a list.
479 All arguments except the last one are copied, so none of the arguments
480 is altered. (See @code{nconc} in @ref{Rearrangement}, for a way to join
481 lists with no copying.)
483 More generally, the final argument to @code{append} may be any Lisp
484 object. The final argument is not copied or converted; it becomes the
485 @sc{cdr} of the last cons cell in the new list. If the final argument
486 is itself a list, then its elements become in effect elements of the
487 result list. If the final element is not a list, the result is a
488 dotted list since its final @sc{cdr} is not @code{nil} as required
492 Here is an example of using @code{append}:
496 (setq trees '(pine oak))
498 (setq more-trees (append '(maple birch) trees))
499 @result{} (maple birch pine oak)
506 @result{} (maple birch pine oak)
509 (eq trees (cdr (cdr more-trees)))
514 You can see how @code{append} works by looking at a box diagram. The
515 variable @code{trees} is set to the list @code{(pine oak)} and then the
516 variable @code{more-trees} is set to the list @code{(maple birch pine
517 oak)}. However, the variable @code{trees} continues to refer to the
524 | --- --- --- --- -> --- --- --- ---
525 --> | | |--> | | |--> | | |--> | | |--> nil
526 --- --- --- --- --- --- --- ---
529 --> maple -->birch --> pine --> oak
533 An empty sequence contributes nothing to the value returned by
534 @code{append}. As a consequence of this, a final @code{nil} argument
535 forces a copy of the previous argument:
543 (setq wood (append trees nil))
557 This once was the usual way to copy a list, before the function
558 @code{copy-sequence} was invented. @xref{Sequences Arrays Vectors}.
560 Here we show the use of vectors and strings as arguments to @code{append}:
564 (append [a b] "cd" nil)
565 @result{} (a b 99 100)
569 With the help of @code{apply} (@pxref{Calling Functions}), we can append
570 all the lists in a list of lists:
574 (apply 'append '((a b c) nil (x y z) nil))
575 @result{} (a b c x y z)
579 If no @var{sequences} are given, @code{nil} is returned:
588 Here are some examples where the final argument is not a list:
594 @result{} (x y . [z])
598 The second example shows that when the final argument is a sequence but
599 not a list, the sequence's elements do not become elements of the
600 resulting list. Instead, the sequence becomes the final @sc{cdr}, like
601 any other non-list final argument.
604 This function creates a new list whose elements are the elements of
605 @var{list}, but in reverse order. The original argument @var{list} is
622 @defun copy-tree tree &optional vecp
623 This function returns a copy of the tree @code{tree}. If @var{tree} is a
624 cons cell, this makes a new cons cell with the same @sc{car} and
625 @sc{cdr}, then recursively copies the @sc{car} and @sc{cdr} in the
628 Normally, when @var{tree} is anything other than a cons cell,
629 @code{copy-tree} simply returns @var{tree}. However, if @var{vecp} is
630 non-@code{nil}, it copies vectors too (and operates recursively on
634 @defun number-sequence from &optional to separation
635 This returns a list of numbers starting with @var{from} and
636 incrementing by @var{separation}, and ending at or just before
637 @var{to}. @var{separation} can be positive or negative and defaults
638 to 1. If @var{to} is @code{nil} or numerically equal to @var{from},
639 the value is the one-element list @code{(@var{from})}. If @var{to} is
640 less than @var{from} with a positive @var{separation}, or greater than
641 @var{from} with a negative @var{separation}, the value is @code{nil}
642 because those arguments specify an empty sequence.
644 If @var{separation} is 0 and @var{to} is neither @code{nil} nor
645 numerically equal to @var{from}, @code{number-sequence} signals an
646 error, since those arguments specify an infinite sequence.
648 All arguments can be integers or floating point numbers. However,
649 floating point arguments can be tricky, because floating point
650 arithmetic is inexact. For instance, depending on the machine, it may
651 quite well happen that @code{(number-sequence 0.4 0.6 0.2)} returns
652 the one element list @code{(0.4)}, whereas
653 @code{(number-sequence 0.4 0.8 0.2)} returns a list with three
654 elements. The @var{n}th element of the list is computed by the exact
655 formula @code{(+ @var{from} (* @var{n} @var{separation}))}. Thus, if
656 one wants to make sure that @var{to} is included in the list, one can
657 pass an expression of this exact type for @var{to}. Alternatively,
658 one can replace @var{to} with a slightly larger value (or a slightly
659 more negative value if @var{separation} is negative).
664 (number-sequence 4 9)
665 @result{} (4 5 6 7 8 9)
666 (number-sequence 9 4 -1)
667 @result{} (9 8 7 6 5 4)
668 (number-sequence 9 4 -2)
672 (number-sequence 8 5)
674 (number-sequence 5 8 -1)
676 (number-sequence 1.5 6 2)
677 @result{} (1.5 3.5 5.5)
682 @section Modifying List Variables
684 These functions, and one macro, provide convenient ways
685 to modify a list which is stored in a variable.
687 @defmac push element listname
688 This macro creates a new list whose @sc{car} is @var{element} and
689 whose @sc{cdr} is the list specified by @var{listname}, and saves that
690 list in @var{listname}. In the simplest case, @var{listname} is an
691 unquoted symbol naming a list, and this macro is equivalent
692 to @w{@code{(setq @var{listname} (cons @var{element} @var{listname}))}}.
703 More generally, @code{listname} can be a generalized variable. In
704 that case, this macro does the equivalent of @w{@code{(setf
705 @var{listname} (cons @var{element} @var{listname}))}}.
706 @xref{Generalized Variables}.
708 For the @code{pop} macro, which removes the first element from a list,
709 @xref{List Elements}.
712 Two functions modify lists that are the values of variables.
714 @defun add-to-list symbol element &optional append compare-fn
715 This function sets the variable @var{symbol} by consing @var{element}
716 onto the old value, if @var{element} is not already a member of that
717 value. It returns the resulting list, whether updated or not. The
718 value of @var{symbol} had better be a list already before the call.
719 @code{add-to-list} uses @var{compare-fn} to compare @var{element}
720 against existing list members; if @var{compare-fn} is @code{nil}, it
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 necessary.
779 The ordering information is stored in a hash table on @var{symbol}'s
780 @code{list-order} property.
783 Here's a scenario showing how to use @code{add-to-ordered-list}:
789 (add-to-ordered-list 'foo 'a 1) ;; @r{Add @code{a}.}
792 (add-to-ordered-list 'foo 'c 3) ;; @r{Add @code{c}.}
795 (add-to-ordered-list 'foo 'b 2) ;; @r{Add @code{b}.}
798 (add-to-ordered-list 'foo 'b 4) ;; @r{Move @code{b}.}
801 (add-to-ordered-list 'foo 'd) ;; @r{Append @code{d}.}
804 (add-to-ordered-list 'foo 'e) ;; @r{Add @code{e}}.
805 @result{} (a c b e d)
807 foo ;; @r{@code{foo} was changed.}
808 @result{} (a c b e d)
811 @node Modifying Lists
812 @section Modifying Existing List Structure
813 @cindex destructive list operations
815 You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the
816 primitives @code{setcar} and @code{setcdr}. We call these ``destructive''
817 operations because they change existing list structure.
819 @cindex CL note---@code{rplaca} vs @code{setcar}
823 @b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and
824 @code{rplacd} to alter list structure; they change structure the same
825 way as @code{setcar} and @code{setcdr}, but the Common Lisp functions
826 return the cons cell while @code{setcar} and @code{setcdr} return the
827 new @sc{car} or @sc{cdr}.
831 * Setcar:: Replacing an element in a list.
832 * Setcdr:: Replacing part of the list backbone.
833 This can be used to remove or add elements.
834 * Rearrangement:: Reordering the elements in a list; combining lists.
838 @subsection Altering List Elements with @code{setcar}
840 Changing the @sc{car} of a cons cell is done with @code{setcar}. When
841 used on a list, @code{setcar} replaces one element of a list with a
844 @defun setcar cons object
845 This function stores @var{object} as the new @sc{car} of @var{cons},
846 replacing its previous @sc{car}. In other words, it changes the
847 @sc{car} slot of @var{cons} to refer to @var{object}. It returns the
848 value @var{object}. For example:
866 When a cons cell is part of the shared structure of several lists,
867 storing a new @sc{car} into the cons changes one element of each of
868 these lists. Here is an example:
872 ;; @r{Create two lists that are partly shared.}
875 (setq x2 (cons 'z (cdr x1)))
880 ;; @r{Replace the @sc{car} of a shared link.}
881 (setcar (cdr x1) 'foo)
883 x1 ; @r{Both lists are changed.}
890 ;; @r{Replace the @sc{car} of a link that is not shared.}
893 x1 ; @r{Only one list is changed.}
894 @result{} (baz foo c)
900 Here is a graphical depiction of the shared structure of the two lists
901 in the variables @code{x1} and @code{x2}, showing why replacing @code{b}
906 --- --- --- --- --- ---
907 x1---> | | |----> | | |--> | | |--> nil
908 --- --- --- --- --- ---
922 Here is an alternative form of box diagram, showing the same relationship:
927 -------------- -------------- --------------
928 | car | cdr | | car | cdr | | car | cdr |
929 | a | o------->| b | o------->| c | nil |
931 -------------- | -------------- --------------
943 @subsection Altering the CDR of a List
945 The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}:
947 @defun setcdr cons object
948 This function stores @var{object} as the new @sc{cdr} of @var{cons},
949 replacing its previous @sc{cdr}. In other words, it changes the
950 @sc{cdr} slot of @var{cons} to refer to @var{object}. It returns the
954 Here is an example of replacing the @sc{cdr} of a list with a
955 different list. All but the first element of the list are removed in
956 favor of a different sequence of elements. The first element is
957 unchanged, because it resides in the @sc{car} of the list, and is not
958 reached via the @sc{cdr}.
975 You can delete elements from the middle of a list by altering the
976 @sc{cdr}s of the cons cells in the list. For example, here we delete
977 the second element, @code{b}, from the list @code{(a b c)}, by changing
978 the @sc{cdr} of the first cons cell:
984 (setcdr x1 (cdr (cdr x1)))
991 Here is the result in box notation:
997 -------------- | -------------- | --------------
998 | car | cdr | | | car | cdr | -->| car | cdr |
999 | a | o----- | b | o-------->| c | nil |
1001 -------------- -------------- --------------
1006 The second cons cell, which previously held the element @code{b}, still
1007 exists and its @sc{car} is still @code{b}, but it no longer forms part
1010 It is equally easy to insert a new element by changing @sc{cdr}s:
1016 (setcdr x1 (cons 'd (cdr x1)))
1023 Here is this result in box notation:
1027 -------------- ------------- -------------
1028 | car | cdr | | car | cdr | | car | cdr |
1029 | a | o | -->| b | o------->| c | nil |
1030 | | | | | | | | | | |
1031 --------- | -- | ------------- -------------
1044 @subsection Functions that Rearrange Lists
1045 @cindex rearrangement of lists
1046 @cindex modification of lists
1048 Here are some functions that rearrange lists ``destructively'' by
1049 modifying the @sc{cdr}s of their component cons cells. We call these
1050 functions ``destructive'' because they chew up the original lists passed
1051 to them as arguments, relinking their cons cells to form a new list that
1052 is the returned value.
1055 See @code{delq}, in @ref{Sets And Lists}, for another function
1056 that modifies cons cells.
1059 The function @code{delq} in the following section is another example
1060 of destructive list manipulation.
1063 @defun nconc &rest lists
1064 @cindex concatenating lists
1065 @cindex joining lists
1066 This function returns a list containing all the elements of @var{lists}.
1067 Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are
1068 @emph{not} copied. Instead, the last @sc{cdr} of each of the
1069 @var{lists} is changed to refer to the following list. The last of the
1070 @var{lists} is not altered. For example:
1079 @result{} (1 2 3 4 5)
1083 @result{} (1 2 3 4 5)
1087 Since the last argument of @code{nconc} is not itself modified, it is
1088 reasonable to use a constant list, such as @code{'(4 5)}, as in the
1089 above example. For the same reason, the last argument need not be a
1099 @result{} (1 2 3 . z)
1103 @result{} (1 2 3 . z)
1107 However, the other arguments (all but the last) must be lists.
1109 A common pitfall is to use a quoted constant list as a non-last
1110 argument to @code{nconc}. If you do this, your program will change
1111 each time you run it! Here is what happens:
1115 (defun add-foo (x) ; @r{We want this function to add}
1116 (nconc '(foo) x)) ; @r{@code{foo} to the front of its arg.}
1120 (symbol-function 'add-foo)
1121 @result{} (lambda (x) (nconc (quote (foo)) x))
1125 (setq xx (add-foo '(1 2))) ; @r{It seems to work.}
1129 (setq xy (add-foo '(3 4))) ; @r{What happened?}
1130 @result{} (foo 1 2 3 4)
1138 (symbol-function 'add-foo)
1139 @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x)))
1144 @defun nreverse list
1145 @cindex reversing a list
1146 This function reverses the order of the elements of @var{list}.
1147 Unlike @code{reverse}, @code{nreverse} alters its argument by reversing
1148 the @sc{cdr}s in the cons cells forming the list. The cons cell that
1149 used to be the last one in @var{list} becomes the first cons cell of the
1166 ;; @r{The cons cell that was first is now last.}
1172 To avoid confusion, we usually store the result of @code{nreverse}
1173 back in the same variable which held the original list:
1176 (setq x (nreverse x))
1179 Here is the @code{nreverse} of our favorite example, @code{(a b c)},
1180 presented graphically:
1184 @r{Original list head:} @r{Reversed list:}
1185 ------------- ------------- ------------
1186 | car | cdr | | car | cdr | | car | cdr |
1187 | a | nil |<-- | b | o |<-- | c | o |
1188 | | | | | | | | | | | | |
1189 ------------- | --------- | - | -------- | -
1191 ------------- ------------
1196 @defun sort list predicate
1198 @cindex sorting lists
1199 This function sorts @var{list} stably, though destructively, and
1200 returns the sorted list. It compares elements using @var{predicate}. A
1201 stable sort is one in which elements with equal sort keys maintain their
1202 relative order before and after the sort. Stability is important when
1203 successive sorts are used to order elements according to different
1206 The argument @var{predicate} must be a function that accepts two
1207 arguments. It is called with two elements of @var{list}. To get an
1208 increasing order sort, the @var{predicate} should return non-@code{nil} if the
1209 first element is ``less than'' the second, or @code{nil} if not.
1211 The comparison function @var{predicate} must give reliable results for
1212 any given pair of arguments, at least within a single call to
1213 @code{sort}. It must be @dfn{antisymmetric}; that is, if @var{a} is
1214 less than @var{b}, @var{b} must not be less than @var{a}. It must be
1215 @dfn{transitive}---that is, if @var{a} is less than @var{b}, and @var{b}
1216 is less than @var{c}, then @var{a} must be less than @var{c}. If you
1217 use a comparison function which does not meet these requirements, the
1218 result of @code{sort} is unpredictable.
1220 The destructive aspect of @code{sort} is that it rearranges the cons
1221 cells forming @var{list} by changing @sc{cdr}s. A nondestructive sort
1222 function would create new cons cells to store the elements in their
1223 sorted order. If you wish to make a sorted copy without destroying the
1224 original, copy it first with @code{copy-sequence} and then sort.
1226 Sorting does not change the @sc{car}s of the cons cells in @var{list};
1227 the cons cell that originally contained the element @code{a} in
1228 @var{list} still has @code{a} in its @sc{car} after sorting, but it now
1229 appears in a different position in the list due to the change of
1230 @sc{cdr}s. For example:
1234 (setq nums '(1 3 2 6 5 4 0))
1235 @result{} (1 3 2 6 5 4 0)
1239 @result{} (0 1 2 3 4 5 6)
1243 @result{} (1 2 3 4 5 6)
1248 @strong{Warning}: Note that the list in @code{nums} no longer contains
1249 0; this is the same cons cell that it was before, but it is no longer
1250 the first one in the list. Don't assume a variable that formerly held
1251 the argument now holds the entire sorted list! Instead, save the result
1252 of @code{sort} and use that. Most often we store the result back into
1253 the variable that held the original list:
1256 (setq nums (sort nums '<))
1259 @xref{Sorting}, for more functions that perform sorting.
1260 See @code{documentation} in @ref{Accessing Documentation}, for a
1261 useful example of @code{sort}.
1264 @node Sets And Lists
1265 @section Using Lists as Sets
1266 @cindex lists as sets
1269 A list can represent an unordered mathematical set---simply consider a
1270 value an element of a set if it appears in the list, and ignore the
1271 order of the list. To form the union of two sets, use @code{append} (as
1272 long as you don't mind having duplicate elements). You can remove
1273 @code{equal} duplicates using @code{delete-dups}. Other useful
1274 functions for sets include @code{memq} and @code{delq}, and their
1275 @code{equal} versions, @code{member} and @code{delete}.
1277 @cindex CL note---lack @code{union}, @code{intersection}
1279 @b{Common Lisp note:} Common Lisp has functions @code{union} (which
1280 avoids duplicate elements) and @code{intersection} for set operations.
1281 Although standard GNU Emacs Lisp does not have them, the @file{cl-lib}
1282 library provides versions.
1283 @xref{Lists as Sets,,, cl, Common Lisp Extensions}.
1286 @defun memq object list
1287 @cindex membership in a list
1288 This function tests to see whether @var{object} is a member of
1289 @var{list}. If it is, @code{memq} returns a list starting with the
1290 first occurrence of @var{object}. Otherwise, it returns @code{nil}.
1291 The letter @samp{q} in @code{memq} says that it uses @code{eq} to
1292 compare @var{object} against the elements of the list. For example:
1296 (memq 'b '(a b c b a))
1300 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1306 @defun delq object list
1307 @cindex deleting list elements
1308 This function destructively removes all elements @code{eq} to
1309 @var{object} from @var{list}, and returns the resulting list. The
1310 letter @samp{q} in @code{delq} says that it uses @code{eq} to compare
1311 @var{object} against the elements of the list, like @code{memq} and
1314 Typically, when you invoke @code{delq}, you should use the return
1315 value by assigning it to the variable which held the original list.
1316 The reason for this is explained below.
1319 The @code{delq} function deletes elements from the front of the list
1320 by simply advancing down the list, and returning a sublist that starts
1321 after those elements. For example:
1325 (delq 'a '(a b c)) @equiv{} (cdr '(a b c))
1330 When an element to be deleted appears in the middle of the list,
1331 removing it involves changing the @sc{cdr}s (@pxref{Setcdr}).
1335 (setq sample-list '(a b c (4)))
1336 @result{} (a b c (4))
1339 (delq 'a sample-list)
1344 @result{} (a b c (4))
1347 (delq 'c sample-list)
1356 Note that @code{(delq 'c sample-list)} modifies @code{sample-list} to
1357 splice out the third element, but @code{(delq 'a sample-list)} does not
1358 splice anything---it just returns a shorter list. Don't assume that a
1359 variable which formerly held the argument @var{list} now has fewer
1360 elements, or that it still holds the original list! Instead, save the
1361 result of @code{delq} and use that. Most often we store the result back
1362 into the variable that held the original list:
1365 (setq flowers (delq 'rose flowers))
1368 In the following example, the @code{(4)} that @code{delq} attempts to match
1369 and the @code{(4)} in the @code{sample-list} are not @code{eq}:
1373 (delq '(4) sample-list)
1378 If you want to delete elements that are @code{equal} to a given value,
1379 use @code{delete} (see below).
1381 @defun remq object list
1382 This function returns a copy of @var{list}, with all elements removed
1383 which are @code{eq} to @var{object}. The letter @samp{q} in @code{remq}
1384 says that it uses @code{eq} to compare @var{object} against the elements
1389 (setq sample-list '(a b c a b c))
1390 @result{} (a b c a b c)
1393 (remq 'a sample-list)
1398 @result{} (a b c a b c)
1403 @defun memql object list
1404 The function @code{memql} tests to see whether @var{object} is a member
1405 of @var{list}, comparing members with @var{object} using @code{eql},
1406 so floating point elements are compared by value.
1407 If @var{object} is a member, @code{memql} returns a list starting with
1408 its first occurrence in @var{list}. Otherwise, it returns @code{nil}.
1410 Compare this with @code{memq}:
1414 (memql 1.2 '(1.1 1.2 1.3)) ; @r{@code{1.2} and @code{1.2} are @code{eql}.}
1418 (memq 1.2 '(1.1 1.2 1.3)) ; @r{@code{1.2} and @code{1.2} are not @code{eq}.}
1424 The following three functions are like @code{memq}, @code{delq} and
1425 @code{remq}, but use @code{equal} rather than @code{eq} to compare
1426 elements. @xref{Equality Predicates}.
1428 @defun member object list
1429 The function @code{member} tests to see whether @var{object} is a member
1430 of @var{list}, comparing members with @var{object} using @code{equal}.
1431 If @var{object} is a member, @code{member} returns a list starting with
1432 its first occurrence in @var{list}. Otherwise, it returns @code{nil}.
1434 Compare this with @code{memq}:
1438 (member '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are @code{equal}.}
1442 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1446 ;; @r{Two strings with the same contents are @code{equal}.}
1447 (member "foo" '("foo" "bar"))
1448 @result{} ("foo" "bar")
1453 @defun delete object sequence
1454 This function removes all elements @code{equal} to @var{object} from
1455 @var{sequence}, and returns the resulting sequence.
1457 If @var{sequence} is a list, @code{delete} is to @code{delq} as
1458 @code{member} is to @code{memq}: it uses @code{equal} to compare
1459 elements with @var{object}, like @code{member}; when it finds an
1460 element that matches, it cuts the element out just as @code{delq}
1461 would. As with @code{delq}, you should typically use the return value
1462 by assigning it to the variable which held the original list.
1464 If @code{sequence} is a vector or string, @code{delete} returns a copy
1465 of @code{sequence} with all elements @code{equal} to @code{object}
1472 (setq l '((2) (1) (2)))
1477 ;; @r{If you want to change @code{l} reliably,}
1478 ;; @r{write @code{(setq l (delete '(2) l))}.}
1481 (setq l '((2) (1) (2)))
1486 ;; @r{In this case, it makes no difference whether you set @code{l},}
1487 ;; @r{but you should do so for the sake of the other case.}
1490 (delete '(2) [(2) (1) (2)])
1496 @defun remove object sequence
1497 This function is the non-destructive counterpart of @code{delete}. It
1498 returns a copy of @code{sequence}, a list, vector, or string, with
1499 elements @code{equal} to @code{object} removed. For example:
1503 (remove '(2) '((2) (1) (2)))
1507 (remove '(2) [(2) (1) (2)])
1514 @b{Common Lisp note:} The functions @code{member}, @code{delete} and
1515 @code{remove} in GNU Emacs Lisp are derived from Maclisp, not Common
1516 Lisp. The Common Lisp versions do not use @code{equal} to compare
1520 @defun member-ignore-case object list
1521 This function is like @code{member}, except that @var{object} should
1522 be a string and that it ignores differences in letter-case and text
1523 representation: upper-case and lower-case letters are treated as
1524 equal, and unibyte strings are converted to multibyte prior to
1528 @defun delete-dups list
1529 This function destructively removes all @code{equal} duplicates from
1530 @var{list}, stores the result in @var{list} and returns it. Of
1531 several @code{equal} occurrences of an element in @var{list},
1532 @code{delete-dups} keeps the first one.
1535 See also the function @code{add-to-list}, in @ref{List Variables},
1536 for a way to add an element to a list stored in a variable and used as a
1539 @node Association Lists
1540 @section Association Lists
1541 @cindex association list
1544 An @dfn{association list}, or @dfn{alist} for short, records a mapping
1545 from keys to values. It is a list of cons cells called
1546 @dfn{associations}: the @sc{car} of each cons cell is the @dfn{key}, and the
1547 @sc{cdr} is the @dfn{associated value}.@footnote{This usage of ``key''
1548 is not related to the term ``key sequence''; it means a value used to
1549 look up an item in a table. In this case, the table is the alist, and
1550 the alist associations are the items.}
1552 Here is an example of an alist. The key @code{pine} is associated with
1553 the value @code{cones}; the key @code{oak} is associated with
1554 @code{acorns}; and the key @code{maple} is associated with @code{seeds}.
1564 Both the values and the keys in an alist may be any Lisp objects.
1565 For example, in the following alist, the symbol @code{a} is
1566 associated with the number @code{1}, and the string @code{"b"} is
1567 associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of
1574 Sometimes it is better to design an alist to store the associated
1575 value in the @sc{car} of the @sc{cdr} of the element. Here is an
1576 example of such an alist:
1579 ((rose red) (lily white) (buttercup yellow))
1583 Here we regard @code{red} as the value associated with @code{rose}. One
1584 advantage of this kind of alist is that you can store other related
1585 information---even a list of other items---in the @sc{cdr} of the
1586 @sc{cdr}. One disadvantage is that you cannot use @code{rassq} (see
1587 below) to find the element containing a given value. When neither of
1588 these considerations is important, the choice is a matter of taste, as
1589 long as you are consistent about it for any given alist.
1591 The same alist shown above could be regarded as having the
1592 associated value in the @sc{cdr} of the element; the value associated
1593 with @code{rose} would be the list @code{(red)}.
1595 Association lists are often used to record information that you might
1596 otherwise keep on a stack, since new associations may be added easily to
1597 the front of the list. When searching an association list for an
1598 association with a given key, the first one found is returned, if there
1601 In Emacs Lisp, it is @emph{not} an error if an element of an
1602 association list is not a cons cell. The alist search functions simply
1603 ignore such elements. Many other versions of Lisp signal errors in such
1606 Note that property lists are similar to association lists in several
1607 respects. A property list behaves like an association list in which
1608 each key can occur only once. @xref{Property Lists}, for a comparison
1609 of property lists and association lists.
1611 @defun assoc key alist
1612 This function returns the first association for @var{key} in
1613 @var{alist}, comparing @var{key} against the alist elements using
1614 @code{equal} (@pxref{Equality Predicates}). It returns @code{nil} if no
1615 association in @var{alist} has a @sc{car} @code{equal} to @var{key}.
1619 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1620 @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1622 @result{} (oak . acorns)
1623 (cdr (assoc 'oak trees))
1625 (assoc 'birch trees)
1629 Here is another example, in which the keys and values are not symbols:
1632 (setq needles-per-cluster
1633 '((2 "Austrian Pine" "Red Pine")
1637 (cdr (assoc 3 needles-per-cluster))
1638 @result{} ("Pitch Pine")
1639 (cdr (assoc 2 needles-per-cluster))
1640 @result{} ("Austrian Pine" "Red Pine")
1644 The function @code{assoc-string} is much like @code{assoc} except
1645 that it ignores certain differences between strings. @xref{Text
1648 @defun rassoc value alist
1649 This function returns the first association with value @var{value} in
1650 @var{alist}. It returns @code{nil} if no association in @var{alist} has
1651 a @sc{cdr} @code{equal} to @var{value}.
1653 @code{rassoc} is like @code{assoc} except that it compares the @sc{cdr} of
1654 each @var{alist} association instead of the @sc{car}. You can think of
1655 this as ``reverse @code{assoc}'', finding the key for a given value.
1658 @defun assq key alist
1659 This function is like @code{assoc} in that it returns the first
1660 association for @var{key} in @var{alist}, but it makes the comparison
1661 using @code{eq} instead of @code{equal}. @code{assq} returns @code{nil}
1662 if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}.
1663 This function is used more often than @code{assoc}, since @code{eq} is
1664 faster than @code{equal} and most alists use symbols as keys.
1665 @xref{Equality Predicates}.
1668 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1669 @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1671 @result{} (pine . cones)
1674 On the other hand, @code{assq} is not usually useful in alists where the
1675 keys may not be symbols:
1679 '(("simple leaves" . oak)
1680 ("compound leaves" . horsechestnut)))
1682 (assq "simple leaves" leaves)
1684 (assoc "simple leaves" leaves)
1685 @result{} ("simple leaves" . oak)
1689 @defun rassq value alist
1690 This function returns the first association with value @var{value} in
1691 @var{alist}. It returns @code{nil} if no association in @var{alist} has
1692 a @sc{cdr} @code{eq} to @var{value}.
1694 @code{rassq} is like @code{assq} except that it compares the @sc{cdr} of
1695 each @var{alist} association instead of the @sc{car}. You can think of
1696 this as ``reverse @code{assq}'', finding the key for a given value.
1701 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1703 (rassq 'acorns trees)
1704 @result{} (oak . acorns)
1705 (rassq 'spores trees)
1709 @code{rassq} cannot search for a value stored in the @sc{car}
1710 of the @sc{cdr} of an element:
1713 (setq colors '((rose red) (lily white) (buttercup yellow)))
1715 (rassq 'white colors)
1719 In this case, the @sc{cdr} of the association @code{(lily white)} is not
1720 the symbol @code{white}, but rather the list @code{(white)}. This
1721 becomes clearer if the association is written in dotted pair notation:
1724 (lily white) @equiv{} (lily . (white))
1728 @defun assoc-default key alist &optional test default
1729 This function searches @var{alist} for a match for @var{key}. For each
1730 element of @var{alist}, it compares the element (if it is an atom) or
1731 the element's @sc{car} (if it is a cons) against @var{key}, by calling
1732 @var{test} with two arguments: the element or its @sc{car}, and
1733 @var{key}. The arguments are passed in that order so that you can get
1734 useful results using @code{string-match} with an alist that contains
1735 regular expressions (@pxref{Regexp Search}). If @var{test} is omitted
1736 or @code{nil}, @code{equal} is used for comparison.
1738 If an alist element matches @var{key} by this criterion,
1739 then @code{assoc-default} returns a value based on this element.
1740 If the element is a cons, then the value is the element's @sc{cdr}.
1741 Otherwise, the return value is @var{default}.
1743 If no alist element matches @var{key}, @code{assoc-default} returns
1747 @defun copy-alist alist
1748 @cindex copying alists
1749 This function returns a two-level deep copy of @var{alist}: it creates a
1750 new copy of each association, so that you can alter the associations of
1751 the new alist without changing the old one.
1755 (setq needles-per-cluster
1756 '((2 . ("Austrian Pine" "Red Pine"))
1757 (3 . ("Pitch Pine"))
1759 (5 . ("White Pine"))))
1761 ((2 "Austrian Pine" "Red Pine")
1765 (setq copy (copy-alist needles-per-cluster))
1767 ((2 "Austrian Pine" "Red Pine")
1771 (eq needles-per-cluster copy)
1773 (equal needles-per-cluster copy)
1775 (eq (car needles-per-cluster) (car copy))
1777 (cdr (car (cdr needles-per-cluster)))
1778 @result{} ("Pitch Pine")
1780 (eq (cdr (car (cdr needles-per-cluster)))
1781 (cdr (car (cdr copy))))
1786 This example shows how @code{copy-alist} makes it possible to change
1787 the associations of one copy without affecting the other:
1791 (setcdr (assq 3 copy) '("Martian Vacuum Pine"))
1792 (cdr (assq 3 needles-per-cluster))
1793 @result{} ("Pitch Pine")
1798 @defun assq-delete-all key alist
1799 This function deletes from @var{alist} all the elements whose @sc{car}
1800 is @code{eq} to @var{key}, much as if you used @code{delq} to delete
1801 each such element one by one. It returns the shortened alist, and
1802 often modifies the original list structure of @var{alist}. For
1803 correct results, use the return value of @code{assq-delete-all} rather
1804 than looking at the saved value of @var{alist}.
1807 (setq alist '((foo 1) (bar 2) (foo 3) (lose 4)))
1808 @result{} ((foo 1) (bar 2) (foo 3) (lose 4))
1809 (assq-delete-all 'foo alist)
1810 @result{} ((bar 2) (lose 4))
1812 @result{} ((foo 1) (bar 2) (lose 4))
1816 @defun rassq-delete-all value alist
1817 This function deletes from @var{alist} all the elements whose @sc{cdr}
1818 is @code{eq} to @var{value}. It returns the shortened alist, and
1819 often modifies the original list structure of @var{alist}.
1820 @code{rassq-delete-all} is like @code{assq-delete-all} except that it
1821 compares the @sc{cdr} of each @var{alist} association instead of the