@c -*-texinfo-*-
@c This is part of the GNU Emacs Lisp Reference Manual.
-@c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998, 1999
-@c 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.
+* 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.
@end menu
@node Cons Cells
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 ``holds'' a Lisp object. (These terms are
-synonymous.) The first box, which describes the @sc{car} of the first
-cons cell, contains the symbol @code{tulip}. The arrow from the
-@sc{cdr} box of the first cons cell to the second cons cell indicates
-that the @sc{cdr} of the first cons cell is 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}
@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 is new in Emacs 21.
+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}
@end example
@end defmac
-@anchor{Definition of nth}
@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,
if @var{n} is bigger than @var{list}'s length.
@end defun
-@anchor{Definition of safe-length}
@defun safe-length list
-This function returns the length of @var{list}, with no risk
-of either an error or an infinite loop.
+@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 really a list, @code{safe-length} returns 0. If
-@var{list} is circular, it returns a finite value which is at least the
-number of distinct elements.
+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
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}))}.
-It is new in Emacs 21.
-
-@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}
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 one element list @code{(from)} is returned. If @var{separation}
-is 0 and @var{to} is neither @code{nil} nor numerically equal to
-@var{from}, an error is signaled.
+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
@end example
@end defun
+@node List Variables
+@section Modifying List Variables
+
+ These functions, and one macro, provide convenient ways
+to modify a list which is stored in a variable.
+
+@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
+
+ Two functions modify lists that are the values of variables.
+
+@defun 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.
+@code{add-to-list} 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
+@var{symbol}, but if the optional argument @var{append} is
+non-@code{nil}, 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.
+@end defun
+
+Here's a scenario showing how to use @code{add-to-list}:
+
+@example
+(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 ;; @r{@code{foo} was changed.}
+ @result{} (c a b)
+@end example
+
+ An equivalent expression for @code{(add-to-list '@var{var}
+@var{value})} is this:
+
+@example
+(or (member @var{value} @var{var})
+ (setq @var{var} (cons @var{value} @var{var})))
+@end example
+
+@defun add-to-ordered-list symbol element &optional order
+This function sets the variable @var{symbol} by inserting
+@var{element} 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.
+
+@var{order} may also be omitted or @code{nil}. Then the numeric order
+of @var{element} stays unchanged if it already has one; otherwise,
+@var{element} 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;
+@code{add-to-ordered-list} 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
+@code{list-order} property.
+@end defun
+
+Here's a scenario showing how to use @code{add-to-ordered-list}:
+
+@example
+(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 ;; @r{@code{foo} was changed.}
+ @result{} (a c b e d)
+@end example
+
@node Modifying Lists
@section Modifying Existing List Structure
@cindex destructive list operations
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
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
destructively. See @ref{Sets And Lists}.
@end defun
+@defun 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}:
+
+@example
+@group
+(memql 1.2 '(1.1 1.2 1.3)) ; @r{@code{1.2} and @code{1.2} are @code{eql}.}
+ @result{} (1.2 1.3)
+@end group
+@group
+(memq 1.2 '(1.1 1.2 1.3)) ; @r{@code{1.2} and @code{1.2} are not @code{eq}.}
+ @result{} nil
+@end group
+@end example
+@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}.
@code{delete-dups} keeps the first one.
@end defun
- See also the function @code{add-to-list}, in @ref{Setting Variables},
+ See also the function @code{add-to-list}, in @ref{List Variables},
for another way to add an element to a list stored in a variable.
@node Association Lists
@end group
@end example
- The associated values in an alist may be any Lisp objects; so may the
-keys. For example, in the following alist, the symbol @code{a} is
+ 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:
these considerations is important, the choice is a matter of taste, as
long as you are consistent about it for any given alist.
- Note that the same alist shown above could be regarded as having the
+ 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)}.
@code{rassoc} 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.
+this as ``reverse @code{assoc},'' finding the key for a given value.
@end defun
@defun assq key alist
@code{rassq} 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.
+this as ``reverse @code{assq},'' finding the key for a given value.
For example:
@result{} nil
@end smallexample
-Note that @code{rassq} cannot search for a value stored in the @sc{car}
+@code{rassq} cannot search for a value stored in the @sc{car}
of the @sc{cdr} of an element:
@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
@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