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
55 Since @code{nil} is the conventional value to put in the @sc{cdr} of
56 the last cons cell in the list, we call that case a @dfn{true list}.
58 In Lisp, we consider the symbol @code{nil} a list as well as a
59 symbol; it is the list with no elements. For convenience, the symbol
60 @code{nil} is considered to have @code{nil} as its @sc{cdr} (and also
61 as its @sc{car}). Therefore, the @sc{cdr} of a true list is always a
66 If the @sc{cdr} of a list's last cons cell is some other value,
67 neither @code{nil} nor another cons cell, we call the structure a
68 @dfn{dotted list}, since its printed representation would use
69 @samp{.}. There is one other possibility: some cons cell's @sc{cdr}
70 could point to one of the previous cons cells in the list. We call
71 that structure a @dfn{circular list}.
73 For some purposes, it does not matter whether a list is true,
74 circular or dotted. If the program doesn't look far enough down the
75 list to see the @sc{cdr} of the final cons cell, it won't care.
76 However, some functions that operate on lists demand true lists and
77 signal errors if given a dotted list. Most functions that try to find
78 the end of a list enter infinite loops if given a circular list.
80 @cindex list structure
81 Because most cons cells are used as part of lists, the phrase
82 @dfn{list structure} has come to mean any structure made out of cons
85 The @sc{cdr} of any nonempty list @var{l} is a list containing all the
86 elements of @var{l} except the first.
89 @comment node-name, next, previous, up
90 @section Lists as Linked Pairs of Boxes
91 @cindex box representation for lists
92 @cindex lists represented as boxes
93 @cindex cons cell as box
95 A cons cell can be illustrated as a pair of boxes. The first box
96 represents the @sc{car} and the second box represents the @sc{cdr}.
97 Here is an illustration of the two-element list, @code{(tulip lily)},
98 made from two cons cells:
102 --------------- ---------------
103 | car | cdr | | car | cdr |
104 | tulip | o---------->| lily | nil |
106 --------------- ---------------
110 Each pair of boxes represents a cons cell. Each box ``refers to'',
111 ``points to'' or ``holds'' a Lisp object. (These terms are
112 synonymous.) The first box, which describes the @sc{car} of the first
113 cons cell, contains the symbol @code{tulip}. The arrow from the
114 @sc{cdr} box of the first cons cell to the second cons cell indicates
115 that the @sc{cdr} of the first cons cell is the second cons cell.
117 The same list can be illustrated in a different sort of box notation
123 | | |--> | | |--> nil
131 Here is a more complex illustration, showing the three-element list,
132 @code{((pine needles) oak maple)}, the first element of which is a
137 --- --- --- --- --- ---
138 | | |--> | | |--> | | |--> nil
139 --- --- --- --- --- ---
145 --> | | |--> | | |--> nil
153 The same list represented in the first box notation looks like this:
157 -------------- -------------- --------------
158 | car | cdr | | car | cdr | | car | cdr |
159 | o | o------->| oak | o------->| maple | nil |
161 -- | --------- -------------- --------------
164 | -------------- ----------------
165 | | car | cdr | | car | cdr |
166 ------>| pine | o------->| needles | nil |
168 -------------- ----------------
172 @xref{Cons Cell Type}, for the read and print syntax of cons cells and
173 lists, and for more ``box and arrow'' illustrations of lists.
175 @node List-related Predicates
176 @section Predicates on Lists
178 The following predicates test whether a Lisp object is an atom, is a
179 cons cell or is a list, or whether it is the distinguished object
180 @code{nil}. (Many of these predicates can be defined in terms of the
181 others, but they are used so often that it is worth having all of them.)
184 This function returns @code{t} if @var{object} is a cons cell, @code{nil}
185 otherwise. @code{nil} is not a cons cell, although it @emph{is} a list.
190 This function returns @code{t} if @var{object} is an atom, @code{nil}
191 otherwise. All objects except cons cells are atoms. The symbol
192 @code{nil} is an atom and is also a list; it is the only Lisp object
196 (atom @var{object}) @equiv{} (not (consp @var{object}))
201 This function returns @code{t} if @var{object} is a cons cell or
202 @code{nil}. Otherwise, it returns @code{nil}.
217 This function is the opposite of @code{listp}: it returns @code{t} if
218 @var{object} is not a list. Otherwise, it returns @code{nil}.
221 (listp @var{object}) @equiv{} (not (nlistp @var{object}))
226 This function returns @code{t} if @var{object} is @code{nil}, and
227 returns @code{nil} otherwise. This function is identical to @code{not},
228 but as a matter of clarity we use @code{null} when @var{object} is
229 considered a list and @code{not} when it is considered a truth value
230 (see @code{not} in @ref{Combining Conditions}).
247 @section Accessing Elements of Lists
248 @cindex list elements
251 This function returns the value referred to by the first slot of the
252 cons cell @var{cons-cell}. Expressed another way, this function
253 returns the @sc{car} of @var{cons-cell}.
255 As a special case, if @var{cons-cell} is @code{nil}, then @code{car}
256 is defined to return @code{nil}; therefore, any list is a valid argument
257 for @code{car}. An error is signaled if the argument is not a cons cell
273 This function returns the value referred to by the second slot of
274 the cons cell @var{cons-cell}. Expressed another way, this function
275 returns the @sc{cdr} of @var{cons-cell}.
277 As a special case, if @var{cons-cell} is @code{nil}, then @code{cdr}
278 is defined to return @code{nil}; therefore, any list is a valid argument
279 for @code{cdr}. An error is signaled if the argument is not a cons cell
294 @defun car-safe object
295 This function lets you take the @sc{car} of a cons cell while avoiding
296 errors for other data types. It returns the @sc{car} of @var{object} if
297 @var{object} is a cons cell, @code{nil} otherwise. This is in contrast
298 to @code{car}, which signals an error if @var{object} is not a list.
302 (car-safe @var{object})
304 (let ((x @var{object}))
312 @defun cdr-safe object
313 This function lets you take the @sc{cdr} of a cons cell while
314 avoiding errors for other data types. It returns the @sc{cdr} of
315 @var{object} if @var{object} is a cons cell, @code{nil} otherwise.
316 This is in contrast to @code{cdr}, which signals an error if
317 @var{object} is not a list.
321 (cdr-safe @var{object})
323 (let ((x @var{object}))
333 This macro is a way of examining the @sc{car} of a list,
334 and taking it off the list, all at once. It is new in Emacs 21.
336 It operates on the list which is stored in the symbol @var{listname}.
337 It removes this element from the list by setting @var{listname}
338 to the @sc{cdr} of its old value---but it also returns the @sc{car}
339 of that list, which is the element being removed.
351 @anchor{Definition of nth}
353 This function returns the @var{n}th element of @var{list}. Elements
354 are numbered starting with zero, so the @sc{car} of @var{list} is
355 element number zero. If the length of @var{list} is @var{n} or less,
356 the value is @code{nil}.
358 If @var{n} is negative, @code{nth} returns the first element of
374 (nth n x) @equiv{} (car (nthcdr n x))
378 The function @code{elt} is similar, but applies to any kind of sequence.
379 For historical reasons, it takes its arguments in the opposite order.
380 @xref{Sequence Functions}.
384 This function returns the @var{n}th @sc{cdr} of @var{list}. In other
385 words, it skips past the first @var{n} links of @var{list} and returns
388 If @var{n} is zero or negative, @code{nthcdr} returns all of
389 @var{list}. If the length of @var{list} is @var{n} or less,
390 @code{nthcdr} returns @code{nil}.
394 (nthcdr 1 '(1 2 3 4))
398 (nthcdr 10 '(1 2 3 4))
402 (nthcdr -3 '(1 2 3 4))
408 @defun last list &optional n
409 This function returns the last link of @var{list}. The @code{car} of
410 this link is the list's last element. If @var{list} is null,
411 @code{nil} is returned. If @var{n} is non-@code{nil}, the
412 @var{n}th-to-last link is returned instead, or the whole of @var{list}
413 if @var{n} is bigger than @var{list}'s length.
416 @anchor{Definition of safe-length}
417 @defun safe-length list
418 This function returns the length of @var{list}, with no risk of either
419 an error or an infinite loop. It generally returns the number of
420 distinct cons cells in the list. However, for circular lists,
421 the value is just an upper bound; it is often too large.
423 If @var{list} is not @code{nil} or a cons cell, @code{safe-length}
427 The most common way to compute the length of a list, when you are not
428 worried that it may be circular, is with @code{length}. @xref{Sequence
431 @defun caar cons-cell
432 This is the same as @code{(car (car @var{cons-cell}))}.
435 @defun cadr cons-cell
436 This is the same as @code{(car (cdr @var{cons-cell}))}
437 or @code{(nth 1 @var{cons-cell})}.
440 @defun cdar cons-cell
441 This is the same as @code{(cdr (car @var{cons-cell}))}.
444 @defun cddr cons-cell
445 This is the same as @code{(cdr (cdr @var{cons-cell}))}
446 or @code{(nthcdr 2 @var{cons-cell})}.
449 @defun butlast x &optional n
450 This function returns the list @var{x} with the last element,
451 or the last @var{n} elements, removed. If @var{n} is greater
452 than zero it makes a copy of the list so as not to damage the
453 original list. In general, @code{(append (butlast @var{x} @var{n})
454 (last @var{x} @var{n}))} will return a list equal to @var{x}.
457 @defun nbutlast x &optional n
458 This is a version of @code{butlast} that works by destructively
459 modifying the @code{cdr} of the appropriate element, rather than
460 making a copy of the list.
464 @comment node-name, next, previous, up
465 @section Building Cons Cells and Lists
467 @cindex building lists
469 Many functions build lists, as lists reside at the very heart of Lisp.
470 @code{cons} is the fundamental list-building function; however, it is
471 interesting to note that @code{list} is used more times in the source
472 code for Emacs than @code{cons}.
474 @defun cons object1 object2
475 This function is the most basic function for building new list
476 structure. It creates a new cons cell, making @var{object1} the
477 @sc{car}, and @var{object2} the @sc{cdr}. It then returns the new
478 cons cell. The arguments @var{object1} and @var{object2} may be any
479 Lisp objects, but most often @var{object2} is a list.
497 @code{cons} is often used to add a single element to the front of a
498 list. This is called @dfn{consing the element onto the list}.
499 @footnote{There is no strictly equivalent way to add an element to
500 the end of a list. You can use @code{(append @var{listname} (list
501 @var{newelt}))}, which creates a whole new list by copying @var{listname}
502 and adding @var{newelt} to its end. Or you can use @code{(nconc
503 @var{listname} (list @var{newelt}))}, which modifies @var{listname}
504 by following all the @sc{cdr}s and then replacing the terminating
505 @code{nil}. Compare this to adding an element to the beginning of a
506 list with @code{cons}, which neither copies nor modifies the list.}
510 (setq list (cons newelt list))
513 Note that there is no conflict between the variable named @code{list}
514 used in this example and the function named @code{list} described below;
515 any symbol can serve both purposes.
519 @defmac push newelt listname
520 This macro provides an alternative way to write
521 @code{(setq @var{listname} (cons @var{newelt} @var{listname}))}.
522 It is new in Emacs 21.
534 @defun list &rest objects
535 This function creates a list with @var{objects} as its elements. The
536 resulting list is always @code{nil}-terminated. If no @var{objects}
537 are given, the empty list is returned.
542 @result{} (1 2 3 4 5)
545 (list 1 2 '(3 4 5) 'foo)
546 @result{} (1 2 (3 4 5) foo)
555 @defun make-list length object
556 This function creates a list of @var{length} elements, in which each
557 element is @var{object}. Compare @code{make-list} with
558 @code{make-string} (@pxref{Creating Strings}).
563 @result{} (pigs pigs pigs)
570 (setq l (make-list 3 '(a b))
571 @result{} ((a b) (a b) (a b))
572 (eq (car l) (cadr l))
578 @defun append &rest sequences
579 @cindex copying lists
580 This function returns a list containing all the elements of
581 @var{sequences}. The @var{sequences} may be lists, vectors,
582 bool-vectors, or strings, but the last one should usually be a list.
583 All arguments except the last one are copied, so none of the arguments
584 is altered. (See @code{nconc} in @ref{Rearrangement}, for a way to join
585 lists with no copying.)
587 More generally, the final argument to @code{append} may be any Lisp
588 object. The final argument is not copied or converted; it becomes the
589 @sc{cdr} of the last cons cell in the new list. If the final argument
590 is itself a list, then its elements become in effect elements of the
591 result list. If the final element is not a list, the result is a
592 dotted list since its final @sc{cdr} is not @code{nil} as required
595 In Emacs 20 and before, the @code{append} function also allowed
596 integers as (non last) arguments. It converted them to strings of
597 digits, making up the decimal print representation of the integer, and
598 then used the strings instead of the original integers. This obsolete
599 usage no longer works. The proper way to convert an integer to a
600 decimal number in this way is with @code{format} (@pxref{Formatting
601 Strings}) or @code{number-to-string} (@pxref{String Conversion}).
604 Here is an example of using @code{append}:
608 (setq trees '(pine oak))
610 (setq more-trees (append '(maple birch) trees))
611 @result{} (maple birch pine oak)
618 @result{} (maple birch pine oak)
621 (eq trees (cdr (cdr more-trees)))
626 You can see how @code{append} works by looking at a box diagram. The
627 variable @code{trees} is set to the list @code{(pine oak)} and then the
628 variable @code{more-trees} is set to the list @code{(maple birch pine
629 oak)}. However, the variable @code{trees} continues to refer to the
636 | --- --- --- --- -> --- --- --- ---
637 --> | | |--> | | |--> | | |--> | | |--> nil
638 --- --- --- --- --- --- --- ---
641 --> maple -->birch --> pine --> oak
645 An empty sequence contributes nothing to the value returned by
646 @code{append}. As a consequence of this, a final @code{nil} argument
647 forces a copy of the previous argument:
655 (setq wood (append trees nil))
669 This once was the usual way to copy a list, before the function
670 @code{copy-sequence} was invented. @xref{Sequences Arrays Vectors}.
672 Here we show the use of vectors and strings as arguments to @code{append}:
676 (append [a b] "cd" nil)
677 @result{} (a b 99 100)
681 With the help of @code{apply} (@pxref{Calling Functions}), we can append
682 all the lists in a list of lists:
686 (apply 'append '((a b c) nil (x y z) nil))
687 @result{} (a b c x y z)
691 If no @var{sequences} are given, @code{nil} is returned:
700 Here are some examples where the final argument is not a list:
706 @result{} (x y . [z])
710 The second example shows that when the final argument is a sequence but
711 not a list, the sequence's elements do not become elements of the
712 resulting list. Instead, the sequence becomes the final @sc{cdr}, like
713 any other non-list final argument.
716 This function creates a new list whose elements are the elements of
717 @var{list}, but in reverse order. The original argument @var{list} is
734 @defun copy-tree tree &optional vecp
735 This function returns a copy of the tree @code{tree}. If @var{tree} is a
736 cons cell, this makes a new cons cell with the same @sc{car} and
737 @sc{cdr}, then recursively copies the @sc{car} and @sc{cdr} in the
740 Normally, when @var{tree} is anything other than a cons cell,
741 @code{copy-tree} simply returns @var{tree}. However, if @var{vecp} is
742 non-@code{nil}, it copies vectors too (and operates recursively on
746 @defun number-sequence from &optional to separation
747 This returns a list of numbers starting with @var{from} and
748 incrementing by @var{separation}, and ending at or just before
749 @var{to}. @var{separation} can be positive or negative and defaults
750 to 1. If @var{to} is @code{nil} or numerically equal to @var{from},
751 the one element list @code{(from)} is returned. If @var{separation}
752 is 0 and @var{to} is neither @code{nil} nor numerically equal to
753 @var{from}, an error is signaled.
755 All arguments can be integers or floating point numbers. However,
756 floating point arguments can be tricky, because floating point
757 arithmetic is inexact. For instance, depending on the machine, it may
758 quite well happen that @code{(number-sequence 0.4 0.6 0.2)} returns
759 the one element list @code{(0.4)}, whereas
760 @code{(number-sequence 0.4 0.8 0.2)} returns a list with three
761 elements. The @var{n}th element of the list is computed by the exact
762 formula @code{(+ @var{from} (* @var{n} @var{separation}))}. Thus, if
763 one wants to make sure that @var{to} is included in the list, one can
764 pass an expression of this exact type for @var{to}. Alternatively,
765 one can replace @var{to} with a slightly larger value (or a slightly
766 more negative value if @var{separation} is negative).
771 (number-sequence 4 9)
772 @result{} (4 5 6 7 8 9)
773 (number-sequence 9 4 -1)
774 @result{} (9 8 7 6 5 4)
775 (number-sequence 9 4 -2)
779 (number-sequence 8 5)
781 (number-sequence 5 8 -1)
783 (number-sequence 1.5 6 2)
784 @result{} (1.5 3.5 5.5)
788 @node Modifying Lists
789 @section Modifying Existing List Structure
790 @cindex destructive list operations
792 You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the
793 primitives @code{setcar} and @code{setcdr}. We call these ``destructive''
794 operations because they change existing list structure.
796 @cindex CL note---@code{rplaca} vrs @code{setcar}
800 @b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and
801 @code{rplacd} to alter list structure; they change structure the same
802 way as @code{setcar} and @code{setcdr}, but the Common Lisp functions
803 return the cons cell while @code{setcar} and @code{setcdr} return the
804 new @sc{car} or @sc{cdr}.
808 * Setcar:: Replacing an element in a list.
809 * Setcdr:: Replacing part of the list backbone.
810 This can be used to remove or add elements.
811 * Rearrangement:: Reordering the elements in a list; combining lists.
815 @subsection Altering List Elements with @code{setcar}
817 Changing the @sc{car} of a cons cell is done with @code{setcar}. When
818 used on a list, @code{setcar} replaces one element of a list with a
821 @defun setcar cons object
822 This function stores @var{object} as the new @sc{car} of @var{cons},
823 replacing its previous @sc{car}. In other words, it changes the
824 @sc{car} slot of @var{cons} to refer to @var{object}. It returns the
825 value @var{object}. For example:
843 When a cons cell is part of the shared structure of several lists,
844 storing a new @sc{car} into the cons changes one element of each of
845 these lists. Here is an example:
849 ;; @r{Create two lists that are partly shared.}
852 (setq x2 (cons 'z (cdr x1)))
857 ;; @r{Replace the @sc{car} of a shared link.}
858 (setcar (cdr x1) 'foo)
860 x1 ; @r{Both lists are changed.}
867 ;; @r{Replace the @sc{car} of a link that is not shared.}
870 x1 ; @r{Only one list is changed.}
871 @result{} (baz foo c)
877 Here is a graphical depiction of the shared structure of the two lists
878 in the variables @code{x1} and @code{x2}, showing why replacing @code{b}
883 --- --- --- --- --- ---
884 x1---> | | |----> | | |--> | | |--> nil
885 --- --- --- --- --- ---
899 Here is an alternative form of box diagram, showing the same relationship:
904 -------------- -------------- --------------
905 | car | cdr | | car | cdr | | car | cdr |
906 | a | o------->| b | o------->| c | nil |
908 -------------- | -------------- --------------
920 @subsection Altering the CDR of a List
922 The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}:
924 @defun setcdr cons object
925 This function stores @var{object} as the new @sc{cdr} of @var{cons},
926 replacing its previous @sc{cdr}. In other words, it changes the
927 @sc{cdr} slot of @var{cons} to refer to @var{object}. It returns the
931 Here is an example of replacing the @sc{cdr} of a list with a
932 different list. All but the first element of the list are removed in
933 favor of a different sequence of elements. The first element is
934 unchanged, because it resides in the @sc{car} of the list, and is not
935 reached via the @sc{cdr}.
952 You can delete elements from the middle of a list by altering the
953 @sc{cdr}s of the cons cells in the list. For example, here we delete
954 the second element, @code{b}, from the list @code{(a b c)}, by changing
955 the @sc{cdr} of the first cons cell:
961 (setcdr x1 (cdr (cdr x1)))
969 Here is the result in box notation:
975 -------------- | -------------- | --------------
976 | car | cdr | | | car | cdr | -->| car | cdr |
977 | a | o----- | b | o-------->| c | nil |
979 -------------- -------------- --------------
984 The second cons cell, which previously held the element @code{b}, still
985 exists and its @sc{car} is still @code{b}, but it no longer forms part
988 It is equally easy to insert a new element by changing @sc{cdr}s:
994 (setcdr x1 (cons 'd (cdr x1)))
1001 Here is this result in box notation:
1005 -------------- ------------- -------------
1006 | car | cdr | | car | cdr | | car | cdr |
1007 | a | o | -->| b | o------->| c | nil |
1008 | | | | | | | | | | |
1009 --------- | -- | ------------- -------------
1022 @subsection Functions that Rearrange Lists
1023 @cindex rearrangement of lists
1024 @cindex modification of lists
1026 Here are some functions that rearrange lists ``destructively'' by
1027 modifying the @sc{cdr}s of their component cons cells. We call these
1028 functions ``destructive'' because they chew up the original lists passed
1029 to them as arguments, relinking their cons cells to form a new list that
1030 is the returned value.
1033 See @code{delq}, in @ref{Sets And Lists}, for another function
1034 that modifies cons cells.
1037 The function @code{delq} in the following section is another example
1038 of destructive list manipulation.
1041 @defun nconc &rest lists
1042 @cindex concatenating lists
1043 @cindex joining lists
1044 This function returns a list containing all the elements of @var{lists}.
1045 Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are
1046 @emph{not} copied. Instead, the last @sc{cdr} of each of the
1047 @var{lists} is changed to refer to the following list. The last of the
1048 @var{lists} is not altered. For example:
1057 @result{} (1 2 3 4 5)
1061 @result{} (1 2 3 4 5)
1065 Since the last argument of @code{nconc} is not itself modified, it is
1066 reasonable to use a constant list, such as @code{'(4 5)}, as in the
1067 above example. For the same reason, the last argument need not be a
1077 @result{} (1 2 3 . z)
1081 @result{} (1 2 3 . z)
1085 However, the other arguments (all but the last) must be lists.
1087 A common pitfall is to use a quoted constant list as a non-last
1088 argument to @code{nconc}. If you do this, your program will change
1089 each time you run it! Here is what happens:
1093 (defun add-foo (x) ; @r{We want this function to add}
1094 (nconc '(foo) x)) ; @r{@code{foo} to the front of its arg.}
1098 (symbol-function 'add-foo)
1099 @result{} (lambda (x) (nconc (quote (foo)) x))
1103 (setq xx (add-foo '(1 2))) ; @r{It seems to work.}
1107 (setq xy (add-foo '(3 4))) ; @r{What happened?}
1108 @result{} (foo 1 2 3 4)
1116 (symbol-function 'add-foo)
1117 @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x)))
1122 @defun nreverse list
1123 @cindex reversing a list
1124 This function reverses the order of the elements of @var{list}.
1125 Unlike @code{reverse}, @code{nreverse} alters its argument by reversing
1126 the @sc{cdr}s in the cons cells forming the list. The cons cell that
1127 used to be the last one in @var{list} becomes the first cons cell of the
1144 ;; @r{The cons cell that was first is now last.}
1150 To avoid confusion, we usually store the result of @code{nreverse}
1151 back in the same variable which held the original list:
1154 (setq x (nreverse x))
1157 Here is the @code{nreverse} of our favorite example, @code{(a b c)},
1158 presented graphically:
1162 @r{Original list head:} @r{Reversed list:}
1163 ------------- ------------- ------------
1164 | car | cdr | | car | cdr | | car | cdr |
1165 | a | nil |<-- | b | o |<-- | c | o |
1166 | | | | | | | | | | | | |
1167 ------------- | --------- | - | -------- | -
1169 ------------- ------------
1174 @defun sort list predicate
1176 @cindex sorting lists
1177 This function sorts @var{list} stably, though destructively, and
1178 returns the sorted list. It compares elements using @var{predicate}. A
1179 stable sort is one in which elements with equal sort keys maintain their
1180 relative order before and after the sort. Stability is important when
1181 successive sorts are used to order elements according to different
1184 The argument @var{predicate} must be a function that accepts two
1185 arguments. It is called with two elements of @var{list}. To get an
1186 increasing order sort, the @var{predicate} should return @code{t} if the
1187 first element is ``less than'' the second, or @code{nil} if not.
1189 The comparison function @var{predicate} must give reliable results for
1190 any given pair of arguments, at least within a single call to
1191 @code{sort}. It must be @dfn{antisymmetric}; that is, if @var{a} is
1192 less than @var{b}, @var{b} must not be less than @var{a}. It must be
1193 @dfn{transitive}---that is, if @var{a} is less than @var{b}, and @var{b}
1194 is less than @var{c}, then @var{a} must be less than @var{c}. If you
1195 use a comparison function which does not meet these requirements, the
1196 result of @code{sort} is unpredictable.
1198 The destructive aspect of @code{sort} is that it rearranges the cons
1199 cells forming @var{list} by changing @sc{cdr}s. A nondestructive sort
1200 function would create new cons cells to store the elements in their
1201 sorted order. If you wish to make a sorted copy without destroying the
1202 original, copy it first with @code{copy-sequence} and then sort.
1204 Sorting does not change the @sc{car}s of the cons cells in @var{list};
1205 the cons cell that originally contained the element @code{a} in
1206 @var{list} still has @code{a} in its @sc{car} after sorting, but it now
1207 appears in a different position in the list due to the change of
1208 @sc{cdr}s. For example:
1212 (setq nums '(1 3 2 6 5 4 0))
1213 @result{} (1 3 2 6 5 4 0)
1217 @result{} (0 1 2 3 4 5 6)
1221 @result{} (1 2 3 4 5 6)
1226 @strong{Warning}: Note that the list in @code{nums} no longer contains
1227 0; this is the same cons cell that it was before, but it is no longer
1228 the first one in the list. Don't assume a variable that formerly held
1229 the argument now holds the entire sorted list! Instead, save the result
1230 of @code{sort} and use that. Most often we store the result back into
1231 the variable that held the original list:
1234 (setq nums (sort nums '<))
1237 @xref{Sorting}, for more functions that perform sorting.
1238 See @code{documentation} in @ref{Accessing Documentation}, for a
1239 useful example of @code{sort}.
1242 @node Sets And Lists
1243 @section Using Lists as Sets
1244 @cindex lists as sets
1247 A list can represent an unordered mathematical set---simply consider a
1248 value an element of a set if it appears in the list, and ignore the
1249 order of the list. To form the union of two sets, use @code{append} (as
1250 long as you don't mind having duplicate elements). You can remove
1251 @code{equal} duplicates using @code{delete-dups}. Other useful
1252 functions for sets include @code{memq} and @code{delq}, and their
1253 @code{equal} versions, @code{member} and @code{delete}.
1255 @cindex CL note---lack @code{union}, @code{intersection}
1257 @b{Common Lisp note:} Common Lisp has functions @code{union} (which
1258 avoids duplicate elements) and @code{intersection} for set operations,
1259 but GNU Emacs Lisp does not have them. You can write them in Lisp if
1263 @defun memq object list
1264 @cindex membership in a list
1265 This function tests to see whether @var{object} is a member of
1266 @var{list}. If it is, @code{memq} returns a list starting with the
1267 first occurrence of @var{object}. Otherwise, it returns @code{nil}.
1268 The letter @samp{q} in @code{memq} says that it uses @code{eq} to
1269 compare @var{object} against the elements of the list. For example:
1273 (memq 'b '(a b c b a))
1277 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1283 @defun delq object list
1284 @cindex deletion of elements
1285 This function destructively removes all elements @code{eq} to
1286 @var{object} from @var{list}. The letter @samp{q} in @code{delq} says
1287 that it uses @code{eq} to compare @var{object} against the elements of
1288 the list, like @code{memq} and @code{remq}.
1291 When @code{delq} deletes elements from the front of the list, it does so
1292 simply by advancing down the list and returning a sublist that starts
1293 after those elements:
1297 (delq 'a '(a b c)) @equiv{} (cdr '(a b c))
1301 When an element to be deleted appears in the middle of the list,
1302 removing it involves changing the @sc{cdr}s (@pxref{Setcdr}).
1306 (setq sample-list '(a b c (4)))
1307 @result{} (a b c (4))
1310 (delq 'a sample-list)
1315 @result{} (a b c (4))
1318 (delq 'c sample-list)
1327 Note that @code{(delq 'c sample-list)} modifies @code{sample-list} to
1328 splice out the third element, but @code{(delq 'a sample-list)} does not
1329 splice anything---it just returns a shorter list. Don't assume that a
1330 variable which formerly held the argument @var{list} now has fewer
1331 elements, or that it still holds the original list! Instead, save the
1332 result of @code{delq} and use that. Most often we store the result back
1333 into the variable that held the original list:
1336 (setq flowers (delq 'rose flowers))
1339 In the following example, the @code{(4)} that @code{delq} attempts to match
1340 and the @code{(4)} in the @code{sample-list} are not @code{eq}:
1344 (delq '(4) sample-list)
1349 @defun remq object list
1350 This function returns a copy of @var{list}, with all elements removed
1351 which are @code{eq} to @var{object}. The letter @samp{q} in @code{remq}
1352 says that it uses @code{eq} to compare @var{object} against the elements
1357 (setq sample-list '(a b c a b c))
1358 @result{} (a b c a b c)
1361 (remq 'a sample-list)
1366 @result{} (a b c a b c)
1370 The function @code{delq} offers a way to perform this operation
1371 destructively. See @ref{Sets And Lists}.
1374 The following three functions are like @code{memq}, @code{delq} and
1375 @code{remq}, but use @code{equal} rather than @code{eq} to compare
1376 elements. @xref{Equality Predicates}.
1378 @defun member object list
1379 The function @code{member} tests to see whether @var{object} is a member
1380 of @var{list}, comparing members with @var{object} using @code{equal}.
1381 If @var{object} is a member, @code{member} returns a list starting with
1382 its first occurrence in @var{list}. Otherwise, it returns @code{nil}.
1384 Compare this with @code{memq}:
1388 (member '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are @code{equal}.}
1392 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1396 ;; @r{Two strings with the same contents are @code{equal}.}
1397 (member "foo" '("foo" "bar"))
1398 @result{} ("foo" "bar")
1403 @defun delete object sequence
1404 If @code{sequence} is a list, this function destructively removes all
1405 elements @code{equal} to @var{object} from @var{sequence}. For lists,
1406 @code{delete} is to @code{delq} as @code{member} is to @code{memq}: it
1407 uses @code{equal} to compare elements with @var{object}, like
1408 @code{member}; when it finds an element that matches, it removes the
1409 element just as @code{delq} would.
1411 If @code{sequence} is a vector or string, @code{delete} returns a copy
1412 of @code{sequence} with all elements @code{equal} to @code{object}
1419 (delete '(2) '((2) (1) (2)))
1423 (delete '(2) [(2) (1) (2)])
1429 @defun remove object sequence
1430 This function is the non-destructive counterpart of @code{delete}. If
1431 returns a copy of @code{sequence}, a list, vector, or string, with
1432 elements @code{equal} to @code{object} removed. For example:
1436 (remove '(2) '((2) (1) (2)))
1440 (remove '(2) [(2) (1) (2)])
1447 @b{Common Lisp note:} The functions @code{member}, @code{delete} and
1448 @code{remove} in GNU Emacs Lisp are derived from Maclisp, not Common
1449 Lisp. The Common Lisp versions do not use @code{equal} to compare
1453 @defun member-ignore-case object list
1454 This function is like @code{member}, except that @var{object} should
1455 be a string and that it ignores differences in letter-case and text
1456 representation: upper-case and lower-case letters are treated as
1457 equal, and unibyte strings are converted to multibyte prior to
1461 @defun delete-dups list
1462 This function destructively removes all @code{equal} duplicates from
1463 @var{list}, stores the result in @var{list} and returns it. Of
1464 several @code{equal} occurrences of an element in @var{list},
1465 @code{delete-dups} keeps the first one.
1468 See also the function @code{add-to-list}, in @ref{Setting Variables},
1469 for another way to add an element to a list stored in a variable.
1471 @node Association Lists
1472 @section Association Lists
1473 @cindex association list
1476 An @dfn{association list}, or @dfn{alist} for short, records a mapping
1477 from keys to values. It is a list of cons cells called
1478 @dfn{associations}: the @sc{car} of each cons cell is the @dfn{key}, and the
1479 @sc{cdr} is the @dfn{associated value}.@footnote{This usage of ``key''
1480 is not related to the term ``key sequence''; it means a value used to
1481 look up an item in a table. In this case, the table is the alist, and
1482 the alist associations are the items.}
1484 Here is an example of an alist. The key @code{pine} is associated with
1485 the value @code{cones}; the key @code{oak} is associated with
1486 @code{acorns}; and the key @code{maple} is associated with @code{seeds}.
1496 The associated values in an alist may be any Lisp objects; so may the
1497 keys. For example, in the following alist, the symbol @code{a} is
1498 associated with the number @code{1}, and the string @code{"b"} is
1499 associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of
1506 Sometimes it is better to design an alist to store the associated
1507 value in the @sc{car} of the @sc{cdr} of the element. Here is an
1508 example of such an alist:
1511 ((rose red) (lily white) (buttercup yellow))
1515 Here we regard @code{red} as the value associated with @code{rose}. One
1516 advantage of this kind of alist is that you can store other related
1517 information---even a list of other items---in the @sc{cdr} of the
1518 @sc{cdr}. One disadvantage is that you cannot use @code{rassq} (see
1519 below) to find the element containing a given value. When neither of
1520 these considerations is important, the choice is a matter of taste, as
1521 long as you are consistent about it for any given alist.
1523 Note that the same alist shown above could be regarded as having the
1524 associated value in the @sc{cdr} of the element; the value associated
1525 with @code{rose} would be the list @code{(red)}.
1527 Association lists are often used to record information that you might
1528 otherwise keep on a stack, since new associations may be added easily to
1529 the front of the list. When searching an association list for an
1530 association with a given key, the first one found is returned, if there
1533 In Emacs Lisp, it is @emph{not} an error if an element of an
1534 association list is not a cons cell. The alist search functions simply
1535 ignore such elements. Many other versions of Lisp signal errors in such
1538 Note that property lists are similar to association lists in several
1539 respects. A property list behaves like an association list in which
1540 each key can occur only once. @xref{Property Lists}, for a comparison
1541 of property lists and association lists.
1543 @defun assoc key alist
1544 This function returns the first association for @var{key} in
1545 @var{alist}. It compares @var{key} against the alist elements using
1546 @code{equal} (@pxref{Equality Predicates}). It returns @code{nil} if no
1547 association in @var{alist} has a @sc{car} @code{equal} to @var{key}.
1551 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1552 @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1554 @result{} (oak . acorns)
1555 (cdr (assoc 'oak trees))
1557 (assoc 'birch trees)
1561 Here is another example, in which the keys and values are not symbols:
1564 (setq needles-per-cluster
1565 '((2 "Austrian Pine" "Red Pine")
1569 (cdr (assoc 3 needles-per-cluster))
1570 @result{} ("Pitch Pine")
1571 (cdr (assoc 2 needles-per-cluster))
1572 @result{} ("Austrian Pine" "Red Pine")
1576 The function @code{assoc-string} is much like @code{assoc} except
1577 that it ignores certain differences between strings. @xref{Text
1580 @defun rassoc value alist
1581 This function returns the first association with value @var{value} in
1582 @var{alist}. It returns @code{nil} if no association in @var{alist} has
1583 a @sc{cdr} @code{equal} to @var{value}.
1585 @code{rassoc} is like @code{assoc} except that it compares the @sc{cdr} of
1586 each @var{alist} association instead of the @sc{car}. You can think of
1587 this as ``reverse @code{assoc}'', finding the key for a given value.
1590 @defun assq key alist
1591 This function is like @code{assoc} in that it returns the first
1592 association for @var{key} in @var{alist}, but it makes the comparison
1593 using @code{eq} instead of @code{equal}. @code{assq} returns @code{nil}
1594 if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}.
1595 This function is used more often than @code{assoc}, since @code{eq} is
1596 faster than @code{equal} and most alists use symbols as keys.
1597 @xref{Equality Predicates}.
1600 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1601 @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1603 @result{} (pine . cones)
1606 On the other hand, @code{assq} is not usually useful in alists where the
1607 keys may not be symbols:
1611 '(("simple leaves" . oak)
1612 ("compound leaves" . horsechestnut)))
1614 (assq "simple leaves" leaves)
1616 (assoc "simple leaves" leaves)
1617 @result{} ("simple leaves" . oak)
1621 @defun rassq value alist
1622 This function returns the first association with value @var{value} in
1623 @var{alist}. It returns @code{nil} if no association in @var{alist} has
1624 a @sc{cdr} @code{eq} to @var{value}.
1626 @code{rassq} is like @code{assq} except that it compares the @sc{cdr} of
1627 each @var{alist} association instead of the @sc{car}. You can think of
1628 this as ``reverse @code{assq}'', finding the key for a given value.
1633 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1635 (rassq 'acorns trees)
1636 @result{} (oak . acorns)
1637 (rassq 'spores trees)
1641 Note that @code{rassq} cannot search for a value stored in the @sc{car}
1642 of the @sc{cdr} of an element:
1645 (setq colors '((rose red) (lily white) (buttercup yellow)))
1647 (rassq 'white colors)
1651 In this case, the @sc{cdr} of the association @code{(lily white)} is not
1652 the symbol @code{white}, but rather the list @code{(white)}. This
1653 becomes clearer if the association is written in dotted pair notation:
1656 (lily white) @equiv{} (lily . (white))
1660 @defun assoc-default key alist &optional test default
1661 This function searches @var{alist} for a match for @var{key}. For each
1662 element of @var{alist}, it compares the element (if it is an atom) or
1663 the element's @sc{car} (if it is a cons) against @var{key}, by calling
1664 @var{test} with two arguments: the element or its @sc{car}, and
1665 @var{key}. The arguments are passed in that order so that you can get
1666 useful results using @code{string-match} with an alist that contains
1667 regular expressions (@pxref{Regexp Search}). If @var{test} is omitted
1668 or @code{nil}, @code{equal} is used for comparison.
1670 If an alist element matches @var{key} by this criterion,
1671 then @code{assoc-default} returns a value based on this element.
1672 If the element is a cons, then the value is the element's @sc{cdr}.
1673 Otherwise, the return value is @var{default}.
1675 If no alist element matches @var{key}, @code{assoc-default} returns
1679 @defun copy-alist alist
1680 @cindex copying alists
1681 This function returns a two-level deep copy of @var{alist}: it creates a
1682 new copy of each association, so that you can alter the associations of
1683 the new alist without changing the old one.
1687 (setq needles-per-cluster
1688 '((2 . ("Austrian Pine" "Red Pine"))
1689 (3 . ("Pitch Pine"))
1691 (5 . ("White Pine"))))
1693 ((2 "Austrian Pine" "Red Pine")
1697 (setq copy (copy-alist needles-per-cluster))
1699 ((2 "Austrian Pine" "Red Pine")
1703 (eq needles-per-cluster copy)
1705 (equal needles-per-cluster copy)
1707 (eq (car needles-per-cluster) (car copy))
1709 (cdr (car (cdr needles-per-cluster)))
1710 @result{} ("Pitch Pine")
1712 (eq (cdr (car (cdr needles-per-cluster)))
1713 (cdr (car (cdr copy))))
1718 This example shows how @code{copy-alist} makes it possible to change
1719 the associations of one copy without affecting the other:
1723 (setcdr (assq 3 copy) '("Martian Vacuum Pine"))
1724 (cdr (assq 3 needles-per-cluster))
1725 @result{} ("Pitch Pine")
1730 @defun assq-delete-all key alist
1731 @tindex assq-delete-all
1732 This function deletes from @var{alist} all the elements whose @sc{car}
1733 is @code{eq} to @var{key}, much as if you used @code{delq} to delete
1734 each such element one by one. It returns the shortened alist, and
1735 often modifies the original list structure of @var{alist}. For
1736 correct results, use the return value of @code{assq-delete-all} rather
1737 than looking at the saved value of @var{alist}.
1740 (setq alist '((foo 1) (bar 2) (foo 3) (lose 4)))
1741 @result{} ((foo 1) (bar 2) (foo 3) (lose 4))
1742 (assq-delete-all 'foo alist)
1743 @result{} ((bar 2) (lose 4))
1745 @result{} ((foo 1) (bar 2) (lose 4))
1750 arch-tag: 31fb8a4e-4aa8-4a74-a206-aa00451394d4