2 @c This is part of the GNU Emacs Lisp Reference Manual.
3 @c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998 Free Software Foundation, Inc.
4 @c See the file elisp.texi for copying conditions.
5 @setfilename ../info/lists
6 @node Lists, Sequences Arrays Vectors, Strings and Characters, Top
9 @cindex element (of list)
11 A @dfn{list} represents a sequence of zero or more elements (which may
12 be any Lisp objects). The important difference between lists and
13 vectors is that two or more lists can share part of their structure; in
14 addition, you can insert or delete elements in a list without copying
18 * Cons Cells:: How lists are made out of cons cells.
19 * Lists as Boxes:: Graphical notation to explain lists.
20 * List-related Predicates:: Is this object a list? Comparing two lists.
21 * List Elements:: Extracting the pieces of a list.
22 * Building Lists:: Creating list structure.
23 * Modifying Lists:: Storing new pieces into an existing list.
24 * Sets And Lists:: A list can represent a finite mathematical set.
25 * Association Lists:: A list can represent a finite relation or mapping.
29 @section Lists and Cons Cells
30 @cindex lists and cons cells
31 @cindex @code{nil} and lists
33 Lists in Lisp are not a primitive data type; they are built up from
34 @dfn{cons cells}. A cons cell is a data object that represents an
35 ordered pair. It holds, or ``refers to,'' two Lisp objects, one labeled
36 as the @sc{car}, and the other labeled as the @sc{cdr}. These names are
37 traditional; see @ref{Cons Cell Type}. @sc{cdr} is pronounced
40 A list is a series of cons cells chained together, one cons cell per
41 element of the list. By convention, the @sc{car}s of the cons cells are
42 the elements of the list, and the @sc{cdr}s are used to chain the list:
43 the @sc{cdr} of each cons cell is the following cons cell. The @sc{cdr}
44 of the last cons cell is @code{nil}. This asymmetry between the
45 @sc{car} and the @sc{cdr} is entirely a matter of convention; at the
46 level of cons cells, the @sc{car} and @sc{cdr} slots have the same
49 @cindex list structure
50 Because most cons cells are used as part of lists, the phrase
51 @dfn{list structure} has come to mean any structure made out of cons
54 The symbol @code{nil} is considered a list as well as a symbol; it is
55 the list with no elements. For convenience, the symbol @code{nil} is
56 considered to have @code{nil} as its @sc{cdr} (and also as its
59 The @sc{cdr} of any nonempty list @var{l} is a list containing all the
60 elements of @var{l} except the first.
63 @comment node-name, next, previous, up
64 @section Lists as Linked Pairs of Boxes
65 @cindex box representation for lists
66 @cindex lists represented as boxes
67 @cindex cons cell as box
69 A cons cell can be illustrated as a pair of boxes. The first box
70 represents the @sc{car} and the second box represents the @sc{cdr}.
71 Here is an illustration of the two-element list, @code{(tulip lily)},
72 made from two cons cells:
76 --------------- ---------------
77 | car | cdr | | car | cdr |
78 | tulip | o---------->| lily | nil |
80 --------------- ---------------
84 Each pair of boxes represents a cons cell. Each box ``refers to'',
85 ``points to'' or ``holds'' a Lisp object. (These terms are
86 synonymous.) The first box, which describes the @sc{car} of the first
87 cons cell, contains the symbol @code{tulip}. The arrow from the
88 @sc{cdr} box of the first cons cell to the second cons cell indicates
89 that the @sc{cdr} of the first cons cell is the second cons cell.
91 The same list can be illustrated in a different sort of box notation
105 Here is a more complex illustration, showing the three-element list,
106 @code{((pine needles) oak maple)}, the first element of which is a
111 --- --- --- --- --- ---
112 | | |--> | | |--> | | |--> nil
113 --- --- --- --- --- ---
119 --> | | |--> | | |--> nil
127 The same list represented in the first box notation looks like this:
131 -------------- -------------- --------------
132 | car | cdr | | car | cdr | | car | cdr |
133 | o | o------->| oak | o------->| maple | nil |
135 -- | --------- -------------- --------------
138 | -------------- ----------------
139 | | car | cdr | | car | cdr |
140 ------>| pine | o------->| needles | nil |
142 -------------- ----------------
146 @xref{Cons Cell Type}, for the read and print syntax of cons cells and
147 lists, and for more ``box and arrow'' illustrations of lists.
149 @node List-related Predicates
150 @section Predicates on Lists
152 The following predicates test whether a Lisp object is an atom, is a
153 cons cell or is a list, or whether it is the distinguished object
154 @code{nil}. (Many of these predicates can be defined in terms of the
155 others, but they are used so often that it is worth having all of them.)
158 This function returns @code{t} if @var{object} is a cons cell, @code{nil}
159 otherwise. @code{nil} is not a cons cell, although it @emph{is} a list.
164 This function returns @code{t} if @var{object} is an atom, @code{nil}
165 otherwise. All objects except cons cells are atoms. The symbol
166 @code{nil} is an atom and is also a list; it is the only Lisp object
170 (atom @var{object}) @equiv{} (not (consp @var{object}))
175 This function returns @code{t} if @var{object} is a cons cell or
176 @code{nil}. Otherwise, it returns @code{nil}.
191 This function is the opposite of @code{listp}: it returns @code{t} if
192 @var{object} is not a list. Otherwise, it returns @code{nil}.
195 (listp @var{object}) @equiv{} (not (nlistp @var{object}))
200 This function returns @code{t} if @var{object} is @code{nil}, and
201 returns @code{nil} otherwise. This function is identical to @code{not},
202 but as a matter of clarity we use @code{null} when @var{object} is
203 considered a list and @code{not} when it is considered a truth value
204 (see @code{not} in @ref{Combining Conditions}).
221 @section Accessing Elements of Lists
222 @cindex list elements
225 This function returns the value referred to by the first slot of the
226 cons cell @var{cons-cell}. Expressed another way, this function
227 returns the @sc{car} of @var{cons-cell}.
229 As a special case, if @var{cons-cell} is @code{nil}, then @code{car}
230 is defined to return @code{nil}; therefore, any list is a valid argument
231 for @code{car}. An error is signaled if the argument is not a cons cell
247 This function returns the value referred to by the second slot of
248 the cons cell @var{cons-cell}. Expressed another way, this function
249 returns the @sc{cdr} of @var{cons-cell}.
251 As a special case, if @var{cons-cell} is @code{nil}, then @code{cdr}
252 is defined to return @code{nil}; therefore, any list is a valid argument
253 for @code{cdr}. An error is signaled if the argument is not a cons cell
268 @defun car-safe object
269 This function lets you take the @sc{car} of a cons cell while avoiding
270 errors for other data types. It returns the @sc{car} of @var{object} if
271 @var{object} is a cons cell, @code{nil} otherwise. This is in contrast
272 to @code{car}, which signals an error if @var{object} is not a list.
276 (car-safe @var{object})
278 (let ((x @var{object}))
286 @defun cdr-safe object
287 This function lets you take the @sc{cdr} of a cons cell while
288 avoiding errors for other data types. It returns the @sc{cdr} of
289 @var{object} if @var{object} is a cons cell, @code{nil} otherwise.
290 This is in contrast to @code{cdr}, which signals an error if
291 @var{object} is not a list.
295 (cdr-safe @var{object})
297 (let ((x @var{object}))
307 This macro is a way of examining the @sc{car} of a list,
308 and taking it off the list, all at once. It is new in Emacs 21.
310 It operates on the list which is stored in the symbol @var{listname}.
311 It removes this element from the list by setting @var{listname}
312 to the @sc{cdr} of its old value---but it also returns the @sc{car}
313 of that list, which is the element being removed.
326 This function returns the @var{n}th element of @var{list}. Elements
327 are numbered starting with zero, so the @sc{car} of @var{list} is
328 element number zero. If the length of @var{list} is @var{n} or less,
329 the value is @code{nil}.
331 If @var{n} is negative, @code{nth} returns the first element of
347 (nth n x) @equiv{} (car (nthcdr n x))
351 The function @code{elt} is similar, but applies to any kind of sequence.
352 For historical reasons, it takes its arguments in the opposite order.
353 @xref{Sequence Functions}.
357 This function returns the @var{n}th @sc{cdr} of @var{list}. In other
358 words, it skips past the first @var{n} links of @var{list} and returns
361 If @var{n} is zero or negative, @code{nthcdr} returns all of
362 @var{list}. If the length of @var{list} is @var{n} or less,
363 @code{nthcdr} returns @code{nil}.
367 (nthcdr 1 '(1 2 3 4))
371 (nthcdr 10 '(1 2 3 4))
375 (nthcdr -3 '(1 2 3 4))
381 @defun safe-length list
383 This function returns the length of @var{list}, with no risk
384 of either an error or an infinite loop.
386 If @var{list} is not really a list, @code{safe-length} returns 0. If
387 @var{list} is circular, it returns a finite value which is at least the
388 number of distinct elements.
391 The most common way to compute the length of a list, when you are not
392 worried that it may be circular, is with @code{length}. @xref{Sequence
395 @defun caar cons-cell
397 This is the same as @code{(car (car @var{cons-cell}))}.
400 @defun cadr cons-cell
402 This is the same as @code{(car (cdr @var{cons-cell}))}
403 or @code{(nth 1 @var{cons-cell})}.
406 @defun cdar cons-cell
408 This is the same as @code{(cdr (car @var{cons-cell}))}.
411 @defun cddr cons-cell
413 This is the same as @code{(cdr (cdr @var{cons-cell}))}
414 or @code{(nthcdr 2 @var{cons-cell})}.
418 @comment node-name, next, previous, up
419 @section Building Cons Cells and Lists
421 @cindex building lists
423 Many functions build lists, as lists reside at the very heart of Lisp.
424 @code{cons} is the fundamental list-building function; however, it is
425 interesting to note that @code{list} is used more times in the source
426 code for Emacs than @code{cons}.
428 @defun cons object1 object2
429 This function is the fundamental function used to build new list
430 structure. It creates a new cons cell, making @var{object1} the
431 @sc{car}, and @var{object2} the @sc{cdr}. It then returns the new cons
432 cell. The arguments @var{object1} and @var{object2} may be any Lisp
433 objects, but most often @var{object2} is a list.
451 @code{cons} is often used to add a single element to the front of a
452 list. This is called @dfn{consing the element onto the list}. For
456 (setq list (cons newelt list))
459 Note that there is no conflict between the variable named @code{list}
460 used in this example and the function named @code{list} described below;
461 any symbol can serve both purposes.
465 @defmac push newelt listname
466 This macro provides an alternative way to write
467 @code{(setq @var{listname} (cons @var{newelt} @var{listname}))}.
468 It is new in Emacs 21.
471 @defun list &rest objects
472 This function creates a list with @var{objects} as its elements. The
473 resulting list is always @code{nil}-terminated. If no @var{objects}
474 are given, the empty list is returned.
479 @result{} (1 2 3 4 5)
482 (list 1 2 '(3 4 5) 'foo)
483 @result{} (1 2 (3 4 5) foo)
492 @defun make-list length object
493 This function creates a list of length @var{length}, in which all the
494 elements have the identical value @var{object}. Compare
495 @code{make-list} with @code{make-string} (@pxref{Creating Strings}).
500 @result{} (pigs pigs pigs)
509 @defun append &rest sequences
510 @cindex copying lists
511 This function returns a list containing all the elements of
512 @var{sequences}. The @var{sequences} may be lists, vectors,
513 bool-vectors, or strings, but the last one should usually be a list.
514 All arguments except the last one are copied, so none of the arguments
515 is altered. (See @code{nconc} in @ref{Rearrangement}, for a way to join
516 lists with no copying.)
518 More generally, the final argument to @code{append} may be any Lisp
519 object. The final argument is not copied or converted; it becomes the
520 @sc{cdr} of the last cons cell in the new list. If the final argument
521 is itself a list, then its elements become in effect elements of the
522 result list. If the final element is not a list, the result is a
523 ``dotted list'' since its final @sc{cdr} is not @code{nil} as required
526 The @code{append} function also allows integers as arguments. It
527 converts them to strings of digits, making up the decimal print
528 representation of the integer, and then uses the strings instead of the
529 original integers. @strong{Don't use this feature; we plan to eliminate
530 it. If you already use this feature, change your programs now!} The
531 proper way to convert an integer to a decimal number in this way is with
532 @code{format} (@pxref{Formatting Strings}) or @code{number-to-string}
533 (@pxref{String Conversion}).
536 Here is an example of using @code{append}:
540 (setq trees '(pine oak))
542 (setq more-trees (append '(maple birch) trees))
543 @result{} (maple birch pine oak)
550 @result{} (maple birch pine oak)
553 (eq trees (cdr (cdr more-trees)))
558 You can see how @code{append} works by looking at a box diagram. The
559 variable @code{trees} is set to the list @code{(pine oak)} and then the
560 variable @code{more-trees} is set to the list @code{(maple birch pine
561 oak)}. However, the variable @code{trees} continues to refer to the
568 | --- --- --- --- -> --- --- --- ---
569 --> | | |--> | | |--> | | |--> | | |--> nil
570 --- --- --- --- --- --- --- ---
573 --> maple -->birch --> pine --> oak
577 An empty sequence contributes nothing to the value returned by
578 @code{append}. As a consequence of this, a final @code{nil} argument
579 forces a copy of the previous argument:
587 (setq wood (append trees nil))
601 This once was the usual way to copy a list, before the function
602 @code{copy-sequence} was invented. @xref{Sequences Arrays Vectors}.
604 Here we show the use of vectors and strings as arguments to @code{append}:
608 (append [a b] "cd" nil)
609 @result{} (a b 99 100)
613 With the help of @code{apply} (@pxref{Calling Functions}), we can append
614 all the lists in a list of lists:
618 (apply 'append '((a b c) nil (x y z) nil))
619 @result{} (a b c x y z)
623 If no @var{sequences} are given, @code{nil} is returned:
632 Here are some examples where the final argument is not a list:
638 @result{} (x y . [z])
642 The second example shows that when the final argument is a sequence but
643 not a list, the sequence's elements do not become elements of the
644 resulting list. Instead, the sequence becomes the final @sc{cdr}, like
645 any other non-list final argument.
648 This function creates a new list whose elements are the elements of
649 @var{list}, but in reverse order. The original argument @var{list} is
666 @node Modifying Lists
667 @section Modifying Existing List Structure
668 @cindex destructive list operations
670 You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the
671 primitives @code{setcar} and @code{setcdr}. We call these ``destructive''
672 operations because they change existing list structure.
674 @cindex CL note---@code{rplaca} vrs @code{setcar}
678 @b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and
679 @code{rplacd} to alter list structure; they change structure the same
680 way as @code{setcar} and @code{setcdr}, but the Common Lisp functions
681 return the cons cell while @code{setcar} and @code{setcdr} return the
682 new @sc{car} or @sc{cdr}.
686 * Setcar:: Replacing an element in a list.
687 * Setcdr:: Replacing part of the list backbone.
688 This can be used to remove or add elements.
689 * Rearrangement:: Reordering the elements in a list; combining lists.
693 @subsection Altering List Elements with @code{setcar}
695 Changing the @sc{car} of a cons cell is done with @code{setcar}. When
696 used on a list, @code{setcar} replaces one element of a list with a
699 @defun setcar cons object
700 This function stores @var{object} as the new @sc{car} of @var{cons},
701 replacing its previous @sc{car}. In other words, it changes the
702 @sc{car} slot of @var{cons} to refer to @var{object}. It returns the
703 value @var{object}. For example:
721 When a cons cell is part of the shared structure of several lists,
722 storing a new @sc{car} into the cons changes one element of each of
723 these lists. Here is an example:
727 ;; @r{Create two lists that are partly shared.}
730 (setq x2 (cons 'z (cdr x1)))
735 ;; @r{Replace the @sc{car} of a shared link.}
736 (setcar (cdr x1) 'foo)
738 x1 ; @r{Both lists are changed.}
745 ;; @r{Replace the @sc{car} of a link that is not shared.}
748 x1 ; @r{Only one list is changed.}
749 @result{} (baz foo c)
755 Here is a graphical depiction of the shared structure of the two lists
756 in the variables @code{x1} and @code{x2}, showing why replacing @code{b}
761 --- --- --- --- --- ---
762 x1---> | | |----> | | |--> | | |--> nil
763 --- --- --- --- --- ---
777 Here is an alternative form of box diagram, showing the same relationship:
782 -------------- -------------- --------------
783 | car | cdr | | car | cdr | | car | cdr |
784 | a | o------->| b | o------->| c | nil |
786 -------------- | -------------- --------------
798 @subsection Altering the CDR of a List
800 The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}:
802 @defun setcdr cons object
803 This function stores @var{object} as the new @sc{cdr} of @var{cons},
804 replacing its previous @sc{cdr}. In other words, it changes the
805 @sc{cdr} slot of @var{cons} to refer to @var{object}. It returns the
809 Here is an example of replacing the @sc{cdr} of a list with a
810 different list. All but the first element of the list are removed in
811 favor of a different sequence of elements. The first element is
812 unchanged, because it resides in the @sc{car} of the list, and is not
813 reached via the @sc{cdr}.
830 You can delete elements from the middle of a list by altering the
831 @sc{cdr}s of the cons cells in the list. For example, here we delete
832 the second element, @code{b}, from the list @code{(a b c)}, by changing
833 the @sc{cdr} of the first cons cell:
839 (setcdr x1 (cdr (cdr x1)))
847 Here is the result in box notation:
853 -------------- | -------------- | --------------
854 | car | cdr | | | car | cdr | -->| car | cdr |
855 | a | o----- | b | o-------->| c | nil |
857 -------------- -------------- --------------
862 The second cons cell, which previously held the element @code{b}, still
863 exists and its @sc{car} is still @code{b}, but it no longer forms part
866 It is equally easy to insert a new element by changing @sc{cdr}s:
872 (setcdr x1 (cons 'd (cdr x1)))
879 Here is this result in box notation:
883 -------------- ------------- -------------
884 | car | cdr | | car | cdr | | car | cdr |
885 | a | o | -->| b | o------->| c | nil |
886 | | | | | | | | | | |
887 --------- | -- | ------------- -------------
900 @subsection Functions that Rearrange Lists
901 @cindex rearrangement of lists
902 @cindex modification of lists
904 Here are some functions that rearrange lists ``destructively'' by
905 modifying the @sc{cdr}s of their component cons cells. We call these
906 functions ``destructive'' because they chew up the original lists passed
907 to them as arguments, relinking their cons cells to form a new list that
908 is the returned value.
911 See @code{delq}, in @ref{Sets And Lists}, for another function
912 that modifies cons cells.
915 The function @code{delq} in the following section is another example
916 of destructive list manipulation.
919 @defun nconc &rest lists
920 @cindex concatenating lists
921 @cindex joining lists
922 This function returns a list containing all the elements of @var{lists}.
923 Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are
924 @emph{not} copied. Instead, the last @sc{cdr} of each of the
925 @var{lists} is changed to refer to the following list. The last of the
926 @var{lists} is not altered. For example:
935 @result{} (1 2 3 4 5)
939 @result{} (1 2 3 4 5)
943 Since the last argument of @code{nconc} is not itself modified, it is
944 reasonable to use a constant list, such as @code{'(4 5)}, as in the
945 above example. For the same reason, the last argument need not be a
955 @result{} (1 2 3 . z)
959 @result{} (1 2 3 . z)
963 However, the other arguments (all but the last) must be lists.
965 A common pitfall is to use a quoted constant list as a non-last
966 argument to @code{nconc}. If you do this, your program will change
967 each time you run it! Here is what happens:
971 (defun add-foo (x) ; @r{We want this function to add}
972 (nconc '(foo) x)) ; @r{@code{foo} to the front of its arg.}
976 (symbol-function 'add-foo)
977 @result{} (lambda (x) (nconc (quote (foo)) x))
981 (setq xx (add-foo '(1 2))) ; @r{It seems to work.}
985 (setq xy (add-foo '(3 4))) ; @r{What happened?}
986 @result{} (foo 1 2 3 4)
994 (symbol-function 'add-foo)
995 @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x)))
1000 @defun nreverse list
1001 @cindex reversing a list
1002 This function reverses the order of the elements of @var{list}.
1003 Unlike @code{reverse}, @code{nreverse} alters its argument by reversing
1004 the @sc{cdr}s in the cons cells forming the list. The cons cell that
1005 used to be the last one in @var{list} becomes the first cons cell of the
1022 ;; @r{The cons cell that was first is now last.}
1028 To avoid confusion, we usually store the result of @code{nreverse}
1029 back in the same variable which held the original list:
1032 (setq x (nreverse x))
1035 Here is the @code{nreverse} of our favorite example, @code{(a b c)},
1036 presented graphically:
1040 @r{Original list head:} @r{Reversed list:}
1041 ------------- ------------- ------------
1042 | car | cdr | | car | cdr | | car | cdr |
1043 | a | nil |<-- | b | o |<-- | c | o |
1044 | | | | | | | | | | | | |
1045 ------------- | --------- | - | -------- | -
1047 ------------- ------------
1052 @defun sort list predicate
1054 @cindex sorting lists
1055 This function sorts @var{list} stably, though destructively, and
1056 returns the sorted list. It compares elements using @var{predicate}. A
1057 stable sort is one in which elements with equal sort keys maintain their
1058 relative order before and after the sort. Stability is important when
1059 successive sorts are used to order elements according to different
1062 The argument @var{predicate} must be a function that accepts two
1063 arguments. It is called with two elements of @var{list}. To get an
1064 increasing order sort, the @var{predicate} should return @code{t} if the
1065 first element is ``less than'' the second, or @code{nil} if not.
1067 The comparison function @var{predicate} must give reliable results for
1068 any given pair of arguments, at least within a single call to
1069 @code{sort}. It must be @dfn{antisymmetric}; that is, if @var{a} is
1070 less than @var{b}, @var{b} must not be less than @var{a}. It must be
1071 @dfn{transitive}---that is, if @var{a} is less than @var{b}, and @var{b}
1072 is less than @var{c}, then @var{a} must be less than @var{c}. If you
1073 use a comparison function which does not meet these requirements, the
1074 result of @code{sort} is unpredictable.
1076 The destructive aspect of @code{sort} is that it rearranges the cons
1077 cells forming @var{list} by changing @sc{cdr}s. A nondestructive sort
1078 function would create new cons cells to store the elements in their
1079 sorted order. If you wish to make a sorted copy without destroying the
1080 original, copy it first with @code{copy-sequence} and then sort.
1082 Sorting does not change the @sc{car}s of the cons cells in @var{list};
1083 the cons cell that originally contained the element @code{a} in
1084 @var{list} still has @code{a} in its @sc{car} after sorting, but it now
1085 appears in a different position in the list due to the change of
1086 @sc{cdr}s. For example:
1090 (setq nums '(1 3 2 6 5 4 0))
1091 @result{} (1 3 2 6 5 4 0)
1095 @result{} (0 1 2 3 4 5 6)
1099 @result{} (1 2 3 4 5 6)
1104 @strong{Warning}: Note that the list in @code{nums} no longer contains
1105 0; this is the same cons cell that it was before, but it is no longer
1106 the first one in the list. Don't assume a variable that formerly held
1107 the argument now holds the entire sorted list! Instead, save the result
1108 of @code{sort} and use that. Most often we store the result back into
1109 the variable that held the original list:
1112 (setq nums (sort nums '<))
1115 @xref{Sorting}, for more functions that perform sorting.
1116 See @code{documentation} in @ref{Accessing Documentation}, for a
1117 useful example of @code{sort}.
1120 @node Sets And Lists
1121 @section Using Lists as Sets
1122 @cindex lists as sets
1125 A list can represent an unordered mathematical set---simply consider a
1126 value an element of a set if it appears in the list, and ignore the
1127 order of the list. To form the union of two sets, use @code{append} (as
1128 long as you don't mind having duplicate elements). Other useful
1129 functions for sets include @code{memq} and @code{delq}, and their
1130 @code{equal} versions, @code{member} and @code{delete}.
1132 @cindex CL note---lack @code{union}, @code{intersection}
1134 @b{Common Lisp note:} Common Lisp has functions @code{union} (which
1135 avoids duplicate elements) and @code{intersection} for set operations,
1136 but GNU Emacs Lisp does not have them. You can write them in Lisp if
1140 @defun memq object list
1141 @cindex membership in a list
1142 This function tests to see whether @var{object} is a member of
1143 @var{list}. If it is, @code{memq} returns a list starting with the
1144 first occurrence of @var{object}. Otherwise, it returns @code{nil}.
1145 The letter @samp{q} in @code{memq} says that it uses @code{eq} to
1146 compare @var{object} against the elements of the list. For example:
1150 (memq 'b '(a b c b a))
1154 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1160 @defun delq object list
1161 @cindex deletion of elements
1162 This function destructively removes all elements @code{eq} to
1163 @var{object} from @var{list}. The letter @samp{q} in @code{delq} says
1164 that it uses @code{eq} to compare @var{object} against the elements of
1165 the list, like @code{memq}.
1168 When @code{delq} deletes elements from the front of the list, it does so
1169 simply by advancing down the list and returning a sublist that starts
1170 after those elements:
1174 (delq 'a '(a b c)) @equiv{} (cdr '(a b c))
1178 When an element to be deleted appears in the middle of the list,
1179 removing it involves changing the @sc{cdr}s (@pxref{Setcdr}).
1183 (setq sample-list '(a b c (4)))
1184 @result{} (a b c (4))
1187 (delq 'a sample-list)
1192 @result{} (a b c (4))
1195 (delq 'c sample-list)
1204 Note that @code{(delq 'c sample-list)} modifies @code{sample-list} to
1205 splice out the third element, but @code{(delq 'a sample-list)} does not
1206 splice anything---it just returns a shorter list. Don't assume that a
1207 variable which formerly held the argument @var{list} now has fewer
1208 elements, or that it still holds the original list! Instead, save the
1209 result of @code{delq} and use that. Most often we store the result back
1210 into the variable that held the original list:
1213 (setq flowers (delq 'rose flowers))
1216 In the following example, the @code{(4)} that @code{delq} attempts to match
1217 and the @code{(4)} in the @code{sample-list} are not @code{eq}:
1221 (delq '(4) sample-list)
1226 The following two functions are like @code{memq} and @code{delq} but use
1227 @code{equal} rather than @code{eq} to compare elements. @xref{Equality
1230 @defun member object list
1231 The function @code{member} tests to see whether @var{object} is a member
1232 of @var{list}, comparing members with @var{object} using @code{equal}.
1233 If @var{object} is a member, @code{member} returns a list starting with
1234 its first occurrence in @var{list}. Otherwise, it returns @code{nil}.
1236 Compare this with @code{memq}:
1240 (member '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are @code{equal}.}
1244 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1248 ;; @r{Two strings with the same contents are @code{equal}.}
1249 (member "foo" '("foo" "bar"))
1250 @result{} ("foo" "bar")
1255 @defun delete object list
1256 This function destructively removes all elements @code{equal} to
1257 @var{object} from @var{list}. It is to @code{delq} as @code{member} is
1258 to @code{memq}: it uses @code{equal} to compare elements with
1259 @var{object}, like @code{member}; when it finds an element that matches,
1260 it removes the element just as @code{delq} would. For example:
1264 (delete '(2) '((2) (1) (2)))
1271 @b{Common Lisp note:} The functions @code{member} and @code{delete} in
1272 GNU Emacs Lisp are derived from Maclisp, not Common Lisp. The Common
1273 Lisp versions do not use @code{equal} to compare elements.
1276 See also the function @code{add-to-list}, in @ref{Setting Variables},
1277 for another way to add an element to a list stored in a variable.
1279 @node Association Lists
1280 @section Association Lists
1281 @cindex association list
1284 An @dfn{association list}, or @dfn{alist} for short, records a mapping
1285 from keys to values. It is a list of cons cells called
1286 @dfn{associations}: the @sc{car} of each cons cell is the @dfn{key}, and the
1287 @sc{cdr} is the @dfn{associated value}.@footnote{This usage of ``key''
1288 is not related to the term ``key sequence''; it means a value used to
1289 look up an item in a table. In this case, the table is the alist, and
1290 the alist associations are the items.}
1292 Here is an example of an alist. The key @code{pine} is associated with
1293 the value @code{cones}; the key @code{oak} is associated with
1294 @code{acorns}; and the key @code{maple} is associated with @code{seeds}.
1304 The associated values in an alist may be any Lisp objects; so may the
1305 keys. For example, in the following alist, the symbol @code{a} is
1306 associated with the number @code{1}, and the string @code{"b"} is
1307 associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of
1314 Sometimes it is better to design an alist to store the associated
1315 value in the @sc{car} of the @sc{cdr} of the element. Here is an
1319 '((rose red) (lily white) (buttercup yellow))
1323 Here we regard @code{red} as the value associated with @code{rose}. One
1324 advantage of this kind of alist is that you can store other related
1325 information---even a list of other items---in the @sc{cdr} of the
1326 @sc{cdr}. One disadvantage is that you cannot use @code{rassq} (see
1327 below) to find the element containing a given value. When neither of
1328 these considerations is important, the choice is a matter of taste, as
1329 long as you are consistent about it for any given alist.
1331 Note that the same alist shown above could be regarded as having the
1332 associated value in the @sc{cdr} of the element; the value associated
1333 with @code{rose} would be the list @code{(red)}.
1335 Association lists are often used to record information that you might
1336 otherwise keep on a stack, since new associations may be added easily to
1337 the front of the list. When searching an association list for an
1338 association with a given key, the first one found is returned, if there
1341 In Emacs Lisp, it is @emph{not} an error if an element of an
1342 association list is not a cons cell. The alist search functions simply
1343 ignore such elements. Many other versions of Lisp signal errors in such
1346 Note that property lists are similar to association lists in several
1347 respects. A property list behaves like an association list in which
1348 each key can occur only once. @xref{Property Lists}, for a comparison
1349 of property lists and association lists.
1351 @defun assoc key alist
1352 This function returns the first association for @var{key} in
1353 @var{alist}. It compares @var{key} against the alist elements using
1354 @code{equal} (@pxref{Equality Predicates}). It returns @code{nil} if no
1355 association in @var{alist} has a @sc{car} @code{equal} to @var{key}.
1359 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1360 @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1362 @result{} (oak . acorns)
1363 (cdr (assoc 'oak trees))
1365 (assoc 'birch trees)
1369 Here is another example, in which the keys and values are not symbols:
1372 (setq needles-per-cluster
1373 '((2 "Austrian Pine" "Red Pine")
1377 (cdr (assoc 3 needles-per-cluster))
1378 @result{} ("Pitch Pine")
1379 (cdr (assoc 2 needles-per-cluster))
1380 @result{} ("Austrian Pine" "Red Pine")
1384 The functions @code{assoc-ignore-representation} and
1385 @code{assoc-ignore-case} are much like @code{assoc} except using
1386 @code{compare-strings} to do the comparison. @xref{Text Comparison}.
1388 @defun rassoc value alist
1389 This function returns the first association with value @var{value} in
1390 @var{alist}. It returns @code{nil} if no association in @var{alist} has
1391 a @sc{cdr} @code{equal} to @var{value}.
1393 @code{rassoc} is like @code{assoc} except that it compares the @sc{cdr} of
1394 each @var{alist} association instead of the @sc{car}. You can think of
1395 this as ``reverse @code{assoc}'', finding the key for a given value.
1398 @defun assq key alist
1399 This function is like @code{assoc} in that it returns the first
1400 association for @var{key} in @var{alist}, but it makes the comparison
1401 using @code{eq} instead of @code{equal}. @code{assq} returns @code{nil}
1402 if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}.
1403 This function is used more often than @code{assoc}, since @code{eq} is
1404 faster than @code{equal} and most alists use symbols as keys.
1405 @xref{Equality Predicates}.
1408 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1409 @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1411 @result{} (pine . cones)
1414 On the other hand, @code{assq} is not usually useful in alists where the
1415 keys may not be symbols:
1419 '(("simple leaves" . oak)
1420 ("compound leaves" . horsechestnut)))
1422 (assq "simple leaves" leaves)
1424 (assoc "simple leaves" leaves)
1425 @result{} ("simple leaves" . oak)
1429 @defun rassq value alist
1430 This function returns the first association with value @var{value} in
1431 @var{alist}. It returns @code{nil} if no association in @var{alist} has
1432 a @sc{cdr} @code{eq} to @var{value}.
1434 @code{rassq} is like @code{assq} except that it compares the @sc{cdr} of
1435 each @var{alist} association instead of the @sc{car}. You can think of
1436 this as ``reverse @code{assq}'', finding the key for a given value.
1441 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1443 (rassq 'acorns trees)
1444 @result{} (oak . acorns)
1445 (rassq 'spores trees)
1449 Note that @code{rassq} cannot search for a value stored in the @sc{car}
1450 of the @sc{cdr} of an element:
1453 (setq colors '((rose red) (lily white) (buttercup yellow)))
1455 (rassq 'white colors)
1459 In this case, the @sc{cdr} of the association @code{(lily white)} is not
1460 the symbol @code{white}, but rather the list @code{(white)}. This
1461 becomes clearer if the association is written in dotted pair notation:
1464 (lily white) @equiv{} (lily . (white))
1468 @tindex assoc-default
1469 @defun assoc-default key alist test default
1470 This function searches @var{alist} for a match for @var{key}. For each
1471 element of @var{alist}, it compares the element (if it is an atom) or
1472 the element's @sc{car} (if it is a cons) against @var{key}, by calling
1473 @var{test} with two arguments: the element or its @sc{car}, and
1474 @var{key}. The arguments are passed in that order so that you can get
1475 useful results using @code{string-match} with an alist that contains
1476 regular expressions (@pxref{Regexp Search}). If @var{test} is omitted
1477 or @code{nil}, @code{equal} is used for comparison.
1479 If an alist element matches @var{key} by this criterion,
1480 then @code{assoc-default} returns a value based on this element.
1481 If the element is a cons, then the value is the element's @sc{cdr}.
1482 Otherwise, the return value is @var{default}.
1484 If no alist element matches @var{key}, @code{assoc-default} returns
1488 @defun copy-alist alist
1489 @cindex copying alists
1490 This function returns a two-level deep copy of @var{alist}: it creates a
1491 new copy of each association, so that you can alter the associations of
1492 the new alist without changing the old one.
1496 (setq needles-per-cluster
1497 '((2 . ("Austrian Pine" "Red Pine"))
1498 (3 . ("Pitch Pine"))
1500 (5 . ("White Pine"))))
1502 ((2 "Austrian Pine" "Red Pine")
1506 (setq copy (copy-alist needles-per-cluster))
1508 ((2 "Austrian Pine" "Red Pine")
1512 (eq needles-per-cluster copy)
1514 (equal needles-per-cluster copy)
1516 (eq (car needles-per-cluster) (car copy))
1518 (cdr (car (cdr needles-per-cluster)))
1519 @result{} ("Pitch Pine")
1521 (eq (cdr (car (cdr needles-per-cluster)))
1522 (cdr (car (cdr copy))))
1527 This example shows how @code{copy-alist} makes it possible to change
1528 the associations of one copy without affecting the other:
1532 (setcdr (assq 3 copy) '("Martian Vacuum Pine"))
1533 (cdr (assq 3 needles-per-cluster))
1534 @result{} ("Pitch Pine")
1539 @defun assoc-delete-all key alist
1540 @tindex assoc-delete-all
1541 This function deletes from @var{alist} all the elements whose @sc{car}
1542 is @var{key}. It returns the modified alist.
1545 (assoc-delete-all 'foo
1546 '((foo 1) (bar 2) (foo 3) (lose 4)))
1547 @result{} ((bar 2) (lose 4))