@c -*-texinfo-*-
@c This is part of the GNU Emacs Lisp Reference Manual.
-@c Copyright (C) 1990, 1991, 1992, 1993, 1994 Free Software Foundation, Inc.
+@c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998, 1999, 2002, 2003,
+@c 2004, 2005, 2006 Free Software Foundation, Inc.
@c See the file elisp.texi for copying conditions.
@setfilename ../info/lists
@node Lists, Sequences Arrays Vectors, Strings and Characters, Top
@menu
* Cons Cells:: How lists are made out of cons cells.
-* Lists as Boxes:: Graphical notation to explain lists.
* List-related Predicates:: Is this object a list? Comparing two lists.
* List Elements:: Extracting the pieces of a list.
* Building Lists:: Creating list structure.
* 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.
@end menu
@node Cons Cells
Lists in Lisp are not a primitive data type; they are built up from
@dfn{cons cells}. A cons cell is a data object that represents an
-ordered pair. It records two Lisp objects, one labeled as the @sc{car},
-and the other labeled as the @sc{cdr}. These names are traditional; see
-@ref{Cons Cell Type}. @sc{cdr} is pronounced ``could-er.''
-
- A list is a series of cons cells chained together, one cons cell per
-element of the list. By convention, the @sc{car}s of the cons cells are
-the elements of the list, and the @sc{cdr}s are used to chain the list:
-the @sc{cdr} of each cons cell is the following cons cell. The @sc{cdr}
-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
+ordered pair. That is, it has two slots, and each slot @dfn{holds}, or
+@dfn{refers 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
+@sc{cdr} slot of each cons cell refers to the following cons cell. The
+@sc{cdr} 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.
+@cindex 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
+@code{nil} 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.
+
+@cindex dotted list
+@cindex 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
+@dfn{dotted list}, since its printed representation would use
+@samp{.}. 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.
+
@cindex list structure
Because most cons cells are used as part of lists, the phrase
@dfn{list structure} has come to mean any structure made out of cons
cells.
- The symbol @code{nil} is considered a list as well as a symbol; it is
-the list with no elements. For convenience, the symbol @code{nil} is
-considered to have @code{nil} as its @sc{cdr} (and also as its
-@sc{car}).
-
- The @sc{cdr} of any nonempty list @var{l} is a list containing all the
+ The @sc{cdr} of any nonempty true list @var{l} is a list containing all the
elements of @var{l} except the first.
-@node Lists as Boxes
-@comment node-name, next, previous, up
-@section Lists as Linked Pairs of Boxes
-@cindex box representation for lists
-@cindex lists represented as boxes
-@cindex cons cell as box
-
- A cons cell can be illustrated as a pair of boxes. The first box
-represents the @sc{car} and the second box represents the @sc{cdr}.
-Here is an illustration of the two-element list, @code{(tulip lily)},
-made from two cons cells:
-
-@example
-@group
- --------------- ---------------
-| car | cdr | | car | cdr |
-| tulip | o---------->| lily | nil |
-| | | | | |
- --------------- ---------------
-@end group
-@end example
-
- Each pair of boxes represents a cons cell. Each box ``refers to'',
-``points to'' or ``contains'' a Lisp object. (These terms are
-synonymous.) The first box, which is the @sc{car} of the first cons
-cell, contains the symbol @code{tulip}. The arrow from the @sc{cdr} of
-the first cons cell to the second cons cell indicates that the @sc{cdr}
-of the first cons cell points to the second cons cell.
-
- The same list can be illustrated in a different sort of box notation
-like this:
-
-@example
-@group
- ___ ___ ___ ___
- |___|___|--> |___|___|--> nil
- | |
- | |
- --> tulip --> lily
-@end group
-@end example
-
- Here is a more complex illustration, showing the three-element list,
-@code{((pine needles) oak maple)}, the first element of which is a
-two-element list:
-
-@example
-@group
- ___ ___ ___ ___ ___ ___
- |___|___|--> |___|___|--> |___|___|--> nil
- | | |
- | | |
- | --> oak --> maple
- |
- | ___ ___ ___ ___
- --> |___|___|--> |___|___|--> nil
- | |
- | |
- --> pine --> needles
-@end group
-@end example
-
- The same list represented in the first box notation looks like this:
-
-@example
-@group
- -------------- -------------- --------------
-| car | cdr | | car | cdr | | car | cdr |
-| o | o------->| oak | o------->| maple | nil |
-| | | | | | | | | |
- -- | --------- -------------- --------------
- |
- |
- | -------------- ----------------
- | | car | cdr | | car | cdr |
- ------>| pine | o------->| needles | nil |
- | | | | | |
- -------------- ----------------
-@end group
-@end example
-
@xref{Cons Cell Type}, for the read and print syntax of cons cells and
-lists, and for more ``box and arrow'' illustrations of lists.
+lists, and for ``box and arrow'' illustrations of lists.
@node List-related Predicates
@section Predicates on Lists
- The following predicates test whether a Lisp object is an atom, 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.)
+ 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.)
@defun consp object
This function returns @code{t} if @var{object} is a cons cell, @code{nil}
@cindex list elements
@defun car cons-cell
-This function returns the value pointed to by the first pointer of the
+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}.
@end defun
@defun cdr cons-cell
-This function returns the value pointed to by the second pointer of
+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}.
@end example
@end defun
+@tindex pop
+@defmac 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.
+
+@example
+x
+ @result{} (a b c)
+(pop x)
+ @result{} a
+x
+ @result{} (b c)
+@end example
+@end defmac
+
@defun nth n list
+@anchor{Definition 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,
(nth n x) @equiv{} (car (nthcdr n x))
@end group
@end 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.
+@xref{Sequence Functions}.
@end defun
@defun nthcdr n list
This function returns the @var{n}th @sc{cdr} of @var{list}. In other
-words, it removes the first @var{n} links of @var{list} and returns
+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
@end example
@end defun
+@defun 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,
+@code{nil} is returned. If @var{n} is non-@code{nil}, the
+@var{n}th-to-last link is returned instead, or the whole of @var{list}
+if @var{n} is bigger than @var{list}'s length.
+@end defun
+
+@defun safe-length list
+@anchor{Definition 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.
+@end 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}.
+
+@defun caar cons-cell
+This is the same as @code{(car (car @var{cons-cell}))}.
+@end defun
+
+@defun cadr cons-cell
+This is the same as @code{(car (cdr @var{cons-cell}))}
+or @code{(nth 1 @var{cons-cell})}.
+@end defun
+
+@defun cdar cons-cell
+This is the same as @code{(cdr (car @var{cons-cell}))}.
+@end defun
+
+@defun cddr cons-cell
+This is the same as @code{(cdr (cdr @var{cons-cell}))}
+or @code{(nthcdr 2 @var{cons-cell})}.
+@end defun
+
+@defun 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}.
+@end defun
+
+@defun 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.
+@end defun
+
@node Building Lists
@comment node-name, next, previous, up
@section Building Cons Cells and Lists
code for Emacs than @code{cons}.
@defun cons object1 object2
-This function is the fundamental function used to build new list
+This function is the most basic function for building new list
structure. It creates a new cons cell, making @var{object1} the
-@sc{car}, 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.
+@sc{car}, 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.
@example
@group
@cindex consing
@code{cons} is often used to add a single element to the front of a
-list. This is called @dfn{consing the element onto the list}. For
-example:
+list. This is called @dfn{consing the element onto the list}.
+@footnote{There is no strictly equivalent way to add an element to
+the end of a list. You can use @code{(append @var{listname} (list
+@var{newelt}))}, which creates a whole new list by copying @var{listname}
+and adding @var{newelt} to its end. Or you can use @code{(nconc
+@var{listname} (list @var{newelt}))}, which modifies @var{listname}
+by following all the @sc{cdr}s and then replacing the terminating
+@code{nil}. Compare this to adding an element to the beginning of a
+list with @code{cons}, which neither copies nor modifies the list.}
+For example:
@example
(setq list (cons newelt list))
any symbol can serve both purposes.
@end defun
+@tindex push
+@defmac push newelt listname
+This macro provides an alternative way to write
+@code{(setq @var{listname} (cons @var{newelt} @var{listname}))}.
+
+@example
+(setq l '(a b))
+ @result{} (a b)
+(push 'c l)
+ @result{} (c a b)
+l
+ @result{} (c a b)
+@end example
+@end defmac
+
@defun 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}
@end defun
@defun make-list length object
-This function creates a list of length @var{length}, in which all the
-elements have the identical value @var{object}. Compare
-@code{make-list} with @code{make-string} (@pxref{Creating Strings}).
+This function creates a list of @var{length} elements, in which each
+element is @var{object}. Compare @code{make-list} with
+@code{make-string} (@pxref{Creating Strings}).
@example
@group
(make-list 0 'pigs)
@result{} nil
@end group
+@group
+(setq l (make-list 3 '(a b))
+ @result{} ((a b) (a b) (a b))
+(eq (car l) (cadr l))
+ @result{} t
+@end group
@end example
@end defun
@defun append &rest sequences
@cindex copying lists
This function returns a list containing all the elements of
-@var{sequences}. The @var{sequences} may be lists, vectors, or strings,
-but the last one should be a list. All arguments except the last one
-are copied, so none of them are altered.
+@var{sequences}. 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
@sc{cdr} 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
+dotted list since its final @sc{cdr} is not @code{nil} as required
in a true list.
-See @code{nconc} in @ref{Rearrangement}, for a way to join lists with no
-copying.
+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}).
+@end defun
-Here is an example of using @code{append}:
+ Here is an example of using @code{append}:
@example
@group
@end group
@end example
-You can see how @code{append} works by looking at a box diagram. The
+ 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
@group
more-trees trees
| |
-| ___ ___ ___ ___ -> ___ ___ ___ ___
- --> |___|___|--> |___|___|--> |___|___|--> |___|___|--> nil
+| --- --- --- --- -> --- --- --- ---
+ --> | | |--> | | |--> | | |--> | | |--> nil
+ --- --- --- --- --- --- --- ---
| | | |
| | | |
--> maple -->birch --> pine --> oak
@end group
@end smallexample
-An empty sequence contributes nothing to the value returned by
+ An empty sequence contributes nothing to the value returned by
@code{append}. As a consequence of this, a final @code{nil} argument
-forces a copy of the previous argument.
+forces a copy of the previous argument:
@example
@group
@result{} (pine oak)
@end group
@group
-(setq wood (append trees ()))
+(setq wood (append trees nil))
@result{} (pine oak)
@end group
@group
This once was the usual way to copy a list, before the function
@code{copy-sequence} was invented. @xref{Sequences Arrays Vectors}.
-With the help of @code{apply}, we can append all the lists in a list of
-lists:
+ Here we show the use of vectors and strings as arguments to @code{append}:
+
+@example
+@group
+(append [a b] "cd" nil)
+ @result{} (a b 99 100)
+@end group
+@end example
+
+ With the help of @code{apply} (@pxref{Calling Functions}), we can append
+all the lists in a list of lists:
@example
@group
@end group
@end example
-If no @var{sequences} are given, @code{nil} is returned:
+ If no @var{sequences} are given, @code{nil} is returned:
@example
@group
@end group
@end example
-Here are some examples where the final argument is not a list:
+ Here are some examples where the final argument is not a list:
@example
(append '(x y) 'z)
resulting list. Instead, the sequence becomes the final @sc{cdr}, like
any other non-list final argument.
-The @code{append} function also allows integers as arguments. It
-converts them to strings of digits, making up the decimal print
-representation of the integer, and then uses the strings instead of the
-original integers. @strong{Don't use this feature; we plan to eliminate
-it. If you already use this feature, change your programs now!} 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}).
-@end defun
-
@defun reverse list
This function creates a new list whose elements are the elements of
@var{list}, but in reverse order. The original argument @var{list} is
@end example
@end defun
+@defun 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
+@sc{cdr}, then recursively copies the @sc{car} and @sc{cdr} in the
+same way.
+
+Normally, when @var{tree} is anything other than a cons cell,
+@code{copy-tree} simply returns @var{tree}. However, if @var{vecp} is
+non-@code{nil}, it copies vectors too (and operates recursively on
+their elements).
+@end defun
+
+@defun 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
+@var{to}. @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
+@var{from} 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
+@code{(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:
+
+@example
+(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)
+@end example
+@end defun
+
@node Modifying Lists
@section Modifying Existing List Structure
+@cindex 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}.
+primitives @code{setcar} and @code{setcdr}. We call these ``destructive''
+operations because they change existing list structure.
-@cindex CL note---@code{rplaca} vrs @code{setcar}
+@cindex CL note---@code{rplaca} vs @code{setcar}
@quotation
@findex rplaca
@findex rplacd
@defun setcar cons object
This function stores @var{object} as the new @sc{car} of @var{cons},
-replacing its previous @sc{car}. It returns the value @var{object}.
-For example:
+replacing its previous @sc{car}. In other words, it changes the
+@sc{car} slot of @var{cons} to refer to @var{object}. It returns the
+value @var{object}. For example:
@example
@group
@example
@group
- ___ ___ ___ ___ ___ ___
-x1---> |___|___|----> |___|___|--> |___|___|--> nil
+ --- --- --- --- --- ---
+x1---> | | |----> | | |--> | | |--> nil
+ --- --- --- --- --- ---
| --> | |
| | | |
--> a | --> b --> c
|
- ___ ___ |
-x2--> |___|___|--
+ --- --- |
+x2--> | | |--
+ --- ---
|
|
--> z
@defun setcdr cons object
This function stores @var{object} as the new @sc{cdr} of @var{cons},
-replacing its previous @sc{cdr}. It returns the value @var{object}.
+replacing its previous @sc{cdr}. In other words, it changes the
+@sc{cdr} slot of @var{cons} to refer to @var{object}. It returns the
+value @var{object}.
@end defun
Here is an example of replacing the @sc{cdr} of a list with a
You can delete elements from the middle of a list by altering the
@sc{cdr}s 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 cell:
+the @sc{cdr} of the first cons cell:
@example
@group
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, to produce a new list that is the returned value.
+to them as arguments, relinking their cons cells to form a new list that
+is the returned value.
-@ifinfo
+@ifnottex
See @code{delq}, in @ref{Sets And Lists}, for another function
that modifies cons cells.
-@end ifinfo
+@end ifnottex
@iftex
The function @code{delq} in the following section is another example
of destructive list manipulation.
@end group
@end 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:
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 cell of the
+used to be the last one in @var{list} becomes the first cons cell of the
value.
For example:
@example
@group
-(setq x '(1 2 3 4))
- @result{} (1 2 3 4)
+(setq x '(a b c))
+ @result{} (a b c)
@end group
@group
x
- @result{} (1 2 3 4)
+ @result{} (a b c)
(nreverse x)
- @result{} (4 3 2 1)
+ @result{} (c b a)
@end group
@group
-;; @r{The cell that was first is now last.}
+;; @r{The cons cell that was first is now last.}
x
- @result{} (1)
+ @result{} (a)
@end group
@end example
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 @code{t} if the
+increasing order sort, the @var{predicate} should return non-@code{nil} 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
+@code{sort}. 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
+@dfn{transitive}---that 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
@end example
@noindent
-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:
+@strong{Warning}: 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:
@example
(setq nums (sort nums '<))
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). Other useful
+long as you don't mind having duplicate elements). You can remove
+@code{equal} duplicates using @code{delete-dups}. Other useful
functions for sets include @code{memq} and @code{delq}, and their
@code{equal} versions, @code{member} and @code{delete}.
-@cindex CL note---lack @code{union}, @code{set}
+@cindex CL note---lack @code{union}, @code{intersection}
@quotation
@b{Common Lisp note:} Common Lisp has functions @code{union} (which
avoids duplicate elements) and @code{intersection} for set operations,
This function destructively removes all elements @code{eq} to
@var{object} 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}.
+the list, like @code{memq} and @code{remq}.
@end defun
When @code{delq} deletes elements from the front of the list, it does so
@end group
@end example
-The following two functions are like @code{memq} and @code{delq} but use
-@code{equal} rather than @code{eq} to compare elements. They are new in
-Emacs 19.
+@defun 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}.
+
+@example
+@group
+(setq sample-list '(a b c a b c))
+ @result{} (a b c a b c)
+@end group
+@group
+(remq 'a sample-list)
+ @result{} (b c b c)
+@end group
+@group
+sample-list
+ @result{} (a b c a b c)
+@end group
+@end example
+@noindent
+The function @code{delq} offers a way to perform this operation
+destructively. See @ref{Sets And Lists}.
+@end defun
+
+The following three functions are like @code{memq}, @code{delq} and
+@code{remq}, but use @code{equal} rather than @code{eq} to compare
+elements. @xref{Equality Predicates}.
@defun member object list
The function @code{member} tests to see whether @var{object} is a member
@end example
@end defun
-@defun delete object list
-This function destructively removes all elements @code{equal} to
-@var{object} from @var{list}. It is to @code{delq} as @code{member} is
-to @code{memq}: it uses @code{equal} to compare elements with
-@var{object}, like @code{member}; when it finds an element that matches,
-it removes the element just as @code{delq} would. For example:
+@defun 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,
+@code{delete} is to @code{delq} as @code{member} is to @code{memq}: it
+uses @code{equal} to compare elements with @var{object}, like
+@code{member}; when it finds an element that matches, it removes the
+element 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:
@example
@group
(delete '(2) '((2) (1) (2)))
- @result{} '((1))
+ @result{} ((1))
+@end group
+@group
+(delete '(2) [(2) (1) (2)])
+ @result{} [(1)]
+@end group
+@end example
+@end defun
+
+@defun remove object sequence
+This function is the non-destructive counterpart of @code{delete}. If
+returns a copy of @code{sequence}, a list, vector, or string, with
+elements @code{equal} to @code{object} removed. For example:
+
+@example
+@group
+(remove '(2) '((2) (1) (2)))
+ @result{} ((1))
+@end group
+@group
+(remove '(2) [(2) (1) (2)])
+ @result{} [(1)]
@end group
@end example
@end defun
@quotation
-@b{Common Lisp note:} The functions @code{member} and @code{delete} in
-GNU Emacs Lisp are derived from Maclisp, not Common Lisp. The Common
-Lisp versions do not use @code{equal} to compare elements.
+@b{Common Lisp note:} The functions @code{member}, @code{delete} and
+@code{remove} in GNU Emacs Lisp are derived from Maclisp, not Common
+Lisp. The Common Lisp versions do not use @code{equal} to compare
+elements.
@end quotation
+@defun 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.
+@end defun
+
+@defun delete-dups list
+This function destructively removes all @code{equal} duplicates from
+@var{list}, stores the result in @var{list} and returns it. Of
+several @code{equal} occurrences of an element in @var{list},
+@code{delete-dups} keeps the first one.
+@end defun
+
See also the function @code{add-to-list}, in @ref{Setting Variables},
for another way to add an element to a list stored in a variable.
An @dfn{association list}, or @dfn{alist} for short, records a mapping
from keys to values. It is a list of cons cells called
-@dfn{associations}: the @sc{car} of each cell is the @dfn{key}, and the
+@dfn{associations}: the @sc{car} of each cons cell is the @dfn{key}, and the
@sc{cdr} is the @dfn{associated value}.@footnote{This 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
@example
@group
-'((pine . cones)
- (oak . acorns)
- (maple . seeds))
+((pine . cones)
+ (oak . acorns)
+ (maple . seeds))
@end group
@end 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:
+example of such an alist:
@example
-'((rose red) (lily white) (buttercup yellow))
+((rose red) (lily white) (buttercup yellow))
@end example
@noindent
Here we regard @code{red} as the value associated with @code{rose}. One
-advantage of this method is that you can store other related
+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
@sc{cdr}. One disadvantage is that you cannot use @code{rassq} (see
below) to find the element containing a given value. When neither of
@end smallexample
@end defun
+ The function @code{assoc-string} is much like @code{assoc} except
+that it ignores certain differences between strings. @xref{Text
+Comparison}.
+
@defun rassoc value alist
This function returns the first association with value @var{value} in
@var{alist}. It returns @code{nil} if no association in @var{alist} has
@end smallexample
@end defun
+@defun 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
+@var{test} with two arguments: the element or its @sc{car}, and
+@var{key}. 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
+@code{nil}.
+@end defun
+
@defun copy-alist alist
@cindex copying alists
This function returns a two-level deep copy of @var{alist}: it creates a
@end smallexample
@end defun
+@defun assq-delete-all key alist
+@tindex assq-delete-all
+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}.
+
+@example
+(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))
+@end example
+@end defun
+
+@defun 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}.
+@code{rassq-delete-all} is like @code{assq-delete-all} except that it
+compares the @sc{cdr} of each @var{alist} association instead of the
+@sc{car}.
+@end defun
+
+@node Rings
+@section Managing a Fixed-Size Ring of Objects
+
+@cindex ring data structure
+ This section describes functions for operating on rings. A
+@dfn{ring} is a fixed-size data structure that supports insertion,
+deletion, rotation, and modulo-indexed reference and traversal.
+
+@defun make-ring size
+This returns a new ring capable of holding @var{size} objects.
+@var{size} should be an integer.
+@end defun
+
+@defun ring-p object
+This returns @code{t} if @var{object} is a ring, @code{nil} otherwise.
+@end defun
+
+@defun ring-size ring
+This returns the maximum capacity of the @var{ring}.
+@end defun
+
+@defun 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}.
+@end defun
+
+@defun ring-elements ring
+This returns a list of the objects in @var{ring}, in order, newest first.
+@end defun
+
+@defun 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}.
+@end defun
+
+@defun ring-empty-p ring
+This returns @code{t} if @var{ring} is empty, @code{nil} otherwise.
+@end 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.
+
+@defun ring-ref ring index
+This returns the object in @var{ring} found at index @var{index}.
+@var{index} may be negative or greater than the ring length. If
+@var{ring} is empty, @code{ring-ref} signals an error.
+@end defun
+
+@defun 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.
+@end defun
+
+@defun 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
+@code{nil}, that means to remove the oldest item. If @var{ring} is
+empty, @code{ring-remove} signals an error.
+@end defun
+
+@defun 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.
+@end defun
+@cindex 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:
+
+@lisp
+(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")
+@end lisp
+
+@ignore
+ arch-tag: 31fb8a4e-4aa8-4a74-a206-aa00451394d4
+@end ignore