2 @c This is part of the GNU Emacs Lisp Reference Manual.
3 @c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998, 1999
4 @c 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 * Lists as Boxes:: Graphical notation to explain lists.
21 * List-related Predicates:: Is this object a list? Comparing two lists.
22 * List Elements:: Extracting the pieces of a list.
23 * Building Lists:: Creating list structure.
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.
30 @section Lists and Cons Cells
31 @cindex lists and cons cells
32 @cindex @code{nil} and lists
34 Lists in Lisp are not a primitive data type; they are built up from
35 @dfn{cons cells}. A cons cell is a data object that represents an
36 ordered pair. That is, it has two slots, and each slot @dfn{holds}, or
37 @dfn{refers to}, some Lisp object. One slot is known as the @sc{car},
38 and the other is known as the @sc{cdr}. (These names are traditional;
39 see @ref{Cons Cell Type}.) @sc{cdr} is pronounced ``could-er.''
41 We say that ``the @sc{car} of this cons cell is'' whatever object
42 its @sc{car} slot currently holds, and likewise for the @sc{cdr}.
44 A list is a series of cons cells ``chained together,'' so that each
45 cell refers to the next one. There is one cons cell for each element of
46 the list. By convention, the @sc{car}s of the cons cells hold the
47 elements of the list, and the @sc{cdr}s are used to chain the list: the
48 @sc{cdr} slot of each cons cell refers to the following cons cell. The
49 @sc{cdr} of the last cons cell is @code{nil}. This asymmetry between
50 the @sc{car} and the @sc{cdr} is entirely a matter of convention; at the
51 level of cons cells, the @sc{car} and @sc{cdr} slots have the same
54 @cindex list structure
55 Because most cons cells are used as part of lists, the phrase
56 @dfn{list structure} has come to mean any structure made out of cons
59 The symbol @code{nil} is considered a list as well as a symbol; it is
60 the list with no elements. For convenience, the symbol @code{nil} is
61 considered to have @code{nil} as its @sc{cdr} (and also as its
64 The @sc{cdr} of any nonempty list @var{l} is a list containing all the
65 elements of @var{l} except the first.
68 @comment node-name, next, previous, up
69 @section Lists as Linked Pairs of Boxes
70 @cindex box representation for lists
71 @cindex lists represented as boxes
72 @cindex cons cell as box
74 A cons cell can be illustrated as a pair of boxes. The first box
75 represents the @sc{car} and the second box represents the @sc{cdr}.
76 Here is an illustration of the two-element list, @code{(tulip lily)},
77 made from two cons cells:
81 --------------- ---------------
82 | car | cdr | | car | cdr |
83 | tulip | o---------->| lily | nil |
85 --------------- ---------------
89 Each pair of boxes represents a cons cell. Each box ``refers to'',
90 ``points to'' or ``holds'' a Lisp object. (These terms are
91 synonymous.) The first box, which describes the @sc{car} of the first
92 cons cell, contains the symbol @code{tulip}. The arrow from the
93 @sc{cdr} box of the first cons cell to the second cons cell indicates
94 that the @sc{cdr} of the first cons cell is the second cons cell.
96 The same list can be illustrated in a different sort of box notation
102 | | |--> | | |--> nil
110 Here is a more complex illustration, showing the three-element list,
111 @code{((pine needles) oak maple)}, the first element of which is a
116 --- --- --- --- --- ---
117 | | |--> | | |--> | | |--> nil
118 --- --- --- --- --- ---
124 --> | | |--> | | |--> nil
132 The same list represented in the first box notation looks like this:
136 -------------- -------------- --------------
137 | car | cdr | | car | cdr | | car | cdr |
138 | o | o------->| oak | o------->| maple | nil |
140 -- | --------- -------------- --------------
143 | -------------- ----------------
144 | | car | cdr | | car | cdr |
145 ------>| pine | o------->| needles | nil |
147 -------------- ----------------
151 @xref{Cons Cell Type}, for the read and print syntax of cons cells and
152 lists, and for more ``box and arrow'' illustrations of lists.
154 @node List-related Predicates
155 @section Predicates on Lists
157 The following predicates test whether a Lisp object is an atom, is a
158 cons cell or is a list, or whether it is the distinguished object
159 @code{nil}. (Many of these predicates can be defined in terms of the
160 others, but they are used so often that it is worth having all of them.)
163 This function returns @code{t} if @var{object} is a cons cell, @code{nil}
164 otherwise. @code{nil} is not a cons cell, although it @emph{is} a list.
169 This function returns @code{t} if @var{object} is an atom, @code{nil}
170 otherwise. All objects except cons cells are atoms. The symbol
171 @code{nil} is an atom and is also a list; it is the only Lisp object
175 (atom @var{object}) @equiv{} (not (consp @var{object}))
180 This function returns @code{t} if @var{object} is a cons cell or
181 @code{nil}. Otherwise, it returns @code{nil}.
196 This function is the opposite of @code{listp}: it returns @code{t} if
197 @var{object} is not a list. Otherwise, it returns @code{nil}.
200 (listp @var{object}) @equiv{} (not (nlistp @var{object}))
205 This function returns @code{t} if @var{object} is @code{nil}, and
206 returns @code{nil} otherwise. This function is identical to @code{not},
207 but as a matter of clarity we use @code{null} when @var{object} is
208 considered a list and @code{not} when it is considered a truth value
209 (see @code{not} in @ref{Combining Conditions}).
226 @section Accessing Elements of Lists
227 @cindex list elements
230 This function returns the value referred to by the first slot of the
231 cons cell @var{cons-cell}. Expressed another way, this function
232 returns the @sc{car} of @var{cons-cell}.
234 As a special case, if @var{cons-cell} is @code{nil}, then @code{car}
235 is defined to return @code{nil}; therefore, any list is a valid argument
236 for @code{car}. An error is signaled if the argument is not a cons cell
252 This function returns the value referred to by the second slot of
253 the cons cell @var{cons-cell}. Expressed another way, this function
254 returns the @sc{cdr} of @var{cons-cell}.
256 As a special case, if @var{cons-cell} is @code{nil}, then @code{cdr}
257 is defined to return @code{nil}; therefore, any list is a valid argument
258 for @code{cdr}. An error is signaled if the argument is not a cons cell
273 @defun car-safe object
274 This function lets you take the @sc{car} of a cons cell while avoiding
275 errors for other data types. It returns the @sc{car} of @var{object} if
276 @var{object} is a cons cell, @code{nil} otherwise. This is in contrast
277 to @code{car}, which signals an error if @var{object} is not a list.
281 (car-safe @var{object})
283 (let ((x @var{object}))
291 @defun cdr-safe object
292 This function lets you take the @sc{cdr} of a cons cell while
293 avoiding errors for other data types. It returns the @sc{cdr} of
294 @var{object} if @var{object} is a cons cell, @code{nil} otherwise.
295 This is in contrast to @code{cdr}, which signals an error if
296 @var{object} is not a list.
300 (cdr-safe @var{object})
302 (let ((x @var{object}))
312 This macro is a way of examining the @sc{car} of a list,
313 and taking it off the list, all at once. It is new in Emacs 21.
315 It operates on the list which is stored in the symbol @var{listname}.
316 It removes this element from the list by setting @var{listname}
317 to the @sc{cdr} of its old value---but it also returns the @sc{car}
318 of that list, which is the element being removed.
330 @anchor{Definition of nth}
332 This function returns the @var{n}th element of @var{list}. Elements
333 are numbered starting with zero, so the @sc{car} of @var{list} is
334 element number zero. If the length of @var{list} is @var{n} or less,
335 the value is @code{nil}.
337 If @var{n} is negative, @code{nth} returns the first element of
353 (nth n x) @equiv{} (car (nthcdr n x))
357 The function @code{elt} is similar, but applies to any kind of sequence.
358 For historical reasons, it takes its arguments in the opposite order.
359 @xref{Sequence Functions}.
363 This function returns the @var{n}th @sc{cdr} of @var{list}. In other
364 words, it skips past the first @var{n} links of @var{list} and returns
367 If @var{n} is zero or negative, @code{nthcdr} returns all of
368 @var{list}. If the length of @var{list} is @var{n} or less,
369 @code{nthcdr} returns @code{nil}.
373 (nthcdr 1 '(1 2 3 4))
377 (nthcdr 10 '(1 2 3 4))
381 (nthcdr -3 '(1 2 3 4))
387 @defun last list &optional n
388 This function returns the last link of @var{list}. The @code{car} of
389 this link is the list's last element. If @var{list} is null,
390 @code{nil} is returned. If @var{n} is non-@code{nil}, the
391 @var{n}th-to-last link is returned instead, or the whole of @var{list}
392 if @var{n} is bigger than @var{list}'s length.
395 @anchor{Definition of safe-length}
396 @defun safe-length list
397 This function returns the length of @var{list}, with no risk
398 of either an error or an infinite loop.
400 If @var{list} is not really a list, @code{safe-length} returns 0. If
401 @var{list} is circular, it returns a finite value which is at least the
402 number of distinct elements.
405 The most common way to compute the length of a list, when you are not
406 worried that it may be circular, is with @code{length}. @xref{Sequence
409 @defun caar cons-cell
410 This is the same as @code{(car (car @var{cons-cell}))}.
413 @defun cadr cons-cell
414 This is the same as @code{(car (cdr @var{cons-cell}))}
415 or @code{(nth 1 @var{cons-cell})}.
418 @defun cdar cons-cell
419 This is the same as @code{(cdr (car @var{cons-cell}))}.
422 @defun cddr cons-cell
423 This is the same as @code{(cdr (cdr @var{cons-cell}))}
424 or @code{(nthcdr 2 @var{cons-cell})}.
427 @defun butlast x &optional n
428 This function returns the list @var{x} with the last element,
429 or the last @var{n} elements, removed. If @var{n} is greater
430 than zero it makes a copy of the list so as not to damage the
431 original list. In general, @code{(append (butlast @var{x} @var{n})
432 (last @var{x} @var{n}))} will return a list equal to @var{x}.
435 @defun nbutlast x &optional n
436 This is a version of @code{butlast} that works by destructively
437 modifying the @code{cdr} of the appropriate element, rather than
438 making a copy of the list.
442 @comment node-name, next, previous, up
443 @section Building Cons Cells and Lists
445 @cindex building lists
447 Many functions build lists, as lists reside at the very heart of Lisp.
448 @code{cons} is the fundamental list-building function; however, it is
449 interesting to note that @code{list} is used more times in the source
450 code for Emacs than @code{cons}.
452 @defun cons object1 object2
453 This function is the most basic function for building new list
454 structure. It creates a new cons cell, making @var{object1} the
455 @sc{car}, and @var{object2} the @sc{cdr}. It then returns the new
456 cons cell. The arguments @var{object1} and @var{object2} may be any
457 Lisp objects, but most often @var{object2} is a list.
475 @code{cons} is often used to add a single element to the front of a
476 list. This is called @dfn{consing the element onto the list}.
477 @footnote{There is no strictly equivalent way to add an element to
478 the end of a list. You can use @code{(append @var{listname} (list
479 @var{newelt}))}, which creates a whole new list by copying @var{listname}
480 and adding @var{newelt} to its end. Or you can use @code{(nconc
481 @var{listname} (list @var{newelt}))}, which modifies @var{listname}
482 by following all the @sc{cdr}s and then replacing the terminating
483 @code{nil}. Compare this to adding an element to the beginning of a
484 list with @code{cons}, which neither copies nor modifies the list.}
488 (setq list (cons newelt list))
491 Note that there is no conflict between the variable named @code{list}
492 used in this example and the function named @code{list} described below;
493 any symbol can serve both purposes.
497 @defmac push newelt listname
498 This macro provides an alternative way to write
499 @code{(setq @var{listname} (cons @var{newelt} @var{listname}))}.
500 It is new in Emacs 21.
512 @defun list &rest objects
513 This function creates a list with @var{objects} as its elements. The
514 resulting list is always @code{nil}-terminated. If no @var{objects}
515 are given, the empty list is returned.
520 @result{} (1 2 3 4 5)
523 (list 1 2 '(3 4 5) 'foo)
524 @result{} (1 2 (3 4 5) foo)
533 @defun make-list length object
534 This function creates a list of @var{length} elements, in which each
535 element is @var{object}. Compare @code{make-list} with
536 @code{make-string} (@pxref{Creating Strings}).
541 @result{} (pigs pigs pigs)
548 (setq l (make-list 3 '(a b))
549 @result{} ((a b) (a b) (a b))
550 (eq (car l) (cadr l))
556 @defun append &rest sequences
557 @cindex copying lists
558 This function returns a list containing all the elements of
559 @var{sequences}. The @var{sequences} may be lists, vectors,
560 bool-vectors, or strings, but the last one should usually be a list.
561 All arguments except the last one are copied, so none of the arguments
562 is altered. (See @code{nconc} in @ref{Rearrangement}, for a way to join
563 lists with no copying.)
565 More generally, the final argument to @code{append} may be any Lisp
566 object. The final argument is not copied or converted; it becomes the
567 @sc{cdr} of the last cons cell in the new list. If the final argument
568 is itself a list, then its elements become in effect elements of the
569 result list. If the final element is not a list, the result is a
570 dotted list since its final @sc{cdr} is not @code{nil} as required
573 In Emacs 20 and before, the @code{append} function also allowed
574 integers as (non last) arguments. It converted them to strings of
575 digits, making up the decimal print representation of the integer, and
576 then used the strings instead of the original integers. This obsolete
577 usage no longer works. The proper way to convert an integer to a
578 decimal number in this way is with @code{format} (@pxref{Formatting
579 Strings}) or @code{number-to-string} (@pxref{String Conversion}).
582 Here is an example of using @code{append}:
586 (setq trees '(pine oak))
588 (setq more-trees (append '(maple birch) trees))
589 @result{} (maple birch pine oak)
596 @result{} (maple birch pine oak)
599 (eq trees (cdr (cdr more-trees)))
604 You can see how @code{append} works by looking at a box diagram. The
605 variable @code{trees} is set to the list @code{(pine oak)} and then the
606 variable @code{more-trees} is set to the list @code{(maple birch pine
607 oak)}. However, the variable @code{trees} continues to refer to the
614 | --- --- --- --- -> --- --- --- ---
615 --> | | |--> | | |--> | | |--> | | |--> nil
616 --- --- --- --- --- --- --- ---
619 --> maple -->birch --> pine --> oak
623 An empty sequence contributes nothing to the value returned by
624 @code{append}. As a consequence of this, a final @code{nil} argument
625 forces a copy of the previous argument:
633 (setq wood (append trees nil))
647 This once was the usual way to copy a list, before the function
648 @code{copy-sequence} was invented. @xref{Sequences Arrays Vectors}.
650 Here we show the use of vectors and strings as arguments to @code{append}:
654 (append [a b] "cd" nil)
655 @result{} (a b 99 100)
659 With the help of @code{apply} (@pxref{Calling Functions}), we can append
660 all the lists in a list of lists:
664 (apply 'append '((a b c) nil (x y z) nil))
665 @result{} (a b c x y z)
669 If no @var{sequences} are given, @code{nil} is returned:
678 Here are some examples where the final argument is not a list:
684 @result{} (x y . [z])
688 The second example shows that when the final argument is a sequence but
689 not a list, the sequence's elements do not become elements of the
690 resulting list. Instead, the sequence becomes the final @sc{cdr}, like
691 any other non-list final argument.
694 This function creates a new list whose elements are the elements of
695 @var{list}, but in reverse order. The original argument @var{list} is
712 @defun copy-tree tree &optional vecp
713 This function returns a copy of the tree @code{tree}. If @var{tree} is a
714 cons cell, this makes a new cons cell with the same @sc{car} and
715 @sc{cdr}, then recursively copies the @sc{car} and @sc{cdr} in the
718 Normally, when @var{tree} is anything other than a cons cell,
719 @code{copy-tree} simply returns @var{tree}. However, if @var{vecp} is
720 non-@code{nil}, it copies vectors too (and operates recursively on
724 @defun number-sequence from &optional to separation
725 This returns a list of numbers starting with @var{from} and
726 incrementing by @var{separation}, and ending at or just before
727 @var{to}. @var{separation} can be positive or negative and defaults
728 to 1. If @var{to} is @code{nil} or numerically equal to @var{from},
729 the one element list @code{(from)} is returned. If @var{separation}
730 is 0 and @var{to} is neither @code{nil} nor numerically equal to
731 @var{from}, an error is signaled.
733 All arguments can be integers or floating point numbers. However,
734 floating point arguments can be tricky, because floating point
735 arithmetic is inexact. For instance, depending on the machine, it may
736 quite well happen that @code{(number-sequence 0.4 0.6 0.2)} returns
737 the one element list @code{(0.4)}, whereas
738 @code{(number-sequence 0.4 0.8 0.2)} returns a list with three
739 elements. The @var{n}th element of the list is computed by the exact
740 formula @code{(+ @var{from} (* @var{n} @var{separation}))}. Thus, if
741 one wants to make sure that @var{to} is included in the list, one can
742 pass an expression of this exact type for @var{to}. Alternatively,
743 one can replace @var{to} with a slightly larger value (or a slightly
744 more negative value if @var{separation} is negative).
749 (number-sequence 4 9)
750 @result{} (4 5 6 7 8 9)
751 (number-sequence 9 4 -1)
752 @result{} (9 8 7 6 5 4)
753 (number-sequence 9 4 -2)
757 (number-sequence 8 5)
759 (number-sequence 5 8 -1)
761 (number-sequence 1.5 6 2)
762 @result{} (1.5 3.5 5.5)
766 @node Modifying Lists
767 @section Modifying Existing List Structure
768 @cindex destructive list operations
770 You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the
771 primitives @code{setcar} and @code{setcdr}. We call these ``destructive''
772 operations because they change existing list structure.
774 @cindex CL note---@code{rplaca} vrs @code{setcar}
778 @b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and
779 @code{rplacd} to alter list structure; they change structure the same
780 way as @code{setcar} and @code{setcdr}, but the Common Lisp functions
781 return the cons cell while @code{setcar} and @code{setcdr} return the
782 new @sc{car} or @sc{cdr}.
786 * Setcar:: Replacing an element in a list.
787 * Setcdr:: Replacing part of the list backbone.
788 This can be used to remove or add elements.
789 * Rearrangement:: Reordering the elements in a list; combining lists.
793 @subsection Altering List Elements with @code{setcar}
795 Changing the @sc{car} of a cons cell is done with @code{setcar}. When
796 used on a list, @code{setcar} replaces one element of a list with a
799 @defun setcar cons object
800 This function stores @var{object} as the new @sc{car} of @var{cons},
801 replacing its previous @sc{car}. In other words, it changes the
802 @sc{car} slot of @var{cons} to refer to @var{object}. It returns the
803 value @var{object}. For example:
821 When a cons cell is part of the shared structure of several lists,
822 storing a new @sc{car} into the cons changes one element of each of
823 these lists. Here is an example:
827 ;; @r{Create two lists that are partly shared.}
830 (setq x2 (cons 'z (cdr x1)))
835 ;; @r{Replace the @sc{car} of a shared link.}
836 (setcar (cdr x1) 'foo)
838 x1 ; @r{Both lists are changed.}
845 ;; @r{Replace the @sc{car} of a link that is not shared.}
848 x1 ; @r{Only one list is changed.}
849 @result{} (baz foo c)
855 Here is a graphical depiction of the shared structure of the two lists
856 in the variables @code{x1} and @code{x2}, showing why replacing @code{b}
861 --- --- --- --- --- ---
862 x1---> | | |----> | | |--> | | |--> nil
863 --- --- --- --- --- ---
877 Here is an alternative form of box diagram, showing the same relationship:
882 -------------- -------------- --------------
883 | car | cdr | | car | cdr | | car | cdr |
884 | a | o------->| b | o------->| c | nil |
886 -------------- | -------------- --------------
898 @subsection Altering the CDR of a List
900 The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}:
902 @defun setcdr cons object
903 This function stores @var{object} as the new @sc{cdr} of @var{cons},
904 replacing its previous @sc{cdr}. In other words, it changes the
905 @sc{cdr} slot of @var{cons} to refer to @var{object}. It returns the
909 Here is an example of replacing the @sc{cdr} of a list with a
910 different list. All but the first element of the list are removed in
911 favor of a different sequence of elements. The first element is
912 unchanged, because it resides in the @sc{car} of the list, and is not
913 reached via the @sc{cdr}.
930 You can delete elements from the middle of a list by altering the
931 @sc{cdr}s of the cons cells in the list. For example, here we delete
932 the second element, @code{b}, from the list @code{(a b c)}, by changing
933 the @sc{cdr} of the first cons cell:
939 (setcdr x1 (cdr (cdr x1)))
947 Here is the result in box notation:
953 -------------- | -------------- | --------------
954 | car | cdr | | | car | cdr | -->| car | cdr |
955 | a | o----- | b | o-------->| c | nil |
957 -------------- -------------- --------------
962 The second cons cell, which previously held the element @code{b}, still
963 exists and its @sc{car} is still @code{b}, but it no longer forms part
966 It is equally easy to insert a new element by changing @sc{cdr}s:
972 (setcdr x1 (cons 'd (cdr x1)))
979 Here is this result in box notation:
983 -------------- ------------- -------------
984 | car | cdr | | car | cdr | | car | cdr |
985 | a | o | -->| b | o------->| c | nil |
986 | | | | | | | | | | |
987 --------- | -- | ------------- -------------
1000 @subsection Functions that Rearrange Lists
1001 @cindex rearrangement of lists
1002 @cindex modification of lists
1004 Here are some functions that rearrange lists ``destructively'' by
1005 modifying the @sc{cdr}s of their component cons cells. We call these
1006 functions ``destructive'' because they chew up the original lists passed
1007 to them as arguments, relinking their cons cells to form a new list that
1008 is the returned value.
1011 See @code{delq}, in @ref{Sets And Lists}, for another function
1012 that modifies cons cells.
1015 The function @code{delq} in the following section is another example
1016 of destructive list manipulation.
1019 @defun nconc &rest lists
1020 @cindex concatenating lists
1021 @cindex joining lists
1022 This function returns a list containing all the elements of @var{lists}.
1023 Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are
1024 @emph{not} copied. Instead, the last @sc{cdr} of each of the
1025 @var{lists} is changed to refer to the following list. The last of the
1026 @var{lists} is not altered. For example:
1035 @result{} (1 2 3 4 5)
1039 @result{} (1 2 3 4 5)
1043 Since the last argument of @code{nconc} is not itself modified, it is
1044 reasonable to use a constant list, such as @code{'(4 5)}, as in the
1045 above example. For the same reason, the last argument need not be a
1055 @result{} (1 2 3 . z)
1059 @result{} (1 2 3 . z)
1063 However, the other arguments (all but the last) must be lists.
1065 A common pitfall is to use a quoted constant list as a non-last
1066 argument to @code{nconc}. If you do this, your program will change
1067 each time you run it! Here is what happens:
1071 (defun add-foo (x) ; @r{We want this function to add}
1072 (nconc '(foo) x)) ; @r{@code{foo} to the front of its arg.}
1076 (symbol-function 'add-foo)
1077 @result{} (lambda (x) (nconc (quote (foo)) x))
1081 (setq xx (add-foo '(1 2))) ; @r{It seems to work.}
1085 (setq xy (add-foo '(3 4))) ; @r{What happened?}
1086 @result{} (foo 1 2 3 4)
1094 (symbol-function 'add-foo)
1095 @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x)))
1100 @defun nreverse list
1101 @cindex reversing a list
1102 This function reverses the order of the elements of @var{list}.
1103 Unlike @code{reverse}, @code{nreverse} alters its argument by reversing
1104 the @sc{cdr}s in the cons cells forming the list. The cons cell that
1105 used to be the last one in @var{list} becomes the first cons cell of the
1122 ;; @r{The cons cell that was first is now last.}
1128 To avoid confusion, we usually store the result of @code{nreverse}
1129 back in the same variable which held the original list:
1132 (setq x (nreverse x))
1135 Here is the @code{nreverse} of our favorite example, @code{(a b c)},
1136 presented graphically:
1140 @r{Original list head:} @r{Reversed list:}
1141 ------------- ------------- ------------
1142 | car | cdr | | car | cdr | | car | cdr |
1143 | a | nil |<-- | b | o |<-- | c | o |
1144 | | | | | | | | | | | | |
1145 ------------- | --------- | - | -------- | -
1147 ------------- ------------
1152 @defun sort list predicate
1154 @cindex sorting lists
1155 This function sorts @var{list} stably, though destructively, and
1156 returns the sorted list. It compares elements using @var{predicate}. A
1157 stable sort is one in which elements with equal sort keys maintain their
1158 relative order before and after the sort. Stability is important when
1159 successive sorts are used to order elements according to different
1162 The argument @var{predicate} must be a function that accepts two
1163 arguments. It is called with two elements of @var{list}. To get an
1164 increasing order sort, the @var{predicate} should return @code{t} if the
1165 first element is ``less than'' the second, or @code{nil} if not.
1167 The comparison function @var{predicate} must give reliable results for
1168 any given pair of arguments, at least within a single call to
1169 @code{sort}. It must be @dfn{antisymmetric}; that is, if @var{a} is
1170 less than @var{b}, @var{b} must not be less than @var{a}. It must be
1171 @dfn{transitive}---that is, if @var{a} is less than @var{b}, and @var{b}
1172 is less than @var{c}, then @var{a} must be less than @var{c}. If you
1173 use a comparison function which does not meet these requirements, the
1174 result of @code{sort} is unpredictable.
1176 The destructive aspect of @code{sort} is that it rearranges the cons
1177 cells forming @var{list} by changing @sc{cdr}s. A nondestructive sort
1178 function would create new cons cells to store the elements in their
1179 sorted order. If you wish to make a sorted copy without destroying the
1180 original, copy it first with @code{copy-sequence} and then sort.
1182 Sorting does not change the @sc{car}s of the cons cells in @var{list};
1183 the cons cell that originally contained the element @code{a} in
1184 @var{list} still has @code{a} in its @sc{car} after sorting, but it now
1185 appears in a different position in the list due to the change of
1186 @sc{cdr}s. For example:
1190 (setq nums '(1 3 2 6 5 4 0))
1191 @result{} (1 3 2 6 5 4 0)
1195 @result{} (0 1 2 3 4 5 6)
1199 @result{} (1 2 3 4 5 6)
1204 @strong{Warning}: Note that the list in @code{nums} no longer contains
1205 0; this is the same cons cell that it was before, but it is no longer
1206 the first one in the list. Don't assume a variable that formerly held
1207 the argument now holds the entire sorted list! Instead, save the result
1208 of @code{sort} and use that. Most often we store the result back into
1209 the variable that held the original list:
1212 (setq nums (sort nums '<))
1215 @xref{Sorting}, for more functions that perform sorting.
1216 See @code{documentation} in @ref{Accessing Documentation}, for a
1217 useful example of @code{sort}.
1220 @node Sets And Lists
1221 @section Using Lists as Sets
1222 @cindex lists as sets
1225 A list can represent an unordered mathematical set---simply consider a
1226 value an element of a set if it appears in the list, and ignore the
1227 order of the list. To form the union of two sets, use @code{append} (as
1228 long as you don't mind having duplicate elements). You can remove
1229 @code{equal} duplicates using @code{delete-dups}. Other useful
1230 functions for sets include @code{memq} and @code{delq}, and their
1231 @code{equal} versions, @code{member} and @code{delete}.
1233 @cindex CL note---lack @code{union}, @code{intersection}
1235 @b{Common Lisp note:} Common Lisp has functions @code{union} (which
1236 avoids duplicate elements) and @code{intersection} for set operations,
1237 but GNU Emacs Lisp does not have them. You can write them in Lisp if
1241 @defun memq object list
1242 @cindex membership in a list
1243 This function tests to see whether @var{object} is a member of
1244 @var{list}. If it is, @code{memq} returns a list starting with the
1245 first occurrence of @var{object}. Otherwise, it returns @code{nil}.
1246 The letter @samp{q} in @code{memq} says that it uses @code{eq} to
1247 compare @var{object} against the elements of the list. For example:
1251 (memq 'b '(a b c b a))
1255 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1261 @defun delq object list
1262 @cindex deletion of elements
1263 This function destructively removes all elements @code{eq} to
1264 @var{object} from @var{list}. The letter @samp{q} in @code{delq} says
1265 that it uses @code{eq} to compare @var{object} against the elements of
1266 the list, like @code{memq} and @code{remq}.
1269 When @code{delq} deletes elements from the front of the list, it does so
1270 simply by advancing down the list and returning a sublist that starts
1271 after those elements:
1275 (delq 'a '(a b c)) @equiv{} (cdr '(a b c))
1279 When an element to be deleted appears in the middle of the list,
1280 removing it involves changing the @sc{cdr}s (@pxref{Setcdr}).
1284 (setq sample-list '(a b c (4)))
1285 @result{} (a b c (4))
1288 (delq 'a sample-list)
1293 @result{} (a b c (4))
1296 (delq 'c sample-list)
1305 Note that @code{(delq 'c sample-list)} modifies @code{sample-list} to
1306 splice out the third element, but @code{(delq 'a sample-list)} does not
1307 splice anything---it just returns a shorter list. Don't assume that a
1308 variable which formerly held the argument @var{list} now has fewer
1309 elements, or that it still holds the original list! Instead, save the
1310 result of @code{delq} and use that. Most often we store the result back
1311 into the variable that held the original list:
1314 (setq flowers (delq 'rose flowers))
1317 In the following example, the @code{(4)} that @code{delq} attempts to match
1318 and the @code{(4)} in the @code{sample-list} are not @code{eq}:
1322 (delq '(4) sample-list)
1327 @defun remq object list
1328 This function returns a copy of @var{list}, with all elements removed
1329 which are @code{eq} to @var{object}. The letter @samp{q} in @code{remq}
1330 says that it uses @code{eq} to compare @var{object} against the elements
1335 (setq sample-list '(a b c a b c))
1336 @result{} (a b c a b c)
1339 (remq 'a sample-list)
1344 @result{} (a b c a b c)
1348 The function @code{delq} offers a way to perform this operation
1349 destructively. See @ref{Sets And Lists}.
1352 The following three functions are like @code{memq}, @code{delq} and
1353 @code{remq}, but use @code{equal} rather than @code{eq} to compare
1354 elements. @xref{Equality Predicates}.
1356 @defun member object list
1357 The function @code{member} tests to see whether @var{object} is a member
1358 of @var{list}, comparing members with @var{object} using @code{equal}.
1359 If @var{object} is a member, @code{member} returns a list starting with
1360 its first occurrence in @var{list}. Otherwise, it returns @code{nil}.
1362 Compare this with @code{memq}:
1366 (member '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are @code{equal}.}
1370 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1374 ;; @r{Two strings with the same contents are @code{equal}.}
1375 (member "foo" '("foo" "bar"))
1376 @result{} ("foo" "bar")
1381 @defun delete object sequence
1382 If @code{sequence} is a list, this function destructively removes all
1383 elements @code{equal} to @var{object} from @var{sequence}. For lists,
1384 @code{delete} is to @code{delq} as @code{member} is to @code{memq}: it
1385 uses @code{equal} to compare elements with @var{object}, like
1386 @code{member}; when it finds an element that matches, it removes the
1387 element just as @code{delq} would.
1389 If @code{sequence} is a vector or string, @code{delete} returns a copy
1390 of @code{sequence} with all elements @code{equal} to @code{object}
1397 (delete '(2) '((2) (1) (2)))
1401 (delete '(2) [(2) (1) (2)])
1407 @defun remove object sequence
1408 This function is the non-destructive counterpart of @code{delete}. If
1409 returns a copy of @code{sequence}, a list, vector, or string, with
1410 elements @code{equal} to @code{object} removed. For example:
1414 (remove '(2) '((2) (1) (2)))
1418 (remove '(2) [(2) (1) (2)])
1425 @b{Common Lisp note:} The functions @code{member}, @code{delete} and
1426 @code{remove} in GNU Emacs Lisp are derived from Maclisp, not Common
1427 Lisp. The Common Lisp versions do not use @code{equal} to compare
1431 @defun member-ignore-case object list
1432 This function is like @code{member}, except that @var{object} should
1433 be a string and that it ignores differences in letter-case and text
1434 representation: upper-case and lower-case letters are treated as
1435 equal, and unibyte strings are converted to multibyte prior to
1439 @defun delete-dups list
1440 This function destructively removes all @code{equal} duplicates from
1441 @var{list}, stores the result in @var{list} and returns it. Of
1442 several @code{equal} occurrences of an element in @var{list},
1443 @code{delete-dups} keeps the first one.
1446 See also the function @code{add-to-list}, in @ref{Setting Variables},
1447 for another way to add an element to a list stored in a variable.
1449 @node Association Lists
1450 @section Association Lists
1451 @cindex association list
1454 An @dfn{association list}, or @dfn{alist} for short, records a mapping
1455 from keys to values. It is a list of cons cells called
1456 @dfn{associations}: the @sc{car} of each cons cell is the @dfn{key}, and the
1457 @sc{cdr} is the @dfn{associated value}.@footnote{This usage of ``key''
1458 is not related to the term ``key sequence''; it means a value used to
1459 look up an item in a table. In this case, the table is the alist, and
1460 the alist associations are the items.}
1462 Here is an example of an alist. The key @code{pine} is associated with
1463 the value @code{cones}; the key @code{oak} is associated with
1464 @code{acorns}; and the key @code{maple} is associated with @code{seeds}.
1474 The associated values in an alist may be any Lisp objects; so may the
1475 keys. For example, in the following alist, the symbol @code{a} is
1476 associated with the number @code{1}, and the string @code{"b"} is
1477 associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of
1484 Sometimes it is better to design an alist to store the associated
1485 value in the @sc{car} of the @sc{cdr} of the element. Here is an
1486 example of such an alist:
1489 ((rose red) (lily white) (buttercup yellow))
1493 Here we regard @code{red} as the value associated with @code{rose}. One
1494 advantage of this kind of alist is that you can store other related
1495 information---even a list of other items---in the @sc{cdr} of the
1496 @sc{cdr}. One disadvantage is that you cannot use @code{rassq} (see
1497 below) to find the element containing a given value. When neither of
1498 these considerations is important, the choice is a matter of taste, as
1499 long as you are consistent about it for any given alist.
1501 Note that the same alist shown above could be regarded as having the
1502 associated value in the @sc{cdr} of the element; the value associated
1503 with @code{rose} would be the list @code{(red)}.
1505 Association lists are often used to record information that you might
1506 otherwise keep on a stack, since new associations may be added easily to
1507 the front of the list. When searching an association list for an
1508 association with a given key, the first one found is returned, if there
1511 In Emacs Lisp, it is @emph{not} an error if an element of an
1512 association list is not a cons cell. The alist search functions simply
1513 ignore such elements. Many other versions of Lisp signal errors in such
1516 Note that property lists are similar to association lists in several
1517 respects. A property list behaves like an association list in which
1518 each key can occur only once. @xref{Property Lists}, for a comparison
1519 of property lists and association lists.
1521 @defun assoc key alist
1522 This function returns the first association for @var{key} in
1523 @var{alist}. It compares @var{key} against the alist elements using
1524 @code{equal} (@pxref{Equality Predicates}). It returns @code{nil} if no
1525 association in @var{alist} has a @sc{car} @code{equal} to @var{key}.
1529 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1530 @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1532 @result{} (oak . acorns)
1533 (cdr (assoc 'oak trees))
1535 (assoc 'birch trees)
1539 Here is another example, in which the keys and values are not symbols:
1542 (setq needles-per-cluster
1543 '((2 "Austrian Pine" "Red Pine")
1547 (cdr (assoc 3 needles-per-cluster))
1548 @result{} ("Pitch Pine")
1549 (cdr (assoc 2 needles-per-cluster))
1550 @result{} ("Austrian Pine" "Red Pine")
1554 The function @code{assoc-string} is much like @code{assoc} except
1555 that it ignores certain differences between strings. @xref{Text
1558 @defun rassoc value alist
1559 This function returns the first association with value @var{value} in
1560 @var{alist}. It returns @code{nil} if no association in @var{alist} has
1561 a @sc{cdr} @code{equal} to @var{value}.
1563 @code{rassoc} is like @code{assoc} except that it compares the @sc{cdr} of
1564 each @var{alist} association instead of the @sc{car}. You can think of
1565 this as ``reverse @code{assoc}'', finding the key for a given value.
1568 @defun assq key alist
1569 This function is like @code{assoc} in that it returns the first
1570 association for @var{key} in @var{alist}, but it makes the comparison
1571 using @code{eq} instead of @code{equal}. @code{assq} returns @code{nil}
1572 if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}.
1573 This function is used more often than @code{assoc}, since @code{eq} is
1574 faster than @code{equal} and most alists use symbols as keys.
1575 @xref{Equality Predicates}.
1578 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1579 @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1581 @result{} (pine . cones)
1584 On the other hand, @code{assq} is not usually useful in alists where the
1585 keys may not be symbols:
1589 '(("simple leaves" . oak)
1590 ("compound leaves" . horsechestnut)))
1592 (assq "simple leaves" leaves)
1594 (assoc "simple leaves" leaves)
1595 @result{} ("simple leaves" . oak)
1599 @defun rassq value alist
1600 This function returns the first association with value @var{value} in
1601 @var{alist}. It returns @code{nil} if no association in @var{alist} has
1602 a @sc{cdr} @code{eq} to @var{value}.
1604 @code{rassq} is like @code{assq} except that it compares the @sc{cdr} of
1605 each @var{alist} association instead of the @sc{car}. You can think of
1606 this as ``reverse @code{assq}'', finding the key for a given value.
1611 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1613 (rassq 'acorns trees)
1614 @result{} (oak . acorns)
1615 (rassq 'spores trees)
1619 Note that @code{rassq} cannot search for a value stored in the @sc{car}
1620 of the @sc{cdr} of an element:
1623 (setq colors '((rose red) (lily white) (buttercup yellow)))
1625 (rassq 'white colors)
1629 In this case, the @sc{cdr} of the association @code{(lily white)} is not
1630 the symbol @code{white}, but rather the list @code{(white)}. This
1631 becomes clearer if the association is written in dotted pair notation:
1634 (lily white) @equiv{} (lily . (white))
1638 @defun assoc-default key alist &optional test default
1639 This function searches @var{alist} for a match for @var{key}. For each
1640 element of @var{alist}, it compares the element (if it is an atom) or
1641 the element's @sc{car} (if it is a cons) against @var{key}, by calling
1642 @var{test} with two arguments: the element or its @sc{car}, and
1643 @var{key}. The arguments are passed in that order so that you can get
1644 useful results using @code{string-match} with an alist that contains
1645 regular expressions (@pxref{Regexp Search}). If @var{test} is omitted
1646 or @code{nil}, @code{equal} is used for comparison.
1648 If an alist element matches @var{key} by this criterion,
1649 then @code{assoc-default} returns a value based on this element.
1650 If the element is a cons, then the value is the element's @sc{cdr}.
1651 Otherwise, the return value is @var{default}.
1653 If no alist element matches @var{key}, @code{assoc-default} returns
1657 @defun copy-alist alist
1658 @cindex copying alists
1659 This function returns a two-level deep copy of @var{alist}: it creates a
1660 new copy of each association, so that you can alter the associations of
1661 the new alist without changing the old one.
1665 (setq needles-per-cluster
1666 '((2 . ("Austrian Pine" "Red Pine"))
1667 (3 . ("Pitch Pine"))
1669 (5 . ("White Pine"))))
1671 ((2 "Austrian Pine" "Red Pine")
1675 (setq copy (copy-alist needles-per-cluster))
1677 ((2 "Austrian Pine" "Red Pine")
1681 (eq needles-per-cluster copy)
1683 (equal needles-per-cluster copy)
1685 (eq (car needles-per-cluster) (car copy))
1687 (cdr (car (cdr needles-per-cluster)))
1688 @result{} ("Pitch Pine")
1690 (eq (cdr (car (cdr needles-per-cluster)))
1691 (cdr (car (cdr copy))))
1696 This example shows how @code{copy-alist} makes it possible to change
1697 the associations of one copy without affecting the other:
1701 (setcdr (assq 3 copy) '("Martian Vacuum Pine"))
1702 (cdr (assq 3 needles-per-cluster))
1703 @result{} ("Pitch Pine")
1708 @defun assq-delete-all key alist
1709 @tindex assq-delete-all
1710 This function deletes from @var{alist} all the elements whose @sc{car}
1711 is @code{eq} to @var{key}, much as if you used @code{delq} to delete
1712 each such element one by one. It returns the shortened alist, and
1713 often modifies the original list structure of @var{alist}. For
1714 correct results, use the return value of @code{assq-delete-all} rather
1715 than looking at the saved value of @var{alist}.
1718 (setq alist '((foo 1) (bar 2) (foo 3) (lose 4)))
1719 @result{} ((foo 1) (bar 2) (foo 3) (lose 4))
1720 (assq-delete-all 'foo alist)
1721 @result{} ((bar 2) (lose 4))
1723 @result{} ((foo 1) (bar 2) (lose 4))
1728 arch-tag: 31fb8a4e-4aa8-4a74-a206-aa00451394d4