X-Git-Url: https://code.delx.au/gnu-emacs/blobdiff_plain/b28c06e83b26294f2ca7cd9079323c69114aad37..dacbc44ca3fc825c9e5ffa799f1a0937c1da0020:/doc/lispref/lists.texi diff --git a/doc/lispref/lists.texi b/doc/lispref/lists.texi index d27c609dc8..14601de181 100644 --- a/doc/lispref/lists.texi +++ b/doc/lispref/lists.texi @@ -1,9 +1,9 @@ @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) @@ -23,7 +23,7 @@ the whole 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 @@ -31,61 +31,56 @@ the whole list. @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 @@ -94,7 +89,7 @@ lists, and for ``box and arrow'' illustrations of 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} @@ -241,13 +236,15 @@ This is in contrast to @code{cdr}, which signals an error if @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 @@ -257,6 +254,13 @@ 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 @@ -372,7 +376,6 @@ making a copy of the list. @end defun @node Building Lists -@comment node-name, next, previous, up @section Building Cons Cells and Lists @cindex cons cells @cindex building lists @@ -462,7 +465,7 @@ element is @var{object}. Compare @code{make-list} with @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 @@ -683,9 +686,12 @@ Some examples: 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)) @@ -695,6 +701,14 @@ This macro provides an alternative way to write 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. @@ -762,8 +776,7 @@ 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. +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. @@ -1267,8 +1280,9 @@ functions for sets include @code{memq} and @code{delq}, and their @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 @@ -1294,14 +1308,19 @@ compare @var{object} against the elements of the list. For example: @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 @@ -1309,6 +1328,7 @@ after those elements: @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}). @@ -1355,10 +1375,10 @@ and the @code{(4)} in the @code{sample-list} are not @code{eq}: (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 @@ -1433,12 +1453,15 @@ Compare this with @code{memq}: @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} @@ -1454,7 +1477,7 @@ For example: 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))) @@ -1631,7 +1654,7 @@ a @sc{cdr} @code{equal} to @var{value}. @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 @@ -1672,7 +1695,7 @@ a @sc{cdr} @code{eq} to @var{value}. @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: @@ -1801,89 +1824,133 @@ 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 +@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