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 ``points 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 ``contains'' 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 pointed to by the first pointer 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 pointed to by the second pointer 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}))
306 This function returns the @var{n}th element of @var{list}. Elements
307 are numbered starting with zero, so the @sc{car} of @var{list} is
308 element number zero. If the length of @var{list} is @var{n} or less,
309 the value is @code{nil}.
311 If @var{n} is negative, @code{nth} returns the first element of
327 (nth n x) @equiv{} (car (nthcdr n x))
331 The function @code{elt} is similar, but applies to any kind of sequence.
332 For historical reasons, it takes its arguments in the opposite order.
333 @xref{Sequence Functions}.
337 This function returns the @var{n}th @sc{cdr} of @var{list}. In other
338 words, it skips past the first @var{n} links of @var{list} and returns
341 If @var{n} is zero or negative, @code{nthcdr} returns all of
342 @var{list}. If the length of @var{list} is @var{n} or less,
343 @code{nthcdr} returns @code{nil}.
347 (nthcdr 1 '(1 2 3 4))
351 (nthcdr 10 '(1 2 3 4))
355 (nthcdr -3 '(1 2 3 4))
361 @defun safe-length list
363 This function returns the length of @var{list}, with no risk
364 of either an error or an infinite loop.
366 If @var{list} is not really a list, @code{safe-length} returns 0. If
367 @var{list} is circular, it returns a finite value which is at least the
368 number of distinct elements.
371 The most common way to compute the length of a list, when you are not
372 worried that it may be circular, is with @code{length}. @xref{Sequence
375 @defun caar cons-cell
377 This is the same as @code{(car (car @var{cons-cell}))}.
380 @defun cadr cons-cell
382 This is the same as @code{(car (cdr @var{cons-cell}))}
383 or @code{(nth 1 @var{cons-cell})}.
386 @defun cdar cons-cell
388 This is the same as @code{(cdr (car @var{cons-cell}))}.
391 @defun cddr cons-cell
393 This is the same as @code{(cdr (cdr @var{cons-cell}))}
394 or @code{(nthcdr 2 @var{cons-cell})}.
398 @comment node-name, next, previous, up
399 @section Building Cons Cells and Lists
401 @cindex building lists
403 Many functions build lists, as lists reside at the very heart of Lisp.
404 @code{cons} is the fundamental list-building function; however, it is
405 interesting to note that @code{list} is used more times in the source
406 code for Emacs than @code{cons}.
408 @defun cons object1 object2
409 This function is the fundamental function used to build new list
410 structure. It creates a new cons cell, making @var{object1} the
411 @sc{car}, and @var{object2} the @sc{cdr}. It then returns the new cons
412 cell. The arguments @var{object1} and @var{object2} may be any Lisp
413 objects, but most often @var{object2} is a list.
431 @code{cons} is often used to add a single element to the front of a
432 list. This is called @dfn{consing the element onto the list}. For
436 (setq list (cons newelt list))
439 Note that there is no conflict between the variable named @code{list}
440 used in this example and the function named @code{list} described below;
441 any symbol can serve both purposes.
444 @defun list &rest objects
445 This function creates a list with @var{objects} as its elements. The
446 resulting list is always @code{nil}-terminated. If no @var{objects}
447 are given, the empty list is returned.
452 @result{} (1 2 3 4 5)
455 (list 1 2 '(3 4 5) 'foo)
456 @result{} (1 2 (3 4 5) foo)
465 @defun make-list length object
466 This function creates a list of length @var{length}, in which all the
467 elements have the identical value @var{object}. Compare
468 @code{make-list} with @code{make-string} (@pxref{Creating Strings}).
473 @result{} (pigs pigs pigs)
482 @defun append &rest sequences
483 @cindex copying lists
484 This function returns a list containing all the elements of
485 @var{sequences}. The @var{sequences} may be lists, vectors,
486 bool-vectors, or strings, but the last one should usually be a list.
487 All arguments except the last one are copied, so none of the arguments
488 is altered. (See @code{nconc} in @ref{Rearrangement}, for a way to join
489 lists with no copying.)
491 More generally, the final argument to @code{append} may be any Lisp
492 object. The final argument is not copied or converted; it becomes the
493 @sc{cdr} of the last cons cell in the new list. If the final argument
494 is itself a list, then its elements become in effect elements of the
495 result list. If the final element is not a list, the result is a
496 ``dotted list'' since its final @sc{cdr} is not @code{nil} as required
499 The @code{append} function also allows integers as arguments. It
500 converts them to strings of digits, making up the decimal print
501 representation of the integer, and then uses the strings instead of the
502 original integers. @strong{Don't use this feature; we plan to eliminate
503 it. If you already use this feature, change your programs now!} The
504 proper way to convert an integer to a decimal number in this way is with
505 @code{format} (@pxref{Formatting Strings}) or @code{number-to-string}
506 (@pxref{String Conversion}).
509 Here is an example of using @code{append}:
513 (setq trees '(pine oak))
515 (setq more-trees (append '(maple birch) trees))
516 @result{} (maple birch pine oak)
523 @result{} (maple birch pine oak)
526 (eq trees (cdr (cdr more-trees)))
531 You can see how @code{append} works by looking at a box diagram. The
532 variable @code{trees} is set to the list @code{(pine oak)} and then the
533 variable @code{more-trees} is set to the list @code{(maple birch pine
534 oak)}. However, the variable @code{trees} continues to refer to the
541 | --- --- --- --- -> --- --- --- ---
542 --> | | |--> | | |--> | | |--> | | |--> nil
543 --- --- --- --- --- --- --- ---
546 --> maple -->birch --> pine --> oak
550 An empty sequence contributes nothing to the value returned by
551 @code{append}. As a consequence of this, a final @code{nil} argument
552 forces a copy of the previous argument:
560 (setq wood (append trees nil))
574 This once was the usual way to copy a list, before the function
575 @code{copy-sequence} was invented. @xref{Sequences Arrays Vectors}.
577 Here we show the use of vectors and strings as arguments to @code{append}:
581 (append [a b] "cd" nil)
582 @result{} (a b 99 100)
586 With the help of @code{apply} (@pxref{Calling Functions}), we can append
587 all the lists in a list of lists:
591 (apply 'append '((a b c) nil (x y z) nil))
592 @result{} (a b c x y z)
596 If no @var{sequences} are given, @code{nil} is returned:
605 Here are some examples where the final argument is not a list:
611 @result{} (x y . [z])
615 The second example shows that when the final argument is a sequence but
616 not a list, the sequence's elements do not become elements of the
617 resulting list. Instead, the sequence becomes the final @sc{cdr}, like
618 any other non-list final argument.
621 This function creates a new list whose elements are the elements of
622 @var{list}, but in reverse order. The original argument @var{list} is
639 @node Modifying Lists
640 @section Modifying Existing List Structure
641 @cindex destructive list operations
643 You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the
644 primitives @code{setcar} and @code{setcdr}. We call these ``destructive''
645 operations because they change existing list structure.
647 @cindex CL note---@code{rplaca} vrs @code{setcar}
651 @b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and
652 @code{rplacd} to alter list structure; they change structure the same
653 way as @code{setcar} and @code{setcdr}, but the Common Lisp functions
654 return the cons cell while @code{setcar} and @code{setcdr} return the
655 new @sc{car} or @sc{cdr}.
659 * Setcar:: Replacing an element in a list.
660 * Setcdr:: Replacing part of the list backbone.
661 This can be used to remove or add elements.
662 * Rearrangement:: Reordering the elements in a list; combining lists.
666 @subsection Altering List Elements with @code{setcar}
668 Changing the @sc{car} of a cons cell is done with @code{setcar}. When
669 used on a list, @code{setcar} replaces one element of a list with a
672 @defun setcar cons object
673 This function stores @var{object} as the new @sc{car} of @var{cons},
674 replacing its previous @sc{car}. In other words, it changes the
675 @sc{car} slot of @var{cons} to point to @var{object}. It returns the
676 value @var{object}. For example:
694 When a cons cell is part of the shared structure of several lists,
695 storing a new @sc{car} into the cons changes one element of each of
696 these lists. Here is an example:
700 ;; @r{Create two lists that are partly shared.}
703 (setq x2 (cons 'z (cdr x1)))
708 ;; @r{Replace the @sc{car} of a shared link.}
709 (setcar (cdr x1) 'foo)
711 x1 ; @r{Both lists are changed.}
718 ;; @r{Replace the @sc{car} of a link that is not shared.}
721 x1 ; @r{Only one list is changed.}
722 @result{} (baz foo c)
728 Here is a graphical depiction of the shared structure of the two lists
729 in the variables @code{x1} and @code{x2}, showing why replacing @code{b}
734 --- --- --- --- --- ---
735 x1---> | | |----> | | |--> | | |--> nil
736 --- --- --- --- --- ---
750 Here is an alternative form of box diagram, showing the same relationship:
755 -------------- -------------- --------------
756 | car | cdr | | car | cdr | | car | cdr |
757 | a | o------->| b | o------->| c | nil |
759 -------------- | -------------- --------------
771 @subsection Altering the CDR of a List
773 The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}:
775 @defun setcdr cons object
776 This function stores @var{object} as the new @sc{cdr} of @var{cons},
777 replacing its previous @sc{cdr}. In other words, it changes the
778 @sc{cdr} slot of @var{cons} to point to @var{object}. It returns the
782 Here is an example of replacing the @sc{cdr} of a list with a
783 different list. All but the first element of the list are removed in
784 favor of a different sequence of elements. The first element is
785 unchanged, because it resides in the @sc{car} of the list, and is not
786 reached via the @sc{cdr}.
803 You can delete elements from the middle of a list by altering the
804 @sc{cdr}s of the cons cells in the list. For example, here we delete
805 the second element, @code{b}, from the list @code{(a b c)}, by changing
806 the @sc{cdr} of the first cons cell:
812 (setcdr x1 (cdr (cdr x1)))
820 Here is the result in box notation:
826 -------------- | -------------- | --------------
827 | car | cdr | | | car | cdr | -->| car | cdr |
828 | a | o----- | b | o-------->| c | nil |
830 -------------- -------------- --------------
835 The second cons cell, which previously held the element @code{b}, still
836 exists and its @sc{car} is still @code{b}, but it no longer forms part
839 It is equally easy to insert a new element by changing @sc{cdr}s:
845 (setcdr x1 (cons 'd (cdr x1)))
852 Here is this result in box notation:
856 -------------- ------------- -------------
857 | car | cdr | | car | cdr | | car | cdr |
858 | a | o | -->| b | o------->| c | nil |
859 | | | | | | | | | | |
860 --------- | -- | ------------- -------------
873 @subsection Functions that Rearrange Lists
874 @cindex rearrangement of lists
875 @cindex modification of lists
877 Here are some functions that rearrange lists ``destructively'' by
878 modifying the @sc{cdr}s of their component cons cells. We call these
879 functions ``destructive'' because they chew up the original lists passed
880 to them as arguments, relinking their cons cells to form a new list that
881 is the returned value.
884 See @code{delq}, in @ref{Sets And Lists}, for another function
885 that modifies cons cells.
888 The function @code{delq} in the following section is another example
889 of destructive list manipulation.
892 @defun nconc &rest lists
893 @cindex concatenating lists
894 @cindex joining lists
895 This function returns a list containing all the elements of @var{lists}.
896 Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are
897 @emph{not} copied. Instead, the last @sc{cdr} of each of the
898 @var{lists} is changed to refer to the following list. The last of the
899 @var{lists} is not altered. For example:
908 @result{} (1 2 3 4 5)
912 @result{} (1 2 3 4 5)
916 Since the last argument of @code{nconc} is not itself modified, it is
917 reasonable to use a constant list, such as @code{'(4 5)}, as in the
918 above example. For the same reason, the last argument need not be a
928 @result{} (1 2 3 . z)
932 @result{} (1 2 3 . z)
936 However, the other arguments (all but the last) must be lists.
938 A common pitfall is to use a quoted constant list as a non-last
939 argument to @code{nconc}. If you do this, your program will change
940 each time you run it! Here is what happens:
944 (defun add-foo (x) ; @r{We want this function to add}
945 (nconc '(foo) x)) ; @r{@code{foo} to the front of its arg.}
949 (symbol-function 'add-foo)
950 @result{} (lambda (x) (nconc (quote (foo)) x))
954 (setq xx (add-foo '(1 2))) ; @r{It seems to work.}
958 (setq xy (add-foo '(3 4))) ; @r{What happened?}
959 @result{} (foo 1 2 3 4)
967 (symbol-function 'add-foo)
968 @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x)))
974 @cindex reversing a list
975 This function reverses the order of the elements of @var{list}.
976 Unlike @code{reverse}, @code{nreverse} alters its argument by reversing
977 the @sc{cdr}s in the cons cells forming the list. The cons cell that
978 used to be the last one in @var{list} becomes the first cons cell of the
995 ;; @r{The cons cell that was first is now last.}
1001 To avoid confusion, we usually store the result of @code{nreverse}
1002 back in the same variable which held the original list:
1005 (setq x (nreverse x))
1008 Here is the @code{nreverse} of our favorite example, @code{(a b c)},
1009 presented graphically:
1013 @r{Original list head:} @r{Reversed list:}
1014 ------------- ------------- ------------
1015 | car | cdr | | car | cdr | | car | cdr |
1016 | a | nil |<-- | b | o |<-- | c | o |
1017 | | | | | | | | | | | | |
1018 ------------- | --------- | - | -------- | -
1020 ------------- ------------
1025 @defun sort list predicate
1027 @cindex sorting lists
1028 This function sorts @var{list} stably, though destructively, and
1029 returns the sorted list. It compares elements using @var{predicate}. A
1030 stable sort is one in which elements with equal sort keys maintain their
1031 relative order before and after the sort. Stability is important when
1032 successive sorts are used to order elements according to different
1035 The argument @var{predicate} must be a function that accepts two
1036 arguments. It is called with two elements of @var{list}. To get an
1037 increasing order sort, the @var{predicate} should return @code{t} if the
1038 first element is ``less than'' the second, or @code{nil} if not.
1040 The comparison function @var{predicate} must give reliable results for
1041 any given pair of arguments, at least within a single call to
1042 @code{sort}. It must be @dfn{antisymmetric}; that is, if @var{a} is
1043 less than @var{b}, @var{b} must not be less than @var{a}. It must be
1044 @dfn{transitive}---that is, if @var{a} is less than @var{b}, and @var{b}
1045 is less than @var{c}, then @var{a} must be less than @var{c}. If you
1046 use a comparison function which does not meet these requirements, the
1047 result of @code{sort} is unpredictable.
1049 The destructive aspect of @code{sort} is that it rearranges the cons
1050 cells forming @var{list} by changing @sc{cdr}s. A nondestructive sort
1051 function would create new cons cells to store the elements in their
1052 sorted order. If you wish to make a sorted copy without destroying the
1053 original, copy it first with @code{copy-sequence} and then sort.
1055 Sorting does not change the @sc{car}s of the cons cells in @var{list};
1056 the cons cell that originally contained the element @code{a} in
1057 @var{list} still has @code{a} in its @sc{car} after sorting, but it now
1058 appears in a different position in the list due to the change of
1059 @sc{cdr}s. For example:
1063 (setq nums '(1 3 2 6 5 4 0))
1064 @result{} (1 3 2 6 5 4 0)
1068 @result{} (0 1 2 3 4 5 6)
1072 @result{} (1 2 3 4 5 6)
1077 @strong{Warning}: Note that the list in @code{nums} no longer contains
1078 0; this is the same cons cell that it was before, but it is no longer
1079 the first one in the list. Don't assume a variable that formerly held
1080 the argument now holds the entire sorted list! Instead, save the result
1081 of @code{sort} and use that. Most often we store the result back into
1082 the variable that held the original list:
1085 (setq nums (sort nums '<))
1088 @xref{Sorting}, for more functions that perform sorting.
1089 See @code{documentation} in @ref{Accessing Documentation}, for a
1090 useful example of @code{sort}.
1093 @node Sets And Lists
1094 @section Using Lists as Sets
1095 @cindex lists as sets
1098 A list can represent an unordered mathematical set---simply consider a
1099 value an element of a set if it appears in the list, and ignore the
1100 order of the list. To form the union of two sets, use @code{append} (as
1101 long as you don't mind having duplicate elements). Other useful
1102 functions for sets include @code{memq} and @code{delq}, and their
1103 @code{equal} versions, @code{member} and @code{delete}.
1105 @cindex CL note---lack @code{union}, @code{intersection}
1107 @b{Common Lisp note:} Common Lisp has functions @code{union} (which
1108 avoids duplicate elements) and @code{intersection} for set operations,
1109 but GNU Emacs Lisp does not have them. You can write them in Lisp if
1113 @defun memq object list
1114 @cindex membership in a list
1115 This function tests to see whether @var{object} is a member of
1116 @var{list}. If it is, @code{memq} returns a list starting with the
1117 first occurrence of @var{object}. Otherwise, it returns @code{nil}.
1118 The letter @samp{q} in @code{memq} says that it uses @code{eq} to
1119 compare @var{object} against the elements of the list. For example:
1123 (memq 'b '(a b c b a))
1127 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1133 @defun delq object list
1134 @cindex deletion of elements
1135 This function destructively removes all elements @code{eq} to
1136 @var{object} from @var{list}. The letter @samp{q} in @code{delq} says
1137 that it uses @code{eq} to compare @var{object} against the elements of
1138 the list, like @code{memq}.
1141 When @code{delq} deletes elements from the front of the list, it does so
1142 simply by advancing down the list and returning a sublist that starts
1143 after those elements:
1147 (delq 'a '(a b c)) @equiv{} (cdr '(a b c))
1151 When an element to be deleted appears in the middle of the list,
1152 removing it involves changing the @sc{cdr}s (@pxref{Setcdr}).
1156 (setq sample-list '(a b c (4)))
1157 @result{} (a b c (4))
1160 (delq 'a sample-list)
1165 @result{} (a b c (4))
1168 (delq 'c sample-list)
1177 Note that @code{(delq 'c sample-list)} modifies @code{sample-list} to
1178 splice out the third element, but @code{(delq 'a sample-list)} does not
1179 splice anything---it just returns a shorter list. Don't assume that a
1180 variable which formerly held the argument @var{list} now has fewer
1181 elements, or that it still holds the original list! Instead, save the
1182 result of @code{delq} and use that. Most often we store the result back
1183 into the variable that held the original list:
1186 (setq flowers (delq 'rose flowers))
1189 In the following example, the @code{(4)} that @code{delq} attempts to match
1190 and the @code{(4)} in the @code{sample-list} are not @code{eq}:
1194 (delq '(4) sample-list)
1199 The following two functions are like @code{memq} and @code{delq} but use
1200 @code{equal} rather than @code{eq} to compare elements. @xref{Equality
1203 @defun member object list
1204 The function @code{member} tests to see whether @var{object} is a member
1205 of @var{list}, comparing members with @var{object} using @code{equal}.
1206 If @var{object} is a member, @code{member} returns a list starting with
1207 its first occurrence in @var{list}. Otherwise, it returns @code{nil}.
1209 Compare this with @code{memq}:
1213 (member '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are @code{equal}.}
1217 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1221 ;; @r{Two strings with the same contents are @code{equal}.}
1222 (member "foo" '("foo" "bar"))
1223 @result{} ("foo" "bar")
1228 @defun delete object list
1229 This function destructively removes all elements @code{equal} to
1230 @var{object} from @var{list}. It is to @code{delq} as @code{member} is
1231 to @code{memq}: it uses @code{equal} to compare elements with
1232 @var{object}, like @code{member}; when it finds an element that matches,
1233 it removes the element just as @code{delq} would. For example:
1237 (delete '(2) '((2) (1) (2)))
1244 @b{Common Lisp note:} The functions @code{member} and @code{delete} in
1245 GNU Emacs Lisp are derived from Maclisp, not Common Lisp. The Common
1246 Lisp versions do not use @code{equal} to compare elements.
1249 See also the function @code{add-to-list}, in @ref{Setting Variables},
1250 for another way to add an element to a list stored in a variable.
1252 @node Association Lists
1253 @section Association Lists
1254 @cindex association list
1257 An @dfn{association list}, or @dfn{alist} for short, records a mapping
1258 from keys to values. It is a list of cons cells called
1259 @dfn{associations}: the @sc{car} of each cons cell is the @dfn{key}, and the
1260 @sc{cdr} is the @dfn{associated value}.@footnote{This usage of ``key''
1261 is not related to the term ``key sequence''; it means a value used to
1262 look up an item in a table. In this case, the table is the alist, and
1263 the alist associations are the items.}
1265 Here is an example of an alist. The key @code{pine} is associated with
1266 the value @code{cones}; the key @code{oak} is associated with
1267 @code{acorns}; and the key @code{maple} is associated with @code{seeds}.
1277 The associated values in an alist may be any Lisp objects; so may the
1278 keys. For example, in the following alist, the symbol @code{a} is
1279 associated with the number @code{1}, and the string @code{"b"} is
1280 associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of
1287 Sometimes it is better to design an alist to store the associated
1288 value in the @sc{car} of the @sc{cdr} of the element. Here is an
1292 '((rose red) (lily white) (buttercup yellow))
1296 Here we regard @code{red} as the value associated with @code{rose}. One
1297 advantage of this kind of alist is that you can store other related
1298 information---even a list of other items---in the @sc{cdr} of the
1299 @sc{cdr}. One disadvantage is that you cannot use @code{rassq} (see
1300 below) to find the element containing a given value. When neither of
1301 these considerations is important, the choice is a matter of taste, as
1302 long as you are consistent about it for any given alist.
1304 Note that the same alist shown above could be regarded as having the
1305 associated value in the @sc{cdr} of the element; the value associated
1306 with @code{rose} would be the list @code{(red)}.
1308 Association lists are often used to record information that you might
1309 otherwise keep on a stack, since new associations may be added easily to
1310 the front of the list. When searching an association list for an
1311 association with a given key, the first one found is returned, if there
1314 In Emacs Lisp, it is @emph{not} an error if an element of an
1315 association list is not a cons cell. The alist search functions simply
1316 ignore such elements. Many other versions of Lisp signal errors in such
1319 Note that property lists are similar to association lists in several
1320 respects. A property list behaves like an association list in which
1321 each key can occur only once. @xref{Property Lists}, for a comparison
1322 of property lists and association lists.
1324 @defun assoc key alist
1325 This function returns the first association for @var{key} in
1326 @var{alist}. It compares @var{key} against the alist elements using
1327 @code{equal} (@pxref{Equality Predicates}). It returns @code{nil} if no
1328 association in @var{alist} has a @sc{car} @code{equal} to @var{key}.
1332 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1333 @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1335 @result{} (oak . acorns)
1336 (cdr (assoc 'oak trees))
1338 (assoc 'birch trees)
1342 Here is another example, in which the keys and values are not symbols:
1345 (setq needles-per-cluster
1346 '((2 "Austrian Pine" "Red Pine")
1350 (cdr (assoc 3 needles-per-cluster))
1351 @result{} ("Pitch Pine")
1352 (cdr (assoc 2 needles-per-cluster))
1353 @result{} ("Austrian Pine" "Red Pine")
1357 The functions @code{assoc-ignore-representation} and
1358 @code{assoc-ignore-case} are much like @code{assoc} except using
1359 @code{compare-strings} to do the comparison. @xref{Text Comparison}.
1361 @defun rassoc value alist
1362 This function returns the first association with value @var{value} in
1363 @var{alist}. It returns @code{nil} if no association in @var{alist} has
1364 a @sc{cdr} @code{equal} to @var{value}.
1366 @code{rassoc} is like @code{assoc} except that it compares the @sc{cdr} of
1367 each @var{alist} association instead of the @sc{car}. You can think of
1368 this as ``reverse @code{assoc}'', finding the key for a given value.
1371 @defun assq key alist
1372 This function is like @code{assoc} in that it returns the first
1373 association for @var{key} in @var{alist}, but it makes the comparison
1374 using @code{eq} instead of @code{equal}. @code{assq} returns @code{nil}
1375 if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}.
1376 This function is used more often than @code{assoc}, since @code{eq} is
1377 faster than @code{equal} and most alists use symbols as keys.
1378 @xref{Equality Predicates}.
1381 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1382 @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1384 @result{} (pine . cones)
1387 On the other hand, @code{assq} is not usually useful in alists where the
1388 keys may not be symbols:
1392 '(("simple leaves" . oak)
1393 ("compound leaves" . horsechestnut)))
1395 (assq "simple leaves" leaves)
1397 (assoc "simple leaves" leaves)
1398 @result{} ("simple leaves" . oak)
1402 @defun rassq value alist
1403 This function returns the first association with value @var{value} in
1404 @var{alist}. It returns @code{nil} if no association in @var{alist} has
1405 a @sc{cdr} @code{eq} to @var{value}.
1407 @code{rassq} is like @code{assq} except that it compares the @sc{cdr} of
1408 each @var{alist} association instead of the @sc{car}. You can think of
1409 this as ``reverse @code{assq}'', finding the key for a given value.
1414 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1416 (rassq 'acorns trees)
1417 @result{} (oak . acorns)
1418 (rassq 'spores trees)
1422 Note that @code{rassq} cannot search for a value stored in the @sc{car}
1423 of the @sc{cdr} of an element:
1426 (setq colors '((rose red) (lily white) (buttercup yellow)))
1428 (rassq 'white colors)
1432 In this case, the @sc{cdr} of the association @code{(lily white)} is not
1433 the symbol @code{white}, but rather the list @code{(white)}. This
1434 becomes clearer if the association is written in dotted pair notation:
1437 (lily white) @equiv{} (lily . (white))
1441 @tindex assoc-default
1442 @defun assoc-default key alist test default
1443 This function searches @var{alist} for a match for @var{key}. For each
1444 element of @var{alist}, it compares the element (if it is an atom) or
1445 the element's @sc{car} (if it is a cons) against @var{key}, by calling
1446 @var{test} with two arguments: the element or its @sc{car}, and
1447 @var{key}. The arguments are passed in that order so that you can get
1448 useful results using @code{string-match} with an alist that contains
1449 regular expressions (@pxref{Regexp Search}). If @var{test} is omitted
1450 or @code{nil}, @code{equal} is used for comparison.
1452 If an alist element matches @var{key} by this criterion,
1453 then @code{assoc-default} returns a value based on this element.
1454 If the element is a cons, then the value is the element's @sc{cdr}.
1455 Otherwise, the return value is @var{default}.
1457 If no alist element matches @var{key}, @code{assoc-default} returns
1461 @defun copy-alist alist
1462 @cindex copying alists
1463 This function returns a two-level deep copy of @var{alist}: it creates a
1464 new copy of each association, so that you can alter the associations of
1465 the new alist without changing the old one.
1469 (setq needles-per-cluster
1470 '((2 . ("Austrian Pine" "Red Pine"))
1471 (3 . ("Pitch Pine"))
1473 (5 . ("White Pine"))))
1475 ((2 "Austrian Pine" "Red Pine")
1479 (setq copy (copy-alist needles-per-cluster))
1481 ((2 "Austrian Pine" "Red Pine")
1485 (eq needles-per-cluster copy)
1487 (equal needles-per-cluster copy)
1489 (eq (car needles-per-cluster) (car copy))
1491 (cdr (car (cdr needles-per-cluster)))
1492 @result{} ("Pitch Pine")
1494 (eq (cdr (car (cdr needles-per-cluster)))
1495 (cdr (car (cdr copy))))
1500 This example shows how @code{copy-alist} makes it possible to change
1501 the associations of one copy without affecting the other:
1505 (setcdr (assq 3 copy) '("Martian Vacuum Pine"))
1506 (cdr (assq 3 needles-per-cluster))
1507 @result{} ("Pitch Pine")