@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, 2001,
+@c 2002, 2003, 2004, 2005, 2006, 2007 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
@chapter Lists
-@cindex list
+@cindex lists
@cindex element (of list)
A @dfn{list} represents a sequence of zero or more elements (which may
@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
@section Lists and Cons Cells
@cindex lists and cons cells
-@cindex @code{nil} and lists
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
@dfn{list structure} has come to mean any structure made out of cons
cells.
- 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 defun
@defun atom object
-@cindex atoms
This function returns @code{t} if @var{object} is an atom, @code{nil}
otherwise. All objects except cons cells are atoms. The symbol
@code{nil} is an atom and is also a list; it is the only Lisp object
@end example
@end defun
-@need 2000
@node List Elements
@section Accessing Elements of Lists
@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
+@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,
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
@end group
@end example
-@need 4000
Here is the result in box notation:
-@example
+@smallexample
@group
--------------------
| |
| | | | | | | | |
-------------- -------------- --------------
@end group
-@end example
+@end smallexample
@noindent
The second cons cell, which previously held the element @code{b}, still
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
@end defun
@defun delq object list
-@cindex deletion of elements
+@cindex deleting list elements
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
(delq '(4) sample-list)
@result{} (a c (4))
@end group
+
+If you want to delete elements that are @code{equal} to a given value,
+use @code{delete} (see below).
@end example
@defun remq object 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
+
+@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
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.
+@code{member}; 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}
@example
@group
-(delete '(2) '((2) (1) (2)))
+(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))}.}
+@end group
+@group
+(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.}
@end group
@group
(delete '(2) [(2) (1) (2)])
@end defun
@defun remove object sequence
-This function is the non-destructive counterpart of @code{delete}. If
+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:
@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.
+ See also the function @code{add-to-list}, in @ref{List Variables},
+for a way to an element to a list stored in a variable and used as a
+set.
@node Association Lists
@section 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)}.
@defun assoc key alist
This function returns the first association for @var{key} in
-@var{alist}. It compares @var{key} against the alist elements using
+@var{alist}, comparing @var{key} against the alist elements using
@code{equal} (@pxref{Equality Predicates}). It returns @code{nil} if no
association in @var{alist} has a @sc{car} @code{equal} to @var{key}.
For example:
@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