@c -*-texinfo-*-
@c This is part of the GNU Emacs Lisp Reference Manual.
-@c Copyright (C) 1990-1995, 1998-1999, 2001-2011 Free Software Foundation, Inc.
+@c Copyright (C) 1990-1995, 1998-1999, 2001-2013 Free Software
+@c Foundation, Inc.
@c See the file elisp.texi for copying conditions.
-@setfilename ../../info/lists
-@node Lists, Sequences Arrays Vectors, Strings and Characters, Top
+@node Lists
@chapter Lists
@cindex lists
@cindex element (of list)
* 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.
+* Property Lists:: A list of paired elements.
@end menu
@node Cons Cells
@cindex lists and 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. 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.''
+@dfn{cons cells} (@pxref{Cons Cell Type}). A cons cell is a data
+object that represents an 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.
+ 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
+(this asymmetry between @sc{car} and @sc{cdr} is entirely a matter of
+convention; at the level of cons cells, the @sc{car} and @sc{cdr}
+slots have similar properties). Hence, the @sc{cdr} slot of each cons
+cell in a list refers to the following cons cell.
@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
+ Also by convention, the @sc{cdr} of the last cons cell in a list is
+@code{nil}. We call such a @code{nil}-terminated structure a
+@dfn{true list}. In Emacs Lisp, the symbol @code{nil} is both a
+symbol and a 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.
+as its @sc{car}).
+
+ Hence, the @sc{cdr} of a true list is always a true list. The
+@sc{cdr} of a nonempty true list is a true list containing all the
+elements except the first.
@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}.
+ If the @sc{cdr} of a list's last cons cell is some value other than
+@code{nil}, we call the structure a @dfn{dotted list}, since its
+printed representation would use dotted pair notation (@pxref{Dotted
+Pair Notation}). 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
+circular or dotted. If a 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 @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.
+ Because most cons cells are used as part of lists, we refer to any
+structure made out of cons cells as a @dfn{list structure}.
@node List-related Predicates
@section Predicates on Lists
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.)
+worth having them.)
@defun consp object
This function returns @code{t} if @var{object} is a cons cell, @code{nil}
@end defun
@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.
+This macro provides a convenient way to examine the @sc{car} of a
+list, and take it off the list, all at once. It operates on the list
+stored in @var{listname}. It removes the first element from the list,
+saves the @sc{cdr} into @var{listname}, then returns the removed
+element.
-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.
+In the simplest case, @var{listname} is an unquoted symbol naming a
+list; in that case, this macro is equivalent to @w{@code{(prog1
+(car listname) (setq listname (cdr listname)))}}.
@example
x
x
@result{} (b c)
@end example
+
+More generally, @var{listname} can be a generalized variable. In that
+case, this macro saves into @var{listname} using @code{setf}.
+@xref{Generalized Variables}.
+
+For the @code{push} macro, which adds an element to a list,
+@xref{List Variables}.
@end defmac
@defun nth n list
@end defun
@node Building Lists
-@comment node-name, next, previous, up
@section Building Cons Cells and Lists
@cindex cons cells
@cindex building lists
@result{} nil
@end group
@group
-(setq l (make-list 3 '(a b))
+(setq l (make-list 3 '(a b)))
@result{} ((a b) (a b) (a b))
(eq (car l) (cadr l))
@result{} t
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}))}.
+@defmac push element listname
+This macro creates a new list whose @sc{car} is @var{element} and
+whose @sc{cdr} is the list specified by @var{listname}, and saves that
+list in @var{listname}. In the simplest case, @var{listname} is an
+unquoted symbol naming a list, and this macro is equivalent
+to @w{@code{(setq @var{listname} (cons @var{element} @var{listname}))}}.
@example
(setq l '(a b))
l
@result{} (c a b)
@end example
+
+More generally, @code{listname} can be a generalized variable. In
+that case, this macro does the equivalent of @w{@code{(setf
+@var{listname} (cons @var{element} @var{listname}))}}.
+@xref{Generalized Variables}.
+
+For the @code{pop} macro, which removes the first element from a list,
+@xref{List Elements}.
@end defmac
Two functions modify lists that are the values of variables.
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.
+and unlike @code{setq}. Quote the argument yourself if necessary.
The ordering information is stored in a hash table on @var{symbol}'s
@code{list-order} property.
@quotation
@b{Common Lisp note:} Common Lisp has functions @code{union} (which
avoids duplicate elements) and @code{intersection} for set operations.
-Although standard GNU Emacs Lisp does not have them, the @file{cl}
-library provides versions. @inforef{Top, Overview, cl}.
+Although standard GNU Emacs Lisp does not have them, the @file{cl-lib}
+library provides versions.
+@xref{Lists as Sets,,, cl, Common Lisp Extensions}.
@end quotation
@defun memq object list
@defun delq object list
@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
-the list, like @code{memq} and @code{remq}.
+@var{object} from @var{list}, and returns the resulting 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}.
+
+Typically, when you invoke @code{delq}, you should use the return
+value by assigning it to the variable which held the original list.
+The reason for this is explained below.
@end 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:
+The @code{delq} function deletes elements from the front of the list
+by simply advancing down the list, and returning a sublist that starts
+after those elements. For example:
@example
@group
@end group
@end example
+@noindent
When an element to be deleted appears in the middle of the list,
removing it involves changing the @sc{cdr}s (@pxref{Setcdr}).
(delq '(4) sample-list)
@result{} (a c (4))
@end group
+@end example
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
This function returns a copy of @var{list}, with all elements removed
@end defun
@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 cuts the
-element out just as @code{delq} would.
+This function removes all elements @code{equal} to @var{object} from
+@var{sequence}, and returns the resulting sequence.
+
+If @var{sequence} is a list, @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 cuts the element out just as @code{delq}
+would. As with @code{delq}, you should typically use the return value
+by assigning it to the variable which held the original list.
If @code{sequence} is a vector or string, @code{delete} returns a copy
of @code{sequence} with all elements @code{equal} to @code{object}
l
@result{} ((2) (1))
;; @r{If you want to change @code{l} reliably,}
-;; @r{write @code{(setq l (delete elt l))}.}
+;; @r{write @code{(setq l (delete '(2) l))}.}
@end group
@group
(setq l '((2) (1) (2)))
@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:
@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
+@node Property Lists
+@section Property Lists
+@cindex property list
+@cindex plist
-@defun ring-p object
-This returns @code{t} if @var{object} is a ring, @code{nil} otherwise.
-@end defun
+ A @dfn{property list} (@dfn{plist} for short) is a list of paired
+elements. Each of the pairs associates a property name (usually a
+symbol) with a property or value. Here is an example of a property
+list:
-@defun ring-size ring
-This returns the maximum capacity of the @var{ring}.
-@end defun
+@example
+(pine cones numbers (1 2 3) color "blue")
+@end example
-@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
+@noindent
+This property list associates @code{pine} with @code{cones},
+@code{numbers} with @code{(1 2 3)}, and @code{color} with
+@code{"blue"}. The property names and values can be any Lisp objects,
+but the names are usually symbols (as they are in this example).
+
+ Property lists are used in several contexts. For instance, the
+function @code{put-text-property} takes an argument which is a
+property list, specifying text properties and associated values which
+are to be applied to text in a string or buffer. @xref{Text
+Properties}.
+
+ Another prominent use of property lists is for storing symbol
+properties. Every symbol possesses a list of properties, used to
+record miscellaneous information about the symbol; these properties
+are stored in the form of a property list. @xref{Symbol Properties}.
-@defun ring-elements ring
-This returns a list of the objects in @var{ring}, in order, newest first.
-@end defun
+@menu
+* Plists and Alists:: Comparison of the advantages of property
+ lists and association lists.
+* Plist Access:: Accessing property lists stored elsewhere.
+@end menu
-@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
+@node Plists and Alists
+@subsection Property Lists and Association Lists
+@cindex plist vs. alist
+@cindex alist vs. plist
+
+@cindex property lists vs association lists
+ Association lists (@pxref{Association Lists}) are very similar to
+property lists. In contrast to association lists, the order of the
+pairs in the property list is not significant, since the property
+names must be distinct.
+
+ Property lists are better than association lists for attaching
+information to various Lisp function names or variables. If your
+program keeps all such information in one association list, it will
+typically need to search that entire list each time it checks for an
+association for a particular Lisp function name or variable, which
+could be slow. By contrast, if you keep the same information in the
+property lists of the function names or variables themselves, each
+search will scan only the length of one property list, which is
+usually short. This is why the documentation for a variable is
+recorded in a property named @code{variable-documentation}. The byte
+compiler likewise uses properties to record those functions needing
+special treatment.
+
+ However, association lists have their own advantages. Depending on
+your application, it may be faster to add an association to the front of
+an association list than to update a property. All properties for a
+symbol are stored in the same property list, so there is a possibility
+of a conflict between different uses of a property name. (For this
+reason, it is a good idea to choose property names that are probably
+unique, such as by beginning the property name with the program's usual
+name-prefix for variables and functions.) An association list may be
+used like a stack where associations are pushed on the front of the list
+and later discarded; this is not possible with a property list.
+
+@node Plist Access
+@subsection Property Lists Outside Symbols
+
+ The following functions can be used to manipulate property lists.
+They all compare property names using @code{eq}.
+
+@defun plist-get plist property
+This returns the value of the @var{property} property stored in the
+property list @var{plist}. It accepts a malformed @var{plist}
+argument. If @var{property} is not found in the @var{plist}, it
+returns @code{nil}. For example,
-@defun ring-empty-p ring
-This returns @code{t} if @var{ring} is empty, @code{nil} otherwise.
+@example
+(plist-get '(foo 4) 'foo)
+ @result{} 4
+(plist-get '(foo 4 bad) 'foo)
+ @result{} 4
+(plist-get '(foo 4 bad) 'bad)
+ @result{} nil
+(plist-get '(foo 4 bad) 'bar)
+ @result{} nil
+@end example
@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 plist-put plist property value
+This stores @var{value} as the value of the @var{property} property in
+the property list @var{plist}. It may modify @var{plist} destructively,
+or it may construct a new list structure without altering the old. The
+function returns the modified property list, so you can store that back
+in the place where you got @var{plist}. For example,
-@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.
+@example
+(setq my-plist '(bar t foo 4))
+ @result{} (bar t foo 4)
+(setq my-plist (plist-put my-plist 'foo 69))
+ @result{} (bar t foo 69)
+(setq my-plist (plist-put my-plist 'quux '(a)))
+ @result{} (bar t foo 69 quux (a))
+@end example
@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.
+@defun lax-plist-get plist property
+Like @code{plist-get} except that it compares properties
+using @code{equal} instead of @code{eq}.
@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.
+@defun lax-plist-put plist property value
+Like @code{plist-put} except that it compares properties
+using @code{equal} instead of @code{eq}.
@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.
+@defun plist-member plist property
+This returns non-@code{nil} if @var{plist} contains the given
+@var{property}. Unlike @code{plist-get}, this allows you to distinguish
+between a missing property and a property with the value @code{nil}.
+The value is actually the tail of @var{plist} whose @code{car} is
+@var{property}.
@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