[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Emacs-diffs] Changes to lists.texi
|
From: |
Glenn Morris |
|
Subject: |
[Emacs-diffs] Changes to lists.texi |
|
Date: |
Thu, 06 Sep 2007 04:21:19 +0000 |
CVSROOT: /sources/emacs
Module name: emacs
Changes by: Glenn Morris <gm> 07/09/06 04:21:18
Index: lists.texi
===================================================================
RCS file: lists.texi
diff -N lists.texi
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ lists.texi 6 Sep 2007 04:21:18 -0000 1.1
@@ -0,0 +1,1904 @@
address@hidden -*-texinfo-*-
address@hidden This is part of the GNU Emacs Lisp Reference Manual.
address@hidden Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998, 1999,
2001,
address@hidden 2002, 2003, 2004, 2005, 2006, 2007 Free Software Foundation,
Inc.
address@hidden See the file elisp.texi for copying conditions.
address@hidden ../info/lists
address@hidden Lists, Sequences Arrays Vectors, Strings and Characters, Top
address@hidden Lists
address@hidden lists
address@hidden element (of list)
+
+ A @dfn{list} represents a sequence of zero or more elements (which may
+be any Lisp objects). The important difference between lists and
+vectors is that two or more lists can share part of their structure; in
+addition, you can insert or delete elements in a list without copying
+the whole list.
+
address@hidden
+* Cons Cells:: How lists are made out of cons cells.
+* List-related Predicates:: Is this object a list? Comparing two lists.
+* List Elements:: Extracting the pieces of a list.
+* Building Lists:: Creating list structure.
+* List Variables:: Modifying lists stored in variables.
+* Modifying Lists:: Storing new pieces into an existing list.
+* Sets And Lists:: A list can represent a finite mathematical set.
+* Association Lists:: A list can represent a finite relation or mapping.
+* Rings:: Managing a fixed-size ring of objects.
address@hidden menu
+
address@hidden Cons Cells
address@hidden Lists and Cons Cells
address@hidden lists and cons cells
+
+ Lists in Lisp are not a primitive data type; they are built up from
address@hidden cells}. A cons cell is a data object that represents an
+ordered pair. That is, it has two slots, and each slot @dfn{holds}, or
address@hidden to}, some Lisp object. One slot is known as the @sc{car},
+and the other is known as the @sc{cdr}. (These names are traditional;
+see @ref{Cons Cell Type}.) @sc{cdr} is pronounced ``could-er.''
+
+ We say that ``the @sc{car} of this cons cell is'' whatever object
+its @sc{car} slot currently holds, and likewise for the @sc{cdr}.
+
+ A list is a series of cons cells ``chained together,'' so that each
+cell refers to the next one. There is one cons cell for each element of
+the list. By convention, the @sc{car}s of the cons cells hold the
+elements of the list, and the @sc{cdr}s are used to chain the list: the
address@hidden slot of each cons cell refers to the following cons cell. The
address@hidden of the last cons cell is @code{nil}. This asymmetry between
+the @sc{car} and the @sc{cdr} is entirely a matter of convention; at the
+level of cons cells, the @sc{car} and @sc{cdr} slots have the same
+characteristics.
+
address@hidden true list
+ Since @code{nil} is the conventional value to put in the @sc{cdr} of
+the last cons cell in the list, we call that case a @dfn{true list}.
+
+ In Lisp, we consider the symbol @code{nil} a list as well as a
+symbol; it is the list with no elements. For convenience, the symbol
address@hidden is considered to have @code{nil} as its @sc{cdr} (and also
+as its @sc{car}). Therefore, the @sc{cdr} of a true list is always a
+true list.
+
address@hidden dotted list
address@hidden circular list
+ If the @sc{cdr} of a list's last cons cell is some other value,
+neither @code{nil} nor another cons cell, we call the structure a
address@hidden list}, since its printed representation would use
address@hidden There is one other possibility: some cons cell's @sc{cdr}
+could point to one of the previous cons cells in the list. We call
+that structure a @dfn{circular list}.
+
+ For some purposes, it does not matter whether a list is true,
+circular or dotted. If the program doesn't look far enough down the
+list to see the @sc{cdr} of the final cons cell, it won't care.
+However, some functions that operate on lists demand true lists and
+signal errors if given a dotted list. Most functions that try to find
+the end of a list enter infinite loops if given a circular list.
+
address@hidden list structure
+ Because most cons cells are used as part of lists, the phrase
address@hidden structure} has come to mean any structure made out of cons
+cells.
+
+ The @sc{cdr} of any nonempty true list @var{l} is a list containing all the
+elements of @var{l} except the first.
+
+ @xref{Cons Cell Type}, for the read and print syntax of cons cells and
+lists, and for ``box and arrow'' illustrations of lists.
+
address@hidden List-related Predicates
address@hidden Predicates on Lists
+
+ The following predicates test whether a Lisp object is an atom,
+whether it is a cons cell or is a list, or whether it is the
+distinguished object @code{nil}. (Many of these predicates can be
+defined in terms of the others, but they are used so often that it is
+worth having all of them.)
+
address@hidden consp object
+This function returns @code{t} if @var{object} is a cons cell, @code{nil}
+otherwise. @code{nil} is not a cons cell, although it @emph{is} a list.
address@hidden defun
+
address@hidden atom object
+This function returns @code{t} if @var{object} is an atom, @code{nil}
+otherwise. All objects except cons cells are atoms. The symbol
address@hidden is an atom and is also a list; it is the only Lisp object
+that is both.
+
address@hidden
+(atom @var{object}) @equiv{} (not (consp @var{object}))
address@hidden example
address@hidden defun
+
address@hidden listp object
+This function returns @code{t} if @var{object} is a cons cell or
address@hidden Otherwise, it returns @code{nil}.
+
address@hidden
address@hidden
+(listp '(1))
+ @result{} t
address@hidden group
address@hidden
+(listp '())
+ @result{} t
address@hidden group
address@hidden example
address@hidden defun
+
address@hidden nlistp object
+This function is the opposite of @code{listp}: it returns @code{t} if
address@hidden is not a list. Otherwise, it returns @code{nil}.
+
address@hidden
+(listp @var{object}) @equiv{} (not (nlistp @var{object}))
address@hidden example
address@hidden defun
+
address@hidden null object
+This function returns @code{t} if @var{object} is @code{nil}, and
+returns @code{nil} otherwise. This function is identical to @code{not},
+but as a matter of clarity we use @code{null} when @var{object} is
+considered a list and @code{not} when it is considered a truth value
+(see @code{not} in @ref{Combining Conditions}).
+
address@hidden
address@hidden
+(null '(1))
+ @result{} nil
address@hidden group
address@hidden
+(null '())
+ @result{} t
address@hidden group
address@hidden example
address@hidden defun
+
+
address@hidden List Elements
address@hidden Accessing Elements of Lists
address@hidden list elements
+
address@hidden car cons-cell
+This function returns the value referred to by the first slot of the
+cons cell @var{cons-cell}. Expressed another way, this function
+returns the @sc{car} of @var{cons-cell}.
+
+As a special case, if @var{cons-cell} is @code{nil}, then @code{car}
+is defined to return @code{nil}; therefore, any list is a valid argument
+for @code{car}. An error is signaled if the argument is not a cons cell
+or @code{nil}.
+
address@hidden
address@hidden
+(car '(a b c))
+ @result{} a
address@hidden group
address@hidden
+(car '())
+ @result{} nil
address@hidden group
address@hidden example
address@hidden defun
+
address@hidden cdr cons-cell
+This function returns the value referred to by the second slot of
+the cons cell @var{cons-cell}. Expressed another way, this function
+returns the @sc{cdr} of @var{cons-cell}.
+
+As a special case, if @var{cons-cell} is @code{nil}, then @code{cdr}
+is defined to return @code{nil}; therefore, any list is a valid argument
+for @code{cdr}. An error is signaled if the argument is not a cons cell
+or @code{nil}.
+
address@hidden
address@hidden
+(cdr '(a b c))
+ @result{} (b c)
address@hidden group
address@hidden
+(cdr '())
+ @result{} nil
address@hidden group
address@hidden example
address@hidden defun
+
address@hidden car-safe object
+This function lets you take the @sc{car} of a cons cell while avoiding
+errors for other data types. It returns the @sc{car} of @var{object} if
address@hidden is a cons cell, @code{nil} otherwise. This is in contrast
+to @code{car}, which signals an error if @var{object} is not a list.
+
address@hidden
address@hidden
+(car-safe @var{object})
address@hidden
+(let ((x @var{object}))
+ (if (consp x)
+ (car x)
+ nil))
address@hidden group
address@hidden example
address@hidden defun
+
address@hidden cdr-safe object
+This function lets you take the @sc{cdr} of a cons cell while
+avoiding errors for other data types. It returns the @sc{cdr} of
address@hidden if @var{object} is a cons cell, @code{nil} otherwise.
+This is in contrast to @code{cdr}, which signals an error if
address@hidden is not a list.
+
address@hidden
address@hidden
+(cdr-safe @var{object})
address@hidden
+(let ((x @var{object}))
+ (if (consp x)
+ (cdr x)
+ nil))
address@hidden group
address@hidden example
address@hidden defun
+
address@hidden pop listname
+This macro is a way of examining the @sc{car} of a list,
+and taking it off the list, all at once.
+
+It operates on the list which is stored in the symbol @var{listname}.
+It removes this element from the list by setting @var{listname}
+to the @sc{cdr} of its old value---but it also returns the @sc{car}
+of that list, which is the element being removed.
+
address@hidden
+x
+ @result{} (a b c)
+(pop x)
+ @result{} a
+x
+ @result{} (b c)
address@hidden example
address@hidden defmac
+
address@hidden nth n list
address@hidden of nth}
+This function returns the @var{n}th element of @var{list}. Elements
+are numbered starting with zero, so the @sc{car} of @var{list} is
+element number zero. If the length of @var{list} is @var{n} or less,
+the value is @code{nil}.
+
+If @var{n} is negative, @code{nth} returns the first element of
address@hidden
+
address@hidden
address@hidden
+(nth 2 '(1 2 3 4))
+ @result{} 3
address@hidden group
address@hidden
+(nth 10 '(1 2 3 4))
+ @result{} nil
address@hidden group
address@hidden
+(nth -3 '(1 2 3 4))
+ @result{} 1
+
+(nth n x) @equiv{} (car (nthcdr n x))
address@hidden group
address@hidden example
+
+The function @code{elt} is similar, but applies to any kind of sequence.
+For historical reasons, it takes its arguments in the opposite order.
address@hidden Functions}.
address@hidden defun
+
address@hidden nthcdr n list
+This function returns the @var{n}th @sc{cdr} of @var{list}. In other
+words, it skips past the first @var{n} links of @var{list} and returns
+what follows.
+
+If @var{n} is zero or negative, @code{nthcdr} returns all of
address@hidden If the length of @var{list} is @var{n} or less,
address@hidden returns @code{nil}.
+
address@hidden
address@hidden
+(nthcdr 1 '(1 2 3 4))
+ @result{} (2 3 4)
address@hidden group
address@hidden
+(nthcdr 10 '(1 2 3 4))
+ @result{} nil
address@hidden group
address@hidden
+(nthcdr -3 '(1 2 3 4))
+ @result{} (1 2 3 4)
address@hidden group
address@hidden example
address@hidden defun
+
address@hidden last list &optional n
+This function returns the last link of @var{list}. The @code{car} of
+this link is the list's last element. If @var{list} is null,
address@hidden is returned. If @var{n} is address@hidden, the
address@hidden link is returned instead, or the whole of @var{list}
+if @var{n} is bigger than @var{list}'s length.
address@hidden defun
+
address@hidden safe-length list
address@hidden of safe-length}
+This function returns the length of @var{list}, with no risk of either
+an error or an infinite loop. It generally returns the number of
+distinct cons cells in the list. However, for circular lists,
+the value is just an upper bound; it is often too large.
+
+If @var{list} is not @code{nil} or a cons cell, @code{safe-length}
+returns 0.
address@hidden defun
+
+ The most common way to compute the length of a list, when you are not
+worried that it may be circular, is with @code{length}. @xref{Sequence
+Functions}.
+
address@hidden caar cons-cell
+This is the same as @code{(car (car @var{cons-cell}))}.
address@hidden defun
+
address@hidden cadr cons-cell
+This is the same as @code{(car (cdr @var{cons-cell}))}
+or @code{(nth 1 @var{cons-cell})}.
address@hidden defun
+
address@hidden cdar cons-cell
+This is the same as @code{(cdr (car @var{cons-cell}))}.
address@hidden defun
+
address@hidden cddr cons-cell
+This is the same as @code{(cdr (cdr @var{cons-cell}))}
+or @code{(nthcdr 2 @var{cons-cell})}.
address@hidden defun
+
address@hidden butlast x &optional n
+This function returns the list @var{x} with the last element,
+or the last @var{n} elements, removed. If @var{n} is greater
+than zero it makes a copy of the list so as not to damage the
+original list. In general, @code{(append (butlast @var{x} @var{n})
+(last @var{x} @var{n}))} will return a list equal to @var{x}.
address@hidden defun
+
address@hidden nbutlast x &optional n
+This is a version of @code{butlast} that works by destructively
+modifying the @code{cdr} of the appropriate element, rather than
+making a copy of the list.
address@hidden defun
+
address@hidden Building Lists
address@hidden node-name, next, previous, up
address@hidden Building Cons Cells and Lists
address@hidden cons cells
address@hidden building lists
+
+ Many functions build lists, as lists reside at the very heart of Lisp.
address@hidden is the fundamental list-building function; however, it is
+interesting to note that @code{list} is used more times in the source
+code for Emacs than @code{cons}.
+
address@hidden cons object1 object2
+This function is the most basic function for building new list
+structure. It creates a new cons cell, making @var{object1} the
address@hidden, and @var{object2} the @sc{cdr}. It then returns the new
+cons cell. The arguments @var{object1} and @var{object2} may be any
+Lisp objects, but most often @var{object2} is a list.
+
address@hidden
address@hidden
+(cons 1 '(2))
+ @result{} (1 2)
address@hidden group
address@hidden
+(cons 1 '())
+ @result{} (1)
address@hidden group
address@hidden
+(cons 1 2)
+ @result{} (1 . 2)
address@hidden group
address@hidden example
+
address@hidden consing
address@hidden is often used to add a single element to the front of a
+list. This is called @dfn{consing the element onto the list}.
address@hidden is no strictly equivalent way to add an element to
+the end of a list. You can use @code{(append @var{listname} (list
address@hidden))}, which creates a whole new list by copying @var{listname}
+and adding @var{newelt} to its end. Or you can use @code{(nconc
address@hidden (list @var{newelt}))}, which modifies @var{listname}
+by following all the @sc{cdr}s and then replacing the terminating
address@hidden Compare this to adding an element to the beginning of a
+list with @code{cons}, which neither copies nor modifies the list.}
+For example:
+
address@hidden
+(setq list (cons newelt list))
address@hidden example
+
+Note that there is no conflict between the variable named @code{list}
+used in this example and the function named @code{list} described below;
+any symbol can serve both purposes.
address@hidden defun
+
address@hidden list &rest objects
+This function creates a list with @var{objects} as its elements. The
+resulting list is always @code{nil}-terminated. If no @var{objects}
+are given, the empty list is returned.
+
address@hidden
address@hidden
+(list 1 2 3 4 5)
+ @result{} (1 2 3 4 5)
address@hidden group
address@hidden
+(list 1 2 '(3 4 5) 'foo)
+ @result{} (1 2 (3 4 5) foo)
address@hidden group
address@hidden
+(list)
+ @result{} nil
address@hidden group
address@hidden example
address@hidden defun
+
address@hidden make-list length object
+This function creates a list of @var{length} elements, in which each
+element is @var{object}. Compare @code{make-list} with
address@hidden (@pxref{Creating Strings}).
+
address@hidden
address@hidden
+(make-list 3 'pigs)
+ @result{} (pigs pigs pigs)
address@hidden group
address@hidden
+(make-list 0 'pigs)
+ @result{} nil
address@hidden group
address@hidden
+(setq l (make-list 3 '(a b))
+ @result{} ((a b) (a b) (a b))
+(eq (car l) (cadr l))
+ @result{} t
address@hidden group
address@hidden example
address@hidden defun
+
address@hidden append &rest sequences
address@hidden copying lists
+This function returns a list containing all the elements of
address@hidden The @var{sequences} may be lists, vectors,
+bool-vectors, or strings, but the last one should usually be a list.
+All arguments except the last one are copied, so none of the arguments
+is altered. (See @code{nconc} in @ref{Rearrangement}, for a way to join
+lists with no copying.)
+
+More generally, the final argument to @code{append} may be any Lisp
+object. The final argument is not copied or converted; it becomes the
address@hidden of the last cons cell in the new list. If the final argument
+is itself a list, then its elements become in effect elements of the
+result list. If the final element is not a list, the result is a
+dotted list since its final @sc{cdr} is not @code{nil} as required
+in a true list.
+
+In Emacs 20 and before, the @code{append} function also allowed
+integers as (non last) arguments. It converted them to strings of
+digits, making up the decimal print representation of the integer, and
+then used the strings instead of the original integers. This obsolete
+usage no longer works. The proper way to convert an integer to a
+decimal number in this way is with @code{format} (@pxref{Formatting
+Strings}) or @code{number-to-string} (@pxref{String Conversion}).
address@hidden defun
+
+ Here is an example of using @code{append}:
+
address@hidden
address@hidden
+(setq trees '(pine oak))
+ @result{} (pine oak)
+(setq more-trees (append '(maple birch) trees))
+ @result{} (maple birch pine oak)
address@hidden group
+
address@hidden
+trees
+ @result{} (pine oak)
+more-trees
+ @result{} (maple birch pine oak)
address@hidden group
address@hidden
+(eq trees (cdr (cdr more-trees)))
+ @result{} t
address@hidden group
address@hidden example
+
+ You can see how @code{append} works by looking at a box diagram. The
+variable @code{trees} is set to the list @code{(pine oak)} and then the
+variable @code{more-trees} is set to the list @code{(maple birch pine
+oak)}. However, the variable @code{trees} continues to refer to the
+original list:
+
address@hidden
address@hidden
+more-trees trees
+| |
+| --- --- --- --- -> --- --- --- ---
+ --> | | |--> | | |--> | | |--> | | |--> nil
+ --- --- --- --- --- --- --- ---
+ | | | |
+ | | | |
+ --> maple -->birch --> pine --> oak
address@hidden group
address@hidden smallexample
+
+ An empty sequence contributes nothing to the value returned by
address@hidden As a consequence of this, a final @code{nil} argument
+forces a copy of the previous argument:
+
address@hidden
address@hidden
+trees
+ @result{} (pine oak)
address@hidden group
address@hidden
+(setq wood (append trees nil))
+ @result{} (pine oak)
address@hidden group
address@hidden
+wood
+ @result{} (pine oak)
address@hidden group
address@hidden
+(eq wood trees)
+ @result{} nil
address@hidden group
address@hidden example
+
address@hidden
+This once was the usual way to copy a list, before the function
address@hidden was invented. @xref{Sequences Arrays Vectors}.
+
+ Here we show the use of vectors and strings as arguments to @code{append}:
+
address@hidden
address@hidden
+(append [a b] "cd" nil)
+ @result{} (a b 99 100)
address@hidden group
address@hidden example
+
+ With the help of @code{apply} (@pxref{Calling Functions}), we can append
+all the lists in a list of lists:
+
address@hidden
address@hidden
+(apply 'append '((a b c) nil (x y z) nil))
+ @result{} (a b c x y z)
address@hidden group
address@hidden example
+
+ If no @var{sequences} are given, @code{nil} is returned:
+
address@hidden
address@hidden
+(append)
+ @result{} nil
address@hidden group
address@hidden example
+
+ Here are some examples where the final argument is not a list:
+
address@hidden
+(append '(x y) 'z)
+ @result{} (x y . z)
+(append '(x y) [z])
+ @result{} (x y . [z])
address@hidden example
+
address@hidden
+The second example shows that when the final argument is a sequence but
+not a list, the sequence's elements do not become elements of the
+resulting list. Instead, the sequence becomes the final @sc{cdr}, like
+any other non-list final argument.
+
address@hidden reverse list
+This function creates a new list whose elements are the elements of
address@hidden, but in reverse order. The original argument @var{list} is
address@hidden altered.
+
address@hidden
address@hidden
+(setq x '(1 2 3 4))
+ @result{} (1 2 3 4)
address@hidden group
address@hidden
+(reverse x)
+ @result{} (4 3 2 1)
+x
+ @result{} (1 2 3 4)
address@hidden group
address@hidden example
address@hidden defun
+
address@hidden copy-tree tree &optional vecp
+This function returns a copy of the tree @code{tree}. If @var{tree} is a
+cons cell, this makes a new cons cell with the same @sc{car} and
address@hidden, then recursively copies the @sc{car} and @sc{cdr} in the
+same way.
+
+Normally, when @var{tree} is anything other than a cons cell,
address@hidden simply returns @var{tree}. However, if @var{vecp} is
address@hidden, it copies vectors too (and operates recursively on
+their elements).
address@hidden defun
+
address@hidden number-sequence from &optional to separation
+This returns a list of numbers starting with @var{from} and
+incrementing by @var{separation}, and ending at or just before
address@hidden @var{separation} can be positive or negative and defaults
+to 1. If @var{to} is @code{nil} or numerically equal to @var{from},
+the value is the one-element list @code{(@var{from})}. If @var{to} is
+less than @var{from} with a positive @var{separation}, or greater than
address@hidden with a negative @var{separation}, the value is @code{nil}
+because those arguments specify an empty sequence.
+
+If @var{separation} is 0 and @var{to} is neither @code{nil} nor
+numerically equal to @var{from}, @code{number-sequence} signals an
+error, since those arguments specify an infinite sequence.
+
+All arguments can be integers or floating point numbers. However,
+floating point arguments can be tricky, because floating point
+arithmetic is inexact. For instance, depending on the machine, it may
+quite well happen that @code{(number-sequence 0.4 0.6 0.2)} returns
+the one element list @code{(0.4)}, whereas
address@hidden(number-sequence 0.4 0.8 0.2)} returns a list with three
+elements. The @var{n}th element of the list is computed by the exact
+formula @code{(+ @var{from} (* @var{n} @var{separation}))}. Thus, if
+one wants to make sure that @var{to} is included in the list, one can
+pass an expression of this exact type for @var{to}. Alternatively,
+one can replace @var{to} with a slightly larger value (or a slightly
+more negative value if @var{separation} is negative).
+
+Some examples:
+
address@hidden
+(number-sequence 4 9)
+ @result{} (4 5 6 7 8 9)
+(number-sequence 9 4 -1)
+ @result{} (9 8 7 6 5 4)
+(number-sequence 9 4 -2)
+ @result{} (9 7 5)
+(number-sequence 8)
+ @result{} (8)
+(number-sequence 8 5)
+ @result{} nil
+(number-sequence 5 8 -1)
+ @result{} nil
+(number-sequence 1.5 6 2)
+ @result{} (1.5 3.5 5.5)
address@hidden example
address@hidden defun
+
address@hidden List Variables
address@hidden Modifying List Variables
+
+ These functions, and one macro, provide convenient ways
+to modify a list which is stored in a variable.
+
address@hidden push newelt listname
+This macro provides an alternative way to write
address@hidden(setq @var{listname} (cons @var{newelt} @var{listname}))}.
+
address@hidden
+(setq l '(a b))
+ @result{} (a b)
+(push 'c l)
+ @result{} (c a b)
+l
+ @result{} (c a b)
address@hidden example
address@hidden defmac
+
+ Two functions modify lists that are the values of variables.
+
address@hidden add-to-list symbol element &optional append compare-fn
+This function sets the variable @var{symbol} by consing @var{element}
+onto the old value, if @var{element} is not already a member of that
+value. It returns the resulting list, whether updated or not. The
+value of @var{symbol} had better be a list already before the call.
address@hidden uses @var{compare-fn} to compare @var{element}
+against existing list members; if @var{compare-fn} is @code{nil}, it
+uses @code{equal}.
+
+Normally, if @var{element} is added, it is added to the front of
address@hidden, but if the optional argument @var{append} is
address@hidden, it is added at the end.
+
+The argument @var{symbol} is not implicitly quoted; @code{add-to-list}
+is an ordinary function, like @code{set} and unlike @code{setq}. Quote
+the argument yourself if that is what you want.
address@hidden defun
+
+Here's a scenario showing how to use @code{add-to-list}:
+
address@hidden
+(setq foo '(a b))
+ @result{} (a b)
+
+(add-to-list 'foo 'c) ;; @r{Add @code{c}.}
+ @result{} (c a b)
+
+(add-to-list 'foo 'b) ;; @r{No effect.}
+ @result{} (c a b)
+
+foo ;; @address@hidden was changed.}
+ @result{} (c a b)
address@hidden example
+
+ An equivalent expression for @code{(add-to-list '@var{var}
address@hidden)} is this:
+
address@hidden
+(or (member @var{value} @var{var})
+ (setq @var{var} (cons @var{value} @var{var})))
address@hidden example
+
address@hidden add-to-ordered-list symbol element &optional order
+This function sets the variable @var{symbol} by inserting
address@hidden into the old value, which must be a list, at the
+position specified by @var{order}. If @var{element} is already a
+member of the list, its position in the list is adjusted according
+to @var{order}. Membership is tested using @code{eq}.
+This function returns the resulting list, whether updated or not.
+
+The @var{order} is typically a number (integer or float), and the
+elements of the list are sorted in non-decreasing numerical order.
+
address@hidden may also be omitted or @code{nil}. Then the numeric order
+of @var{element} stays unchanged if it already has one; otherwise,
address@hidden has no numeric order. Elements without a numeric list
+order are placed at the end of the list, in no particular order.
+
+Any other value for @var{order} removes the numeric order of @var{element}
+if it already has one; otherwise, it is equivalent to @code{nil}.
+
+The argument @var{symbol} is not implicitly quoted;
address@hidden is an ordinary function, like @code{set}
+and unlike @code{setq}. Quote the argument yourself if that is what
+you want.
+
+The ordering information is stored in a hash table on @var{symbol}'s
address@hidden property.
address@hidden defun
+
+Here's a scenario showing how to use @code{add-to-ordered-list}:
+
address@hidden
+(setq foo '())
+ @result{} nil
+
+(add-to-ordered-list 'foo 'a 1) ;; @r{Add @code{a}.}
+ @result{} (a)
+
+(add-to-ordered-list 'foo 'c 3) ;; @r{Add @code{c}.}
+ @result{} (a c)
+
+(add-to-ordered-list 'foo 'b 2) ;; @r{Add @code{b}.}
+ @result{} (a b c)
+
+(add-to-ordered-list 'foo 'b 4) ;; @r{Move @code{b}.}
+ @result{} (a c b)
+
+(add-to-ordered-list 'foo 'd) ;; @r{Append @code{d}.}
+ @result{} (a c b d)
+
+(add-to-ordered-list 'foo 'e) ;; @r{Add @code{e}}.
+ @result{} (a c b e d)
+
+foo ;; @address@hidden was changed.}
+ @result{} (a c b e d)
address@hidden example
+
address@hidden Modifying Lists
address@hidden Modifying Existing List Structure
address@hidden destructive list operations
+
+ You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the
+primitives @code{setcar} and @code{setcdr}. We call these ``destructive''
+operations because they change existing list structure.
+
address@hidden CL address@hidden vs @code{setcar}
address@hidden
address@hidden rplaca
address@hidden rplacd
address@hidden Lisp note:} Common Lisp uses functions @code{rplaca} and
address@hidden to alter list structure; they change structure the same
+way as @code{setcar} and @code{setcdr}, but the Common Lisp functions
+return the cons cell while @code{setcar} and @code{setcdr} return the
+new @sc{car} or @sc{cdr}.
address@hidden quotation
+
address@hidden
+* Setcar:: Replacing an element in a list.
+* Setcdr:: Replacing part of the list backbone.
+ This can be used to remove or add elements.
+* Rearrangement:: Reordering the elements in a list; combining lists.
address@hidden menu
+
address@hidden Setcar
address@hidden Altering List Elements with @code{setcar}
+
+ Changing the @sc{car} of a cons cell is done with @code{setcar}. When
+used on a list, @code{setcar} replaces one element of a list with a
+different element.
+
address@hidden setcar cons object
+This function stores @var{object} as the new @sc{car} of @var{cons},
+replacing its previous @sc{car}. In other words, it changes the
address@hidden slot of @var{cons} to refer to @var{object}. It returns the
+value @var{object}. For example:
+
address@hidden
address@hidden
+(setq x '(1 2))
+ @result{} (1 2)
address@hidden group
address@hidden
+(setcar x 4)
+ @result{} 4
address@hidden group
address@hidden
+x
+ @result{} (4 2)
address@hidden group
address@hidden example
address@hidden defun
+
+ When a cons cell is part of the shared structure of several lists,
+storing a new @sc{car} into the cons changes one element of each of
+these lists. Here is an example:
+
address@hidden
address@hidden
+;; @r{Create two lists that are partly shared.}
+(setq x1 '(a b c))
+ @result{} (a b c)
+(setq x2 (cons 'z (cdr x1)))
+ @result{} (z b c)
address@hidden group
+
address@hidden
+;; @r{Replace the @sc{car} of a shared link.}
+(setcar (cdr x1) 'foo)
+ @result{} foo
+x1 ; @r{Both lists are changed.}
+ @result{} (a foo c)
+x2
+ @result{} (z foo c)
address@hidden group
+
address@hidden
+;; @r{Replace the @sc{car} of a link that is not shared.}
+(setcar x1 'baz)
+ @result{} baz
+x1 ; @r{Only one list is changed.}
+ @result{} (baz foo c)
+x2
+ @result{} (z foo c)
address@hidden group
address@hidden example
+
+ Here is a graphical depiction of the shared structure of the two lists
+in the variables @code{x1} and @code{x2}, showing why replacing @code{b}
+changes them both:
+
address@hidden
address@hidden
+ --- --- --- --- --- ---
+x1---> | | |----> | | |--> | | |--> nil
+ --- --- --- --- --- ---
+ | --> | |
+ | | | |
+ --> a | --> b --> c
+ |
+ --- --- |
+x2--> | | |--
+ --- ---
+ |
+ |
+ --> z
address@hidden group
address@hidden example
+
+ Here is an alternative form of box diagram, showing the same relationship:
+
address@hidden
address@hidden
+x1:
+ -------------- -------------- --------------
+| car | cdr | | car | cdr | | car | cdr |
+| a | o------->| b | o------->| c | nil |
+| | | -->| | | | | |
+ -------------- | -------------- --------------
+ |
+x2: |
+ -------------- |
+| car | cdr | |
+| z | o----
+| | |
+ --------------
address@hidden group
address@hidden example
+
address@hidden Setcdr
address@hidden Altering the CDR of a List
+
+ The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}:
+
address@hidden setcdr cons object
+This function stores @var{object} as the new @sc{cdr} of @var{cons},
+replacing its previous @sc{cdr}. In other words, it changes the
address@hidden slot of @var{cons} to refer to @var{object}. It returns the
+value @var{object}.
address@hidden defun
+
+ Here is an example of replacing the @sc{cdr} of a list with a
+different list. All but the first element of the list are removed in
+favor of a different sequence of elements. The first element is
+unchanged, because it resides in the @sc{car} of the list, and is not
+reached via the @sc{cdr}.
+
address@hidden
address@hidden
+(setq x '(1 2 3))
+ @result{} (1 2 3)
address@hidden group
address@hidden
+(setcdr x '(4))
+ @result{} (4)
address@hidden group
address@hidden
+x
+ @result{} (1 4)
address@hidden group
address@hidden example
+
+ You can delete elements from the middle of a list by altering the
address@hidden of the cons cells in the list. For example, here we delete
+the second element, @code{b}, from the list @code{(a b c)}, by changing
+the @sc{cdr} of the first cons cell:
+
address@hidden
address@hidden
+(setq x1 '(a b c))
+ @result{} (a b c)
+(setcdr x1 (cdr (cdr x1)))
+ @result{} (c)
+x1
+ @result{} (a c)
address@hidden group
address@hidden example
+
+ Here is the result in box notation:
+
address@hidden
address@hidden
+ --------------------
+ | |
+ -------------- | -------------- | --------------
+| car | cdr | | | car | cdr | -->| car | cdr |
+| a | o----- | b | o-------->| c | nil |
+| | | | | | | | |
+ -------------- -------------- --------------
address@hidden group
address@hidden smallexample
+
address@hidden
+The second cons cell, which previously held the element @code{b}, still
+exists and its @sc{car} is still @code{b}, but it no longer forms part
+of this list.
+
+ It is equally easy to insert a new element by changing @sc{cdr}s:
+
address@hidden
address@hidden
+(setq x1 '(a b c))
+ @result{} (a b c)
+(setcdr x1 (cons 'd (cdr x1)))
+ @result{} (d b c)
+x1
+ @result{} (a d b c)
address@hidden group
address@hidden example
+
+ Here is this result in box notation:
+
address@hidden
address@hidden
+ -------------- ------------- -------------
+| car | cdr | | car | cdr | | car | cdr |
+| a | o | -->| b | o------->| c | nil |
+| | | | | | | | | | |
+ --------- | -- | ------------- -------------
+ | |
+ ----- --------
+ | |
+ | --------------- |
+ | | car | cdr | |
+ -->| d | o------
+ | | |
+ ---------------
address@hidden group
address@hidden smallexample
+
address@hidden Rearrangement
address@hidden Functions that Rearrange Lists
address@hidden rearrangement of lists
address@hidden modification of lists
+
+ Here are some functions that rearrange lists ``destructively'' by
+modifying the @sc{cdr}s of their component cons cells. We call these
+functions ``destructive'' because they chew up the original lists passed
+to them as arguments, relinking their cons cells to form a new list that
+is the returned value.
+
address@hidden
+ See @code{delq}, in @ref{Sets And Lists}, for another function
+that modifies cons cells.
address@hidden ifnottex
address@hidden
+ The function @code{delq} in the following section is another example
+of destructive list manipulation.
address@hidden iftex
+
address@hidden nconc &rest lists
address@hidden concatenating lists
address@hidden joining lists
+This function returns a list containing all the elements of @var{lists}.
+Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are
address@hidden copied. Instead, the last @sc{cdr} of each of the
address@hidden is changed to refer to the following list. The last of the
address@hidden is not altered. For example:
+
address@hidden
address@hidden
+(setq x '(1 2 3))
+ @result{} (1 2 3)
address@hidden group
address@hidden
+(nconc x '(4 5))
+ @result{} (1 2 3 4 5)
address@hidden group
address@hidden
+x
+ @result{} (1 2 3 4 5)
address@hidden group
address@hidden example
+
+ Since the last argument of @code{nconc} is not itself modified, it is
+reasonable to use a constant list, such as @code{'(4 5)}, as in the
+above example. For the same reason, the last argument need not be a
+list:
+
address@hidden
address@hidden
+(setq x '(1 2 3))
+ @result{} (1 2 3)
address@hidden group
address@hidden
+(nconc x 'z)
+ @result{} (1 2 3 . z)
address@hidden group
address@hidden
+x
+ @result{} (1 2 3 . z)
address@hidden group
address@hidden example
+
+However, the other arguments (all but the last) must be lists.
+
+A common pitfall is to use a quoted constant list as a non-last
+argument to @code{nconc}. If you do this, your program will change
+each time you run it! Here is what happens:
+
address@hidden
address@hidden
+(defun add-foo (x) ; @r{We want this function to add}
+ (nconc '(foo) x)) ; @address@hidden to the front of its arg.}
address@hidden group
+
address@hidden
+(symbol-function 'add-foo)
+ @result{} (lambda (x) (nconc (quote (foo)) x))
address@hidden group
+
address@hidden
+(setq xx (add-foo '(1 2))) ; @r{It seems to work.}
+ @result{} (foo 1 2)
address@hidden group
address@hidden
+(setq xy (add-foo '(3 4))) ; @r{What happened?}
+ @result{} (foo 1 2 3 4)
address@hidden group
address@hidden
+(eq xx xy)
+ @result{} t
address@hidden group
+
address@hidden
+(symbol-function 'add-foo)
+ @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x)))
address@hidden group
address@hidden smallexample
address@hidden defun
+
address@hidden nreverse list
address@hidden reversing a list
+ This function reverses the order of the elements of @var{list}.
+Unlike @code{reverse}, @code{nreverse} alters its argument by reversing
+the @sc{cdr}s in the cons cells forming the list. The cons cell that
+used to be the last one in @var{list} becomes the first cons cell of the
+value.
+
+ For example:
+
address@hidden
address@hidden
+(setq x '(a b c))
+ @result{} (a b c)
address@hidden group
address@hidden
+x
+ @result{} (a b c)
+(nreverse x)
+ @result{} (c b a)
address@hidden group
address@hidden
+;; @r{The cons cell that was first is now last.}
+x
+ @result{} (a)
address@hidden group
address@hidden example
+
+ To avoid confusion, we usually store the result of @code{nreverse}
+back in the same variable which held the original list:
+
address@hidden
+(setq x (nreverse x))
address@hidden example
+
+ Here is the @code{nreverse} of our favorite example, @code{(a b c)},
+presented graphically:
+
address@hidden
address@hidden
address@hidden list head:} @r{Reversed list:}
+ ------------- ------------- ------------
+| car | cdr | | car | cdr | | car | cdr |
+| a | nil |<-- | b | o |<-- | c | o |
+| | | | | | | | | | | | |
+ ------------- | --------- | - | -------- | -
+ | | | |
+ ------------- ------------
address@hidden group
address@hidden smallexample
address@hidden defun
+
address@hidden sort list predicate
address@hidden stable sort
address@hidden sorting lists
+This function sorts @var{list} stably, though destructively, and
+returns the sorted list. It compares elements using @var{predicate}. A
+stable sort is one in which elements with equal sort keys maintain their
+relative order before and after the sort. Stability is important when
+successive sorts are used to order elements according to different
+criteria.
+
+The argument @var{predicate} must be a function that accepts two
+arguments. It is called with two elements of @var{list}. To get an
+increasing order sort, the @var{predicate} should return address@hidden if the
+first element is ``less than'' the second, or @code{nil} if not.
+
+The comparison function @var{predicate} must give reliable results for
+any given pair of arguments, at least within a single call to
address@hidden It must be @dfn{antisymmetric}; that is, if @var{a} is
+less than @var{b}, @var{b} must not be less than @var{a}. It must be
address@hidden is, if @var{a} is less than @var{b}, and @var{b}
+is less than @var{c}, then @var{a} must be less than @var{c}. If you
+use a comparison function which does not meet these requirements, the
+result of @code{sort} is unpredictable.
+
+The destructive aspect of @code{sort} is that it rearranges the cons
+cells forming @var{list} by changing @sc{cdr}s. A nondestructive sort
+function would create new cons cells to store the elements in their
+sorted order. If you wish to make a sorted copy without destroying the
+original, copy it first with @code{copy-sequence} and then sort.
+
+Sorting does not change the @sc{car}s of the cons cells in @var{list};
+the cons cell that originally contained the element @code{a} in
address@hidden still has @code{a} in its @sc{car} after sorting, but it now
+appears in a different position in the list due to the change of
address@hidden For example:
+
address@hidden
address@hidden
+(setq nums '(1 3 2 6 5 4 0))
+ @result{} (1 3 2 6 5 4 0)
address@hidden group
address@hidden
+(sort nums '<)
+ @result{} (0 1 2 3 4 5 6)
address@hidden group
address@hidden
+nums
+ @result{} (1 2 3 4 5 6)
address@hidden group
address@hidden example
+
address@hidden
address@hidden: Note that the list in @code{nums} no longer contains
+0; this is the same cons cell that it was before, but it is no longer
+the first one in the list. Don't assume a variable that formerly held
+the argument now holds the entire sorted list! Instead, save the result
+of @code{sort} and use that. Most often we store the result back into
+the variable that held the original list:
+
address@hidden
+(setq nums (sort nums '<))
address@hidden example
+
address@hidden, for more functions that perform sorting.
+See @code{documentation} in @ref{Accessing Documentation}, for a
+useful example of @code{sort}.
address@hidden defun
+
address@hidden Sets And Lists
address@hidden Using Lists as Sets
address@hidden lists as sets
address@hidden sets
+
+ A list can represent an unordered mathematical set---simply consider a
+value an element of a set if it appears in the list, and ignore the
+order of the list. To form the union of two sets, use @code{append} (as
+long as you don't mind having duplicate elements). You can remove
address@hidden duplicates using @code{delete-dups}. Other useful
+functions for sets include @code{memq} and @code{delq}, and their
address@hidden versions, @code{member} and @code{delete}.
+
address@hidden CL note---lack @code{union}, @code{intersection}
address@hidden
address@hidden Lisp note:} Common Lisp has functions @code{union} (which
+avoids duplicate elements) and @code{intersection} for set operations,
+but GNU Emacs Lisp does not have them. You can write them in Lisp if
+you wish.
address@hidden quotation
+
address@hidden memq object list
address@hidden membership in a list
+This function tests to see whether @var{object} is a member of
address@hidden If it is, @code{memq} returns a list starting with the
+first occurrence of @var{object}. Otherwise, it returns @code{nil}.
+The letter @samp{q} in @code{memq} says that it uses @code{eq} to
+compare @var{object} against the elements of the list. For example:
+
address@hidden
address@hidden
+(memq 'b '(a b c b a))
+ @result{} (b c b a)
address@hidden group
address@hidden
+(memq '(2) '((1) (2))) ; @address@hidden(2)} and @code{(2)} are not
@code{eq}.}
+ @result{} nil
address@hidden group
address@hidden example
address@hidden defun
+
address@hidden delq object list
address@hidden deleting list elements
+This function destructively removes all elements @code{eq} to
address@hidden from @var{list}. The letter @samp{q} in @code{delq} says
+that it uses @code{eq} to compare @var{object} against the elements of
+the list, like @code{memq} and @code{remq}.
address@hidden defun
+
+When @code{delq} deletes elements from the front of the list, it does so
+simply by advancing down the list and returning a sublist that starts
+after those elements:
+
address@hidden
address@hidden
+(delq 'a '(a b c)) @equiv{} (cdr '(a b c))
address@hidden group
address@hidden example
+
+When an element to be deleted appears in the middle of the list,
+removing it involves changing the @sc{cdr}s (@pxref{Setcdr}).
+
address@hidden
address@hidden
+(setq sample-list '(a b c (4)))
+ @result{} (a b c (4))
address@hidden group
address@hidden
+(delq 'a sample-list)
+ @result{} (b c (4))
address@hidden group
address@hidden
+sample-list
+ @result{} (a b c (4))
address@hidden group
address@hidden
+(delq 'c sample-list)
+ @result{} (a b (4))
address@hidden group
address@hidden
+sample-list
+ @result{} (a b (4))
address@hidden group
address@hidden example
+
+Note that @code{(delq 'c sample-list)} modifies @code{sample-list} to
+splice out the third element, but @code{(delq 'a sample-list)} does not
+splice anything---it just returns a shorter list. Don't assume that a
+variable which formerly held the argument @var{list} now has fewer
+elements, or that it still holds the original list! Instead, save the
+result of @code{delq} and use that. Most often we store the result back
+into the variable that held the original list:
+
address@hidden
+(setq flowers (delq 'rose flowers))
address@hidden example
+
+In the following example, the @code{(4)} that @code{delq} attempts to match
+and the @code{(4)} in the @code{sample-list} are not @code{eq}:
+
address@hidden
address@hidden
+(delq '(4) sample-list)
+ @result{} (a c (4))
address@hidden group
+
+If you want to delete elements that are @code{equal} to a given value,
+use @code{delete} (see below).
address@hidden example
+
address@hidden remq object list
+This function returns a copy of @var{list}, with all elements removed
+which are @code{eq} to @var{object}. The letter @samp{q} in @code{remq}
+says that it uses @code{eq} to compare @var{object} against the elements
+of @code{list}.
+
address@hidden
address@hidden
+(setq sample-list '(a b c a b c))
+ @result{} (a b c a b c)
address@hidden group
address@hidden
+(remq 'a sample-list)
+ @result{} (b c b c)
address@hidden group
address@hidden
+sample-list
+ @result{} (a b c a b c)
address@hidden group
address@hidden example
address@hidden defun
+
address@hidden memql object list
+The function @code{memql} tests to see whether @var{object} is a member
+of @var{list}, comparing members with @var{object} using @code{eql},
+so floating point elements are compared by value.
+If @var{object} is a member, @code{memql} returns a list starting with
+its first occurrence in @var{list}. Otherwise, it returns @code{nil}.
+
+Compare this with @code{memq}:
+
address@hidden
address@hidden
+(memql 1.2 '(1.1 1.2 1.3)) ; @address@hidden and @code{1.2} are @code{eql}.}
+ @result{} (1.2 1.3)
address@hidden group
address@hidden
+(memq 1.2 '(1.1 1.2 1.3)) ; @address@hidden and @code{1.2} are not @code{eq}.}
+ @result{} nil
address@hidden group
address@hidden example
address@hidden defun
+
+The following three functions are like @code{memq}, @code{delq} and
address@hidden, but use @code{equal} rather than @code{eq} to compare
+elements. @xref{Equality Predicates}.
+
address@hidden member object list
+The function @code{member} tests to see whether @var{object} is a member
+of @var{list}, comparing members with @var{object} using @code{equal}.
+If @var{object} is a member, @code{member} returns a list starting with
+its first occurrence in @var{list}. Otherwise, it returns @code{nil}.
+
+Compare this with @code{memq}:
+
address@hidden
address@hidden
+(member '(2) '((1) (2))) ; @address@hidden(2)} and @code{(2)} are
@code{equal}.}
+ @result{} ((2))
address@hidden group
address@hidden
+(memq '(2) '((1) (2))) ; @address@hidden(2)} and @code{(2)} are not
@code{eq}.}
+ @result{} nil
address@hidden group
address@hidden
+;; @r{Two strings with the same contents are @code{equal}.}
+(member "foo" '("foo" "bar"))
+ @result{} ("foo" "bar")
address@hidden group
address@hidden example
address@hidden defun
+
address@hidden delete object sequence
+If @code{sequence} is a list, this function destructively removes all
+elements @code{equal} to @var{object} from @var{sequence}. For lists,
address@hidden is to @code{delq} as @code{member} is to @code{memq}: it
+uses @code{equal} to compare elements with @var{object}, like
address@hidden; when it finds an element that matches, it cuts the
+element out just as @code{delq} would.
+
+If @code{sequence} is a vector or string, @code{delete} returns a copy
+of @code{sequence} with all elements @code{equal} to @code{object}
+removed.
+
+For example:
+
address@hidden
address@hidden
+(setq l '((2) (1) (2)))
+(delete '(2) l)
+ @result{} ((1))
+l
+ @result{} ((2) (1))
+;; @r{If you want to change @code{l} reliably,}
+;; @r{write @code{(setq l (delete elt l))}.}
address@hidden group
address@hidden
+(setq l '((2) (1) (2)))
+(delete '(1) l)
+ @result{} ((2) (2))
+l
+ @result{} ((2) (2))
+;; @r{In this case, it makes no difference whether you set @code{l},}
+;; @r{but you should do so for the sake of the other case.}
address@hidden group
address@hidden
+(delete '(2) [(2) (1) (2)])
+ @result{} [(1)]
address@hidden group
address@hidden example
address@hidden defun
+
address@hidden remove object sequence
+This function is the non-destructive counterpart of @code{delete}. It
+returns a copy of @code{sequence}, a list, vector, or string, with
+elements @code{equal} to @code{object} removed. For example:
+
address@hidden
address@hidden
+(remove '(2) '((2) (1) (2)))
+ @result{} ((1))
address@hidden group
address@hidden
+(remove '(2) [(2) (1) (2)])
+ @result{} [(1)]
address@hidden group
address@hidden example
address@hidden defun
+
address@hidden
address@hidden Lisp note:} The functions @code{member}, @code{delete} and
address@hidden in GNU Emacs Lisp are derived from Maclisp, not Common
+Lisp. The Common Lisp versions do not use @code{equal} to compare
+elements.
address@hidden quotation
+
address@hidden member-ignore-case object list
+This function is like @code{member}, except that @var{object} should
+be a string and that it ignores differences in letter-case and text
+representation: upper-case and lower-case letters are treated as
+equal, and unibyte strings are converted to multibyte prior to
+comparison.
address@hidden defun
+
address@hidden delete-dups list
+This function destructively removes all @code{equal} duplicates from
address@hidden, stores the result in @var{list} and returns it. Of
+several @code{equal} occurrences of an element in @var{list},
address@hidden keeps the first one.
address@hidden defun
+
+ See also the function @code{add-to-list}, in @ref{List Variables},
+for a way to add an element to a list stored in a variable and used as a
+set.
+
address@hidden Association Lists
address@hidden Association Lists
address@hidden association list
address@hidden alist
+
+ An @dfn{association list}, or @dfn{alist} for short, records a mapping
+from keys to values. It is a list of cons cells called
address@hidden: the @sc{car} of each cons cell is the @dfn{key}, and the
address@hidden is the @dfn{associated address@hidden usage of ``key''
+is not related to the term ``key sequence''; it means a value used to
+look up an item in a table. In this case, the table is the alist, and
+the alist associations are the items.}
+
+ Here is an example of an alist. The key @code{pine} is associated with
+the value @code{cones}; the key @code{oak} is associated with
address@hidden; and the key @code{maple} is associated with @code{seeds}.
+
address@hidden
address@hidden
+((pine . cones)
+ (oak . acorns)
+ (maple . seeds))
address@hidden group
address@hidden example
+
+ Both the values and the keys in an alist may be any Lisp objects.
+For example, in the following alist, the symbol @code{a} is
+associated with the number @code{1}, and the string @code{"b"} is
+associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of
+the alist element:
+
address@hidden
+((a . 1) ("b" 2 3))
address@hidden example
+
+ Sometimes it is better to design an alist to store the associated
+value in the @sc{car} of the @sc{cdr} of the element. Here is an
+example of such an alist:
+
address@hidden
+((rose red) (lily white) (buttercup yellow))
address@hidden example
+
address@hidden
+Here we regard @code{red} as the value associated with @code{rose}. One
+advantage of this kind of alist is that you can store other related
+information---even a list of other items---in the @sc{cdr} of the
address@hidden One disadvantage is that you cannot use @code{rassq} (see
+below) to find the element containing a given value. When neither of
+these considerations is important, the choice is a matter of taste, as
+long as you are consistent about it for any given alist.
+
+ The same alist shown above could be regarded as having the
+associated value in the @sc{cdr} of the element; the value associated
+with @code{rose} would be the list @code{(red)}.
+
+ Association lists are often used to record information that you might
+otherwise keep on a stack, since new associations may be added easily to
+the front of the list. When searching an association list for an
+association with a given key, the first one found is returned, if there
+is more than one.
+
+ In Emacs Lisp, it is @emph{not} an error if an element of an
+association list is not a cons cell. The alist search functions simply
+ignore such elements. Many other versions of Lisp signal errors in such
+cases.
+
+ Note that property lists are similar to association lists in several
+respects. A property list behaves like an association list in which
+each key can occur only once. @xref{Property Lists}, for a comparison
+of property lists and association lists.
+
address@hidden assoc key alist
+This function returns the first association for @var{key} in
address@hidden, comparing @var{key} against the alist elements using
address@hidden (@pxref{Equality Predicates}). It returns @code{nil} if no
+association in @var{alist} has a @sc{car} @code{equal} to @var{key}.
+For example:
+
address@hidden
+(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
+ @result{} ((pine . cones) (oak . acorns) (maple . seeds))
+(assoc 'oak trees)
+ @result{} (oak . acorns)
+(cdr (assoc 'oak trees))
+ @result{} acorns
+(assoc 'birch trees)
+ @result{} nil
address@hidden smallexample
+
+Here is another example, in which the keys and values are not symbols:
+
address@hidden
+(setq needles-per-cluster
+ '((2 "Austrian Pine" "Red Pine")
+ (3 "Pitch Pine")
+ (5 "White Pine")))
+
+(cdr (assoc 3 needles-per-cluster))
+ @result{} ("Pitch Pine")
+(cdr (assoc 2 needles-per-cluster))
+ @result{} ("Austrian Pine" "Red Pine")
address@hidden smallexample
address@hidden defun
+
+ The function @code{assoc-string} is much like @code{assoc} except
+that it ignores certain differences between strings. @xref{Text
+Comparison}.
+
address@hidden rassoc value alist
+This function returns the first association with value @var{value} in
address@hidden It returns @code{nil} if no association in @var{alist} has
+a @sc{cdr} @code{equal} to @var{value}.
+
address@hidden is like @code{assoc} except that it compares the @sc{cdr} of
+each @var{alist} association instead of the @sc{car}. You can think of
+this as ``reverse @code{assoc},'' finding the key for a given value.
address@hidden defun
+
address@hidden assq key alist
+This function is like @code{assoc} in that it returns the first
+association for @var{key} in @var{alist}, but it makes the comparison
+using @code{eq} instead of @code{equal}. @code{assq} returns @code{nil}
+if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}.
+This function is used more often than @code{assoc}, since @code{eq} is
+faster than @code{equal} and most alists use symbols as keys.
address@hidden Predicates}.
+
address@hidden
+(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
+ @result{} ((pine . cones) (oak . acorns) (maple . seeds))
+(assq 'pine trees)
+ @result{} (pine . cones)
address@hidden smallexample
+
+On the other hand, @code{assq} is not usually useful in alists where the
+keys may not be symbols:
+
address@hidden
+(setq leaves
+ '(("simple leaves" . oak)
+ ("compound leaves" . horsechestnut)))
+
+(assq "simple leaves" leaves)
+ @result{} nil
+(assoc "simple leaves" leaves)
+ @result{} ("simple leaves" . oak)
address@hidden smallexample
address@hidden defun
+
address@hidden rassq value alist
+This function returns the first association with value @var{value} in
address@hidden It returns @code{nil} if no association in @var{alist} has
+a @sc{cdr} @code{eq} to @var{value}.
+
address@hidden is like @code{assq} except that it compares the @sc{cdr} of
+each @var{alist} association instead of the @sc{car}. You can think of
+this as ``reverse @code{assq},'' finding the key for a given value.
+
+For example:
+
address@hidden
+(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
+
+(rassq 'acorns trees)
+ @result{} (oak . acorns)
+(rassq 'spores trees)
+ @result{} nil
address@hidden smallexample
+
address@hidden cannot search for a value stored in the @sc{car}
+of the @sc{cdr} of an element:
+
address@hidden
+(setq colors '((rose red) (lily white) (buttercup yellow)))
+
+(rassq 'white colors)
+ @result{} nil
address@hidden smallexample
+
+In this case, the @sc{cdr} of the association @code{(lily white)} is not
+the symbol @code{white}, but rather the list @code{(white)}. This
+becomes clearer if the association is written in dotted pair notation:
+
address@hidden
+(lily white) @equiv{} (lily . (white))
address@hidden smallexample
address@hidden defun
+
address@hidden assoc-default key alist &optional test default
+This function searches @var{alist} for a match for @var{key}. For each
+element of @var{alist}, it compares the element (if it is an atom) or
+the element's @sc{car} (if it is a cons) against @var{key}, by calling
address@hidden with two arguments: the element or its @sc{car}, and
address@hidden The arguments are passed in that order so that you can get
+useful results using @code{string-match} with an alist that contains
+regular expressions (@pxref{Regexp Search}). If @var{test} is omitted
+or @code{nil}, @code{equal} is used for comparison.
+
+If an alist element matches @var{key} by this criterion,
+then @code{assoc-default} returns a value based on this element.
+If the element is a cons, then the value is the element's @sc{cdr}.
+Otherwise, the return value is @var{default}.
+
+If no alist element matches @var{key}, @code{assoc-default} returns
address@hidden
address@hidden defun
+
address@hidden copy-alist alist
address@hidden copying alists
+This function returns a two-level deep copy of @var{alist}: it creates a
+new copy of each association, so that you can alter the associations of
+the new alist without changing the old one.
+
address@hidden
address@hidden
+(setq needles-per-cluster
+ '((2 . ("Austrian Pine" "Red Pine"))
+ (3 . ("Pitch Pine"))
address@hidden group
+ (5 . ("White Pine"))))
address@hidden
+((2 "Austrian Pine" "Red Pine")
+ (3 "Pitch Pine")
+ (5 "White Pine"))
+
+(setq copy (copy-alist needles-per-cluster))
address@hidden
+((2 "Austrian Pine" "Red Pine")
+ (3 "Pitch Pine")
+ (5 "White Pine"))
+
+(eq needles-per-cluster copy)
+ @result{} nil
+(equal needles-per-cluster copy)
+ @result{} t
+(eq (car needles-per-cluster) (car copy))
+ @result{} nil
+(cdr (car (cdr needles-per-cluster)))
+ @result{} ("Pitch Pine")
address@hidden
+(eq (cdr (car (cdr needles-per-cluster)))
+ (cdr (car (cdr copy))))
+ @result{} t
address@hidden group
address@hidden smallexample
+
+ This example shows how @code{copy-alist} makes it possible to change
+the associations of one copy without affecting the other:
+
address@hidden
address@hidden
+(setcdr (assq 3 copy) '("Martian Vacuum Pine"))
+(cdr (assq 3 needles-per-cluster))
+ @result{} ("Pitch Pine")
address@hidden group
address@hidden smallexample
address@hidden defun
+
address@hidden assq-delete-all key alist
+This function deletes from @var{alist} all the elements whose @sc{car}
+is @code{eq} to @var{key}, much as if you used @code{delq} to delete
+each such element one by one. It returns the shortened alist, and
+often modifies the original list structure of @var{alist}. For
+correct results, use the return value of @code{assq-delete-all} rather
+than looking at the saved value of @var{alist}.
+
address@hidden
+(setq alist '((foo 1) (bar 2) (foo 3) (lose 4)))
+ @result{} ((foo 1) (bar 2) (foo 3) (lose 4))
+(assq-delete-all 'foo alist)
+ @result{} ((bar 2) (lose 4))
+alist
+ @result{} ((foo 1) (bar 2) (lose 4))
address@hidden example
address@hidden defun
+
address@hidden rassq-delete-all value alist
+This function deletes from @var{alist} all the elements whose @sc{cdr}
+is @code{eq} to @var{value}. It returns the shortened alist, and
+often modifies the original list structure of @var{alist}.
address@hidden is like @code{assq-delete-all} except that it
+compares the @sc{cdr} of each @var{alist} association instead of the
address@hidden
address@hidden defun
+
address@hidden Rings
address@hidden Managing a Fixed-Size Ring of Objects
+
address@hidden ring data structure
+ This section describes functions for operating on rings. A
address@hidden is a fixed-size data structure that supports insertion,
+deletion, rotation, and modulo-indexed reference and traversal.
+
address@hidden make-ring size
+This returns a new ring capable of holding @var{size} objects.
address@hidden should be an integer.
address@hidden defun
+
address@hidden ring-p object
+This returns @code{t} if @var{object} is a ring, @code{nil} otherwise.
address@hidden defun
+
address@hidden ring-size ring
+This returns the maximum capacity of the @var{ring}.
address@hidden defun
+
address@hidden ring-length ring
+This returns the number of objects that @var{ring} currently contains.
+The value will never exceed that returned by @code{ring-size}.
address@hidden defun
+
address@hidden ring-elements ring
+This returns a list of the objects in @var{ring}, in order, newest first.
address@hidden defun
+
address@hidden ring-copy ring
+This returns a new ring which is a copy of @var{ring}.
+The new ring contains the same (@code{eq}) objects as @var{ring}.
address@hidden defun
+
address@hidden ring-empty-p ring
+This returns @code{t} if @var{ring} is empty, @code{nil} otherwise.
address@hidden defun
+
+ The newest element in the ring always has index 0. Higher indices
+correspond to older elements. Indices are computed modulo the ring
+length. Index @minus{}1 corresponds to the oldest element, @minus{}2
+to the next-oldest, and so forth.
+
address@hidden ring-ref ring index
+This returns the object in @var{ring} found at index @var{index}.
address@hidden may be negative or greater than the ring length. If
address@hidden is empty, @code{ring-ref} signals an error.
address@hidden defun
+
address@hidden ring-insert ring object
+This inserts @var{object} into @var{ring}, making it the newest
+element, and returns @var{object}.
+
+If the ring is full, insertion removes the oldest element to
+make room for the new element.
address@hidden defun
+
address@hidden ring-remove ring &optional index
+Remove an object from @var{ring}, and return that object. The
+argument @var{index} specifies which item to remove; if it is
address@hidden, that means to remove the oldest item. If @var{ring} is
+empty, @code{ring-remove} signals an error.
address@hidden defun
+
address@hidden ring-insert-at-beginning ring object
+This inserts @var{object} into @var{ring}, treating it as the oldest
+element. The return value is not significant.
+
+If the ring is full, this function removes the newest element to make
+room for the inserted element.
address@hidden defun
+
address@hidden fifo data structure
+ If you are careful not to exceed the ring size, you can
+use the ring as a first-in-first-out queue. For example:
+
address@hidden
+(let ((fifo (make-ring 5)))
+ (mapc (lambda (obj) (ring-insert fifo obj))
+ '(0 one "two"))
+ (list (ring-remove fifo) t
+ (ring-remove fifo) t
+ (ring-remove fifo)))
+ @result{} (0 t one t "two")
address@hidden lisp
+
address@hidden
+ arch-tag: 31fb8a4e-4aa8-4a74-a206-aa00451394d4
address@hidden ignore
- [Emacs-diffs] Changes to lists.texi,
Glenn Morris <=