X-Git-Url: https://code.delx.au/gnu-emacs/blobdiff_plain/f9f59935f3518733b46009b9ee40132b1f330cf0..bbf6f18c1ec1b7fae1fc95114591ae0a3e425c58:/lispref/lists.texi diff --git a/lispref/lists.texi b/lispref/lists.texi index 6334b4bdcd..ca31023594 100644 --- a/lispref/lists.texi +++ b/lispref/lists.texi @@ -32,9 +32,10 @@ the whole list. 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.'' +ordered pair. It holds, or ``refers to,'' 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 @@ -81,19 +82,20 @@ made from two cons cells: @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. +``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 + --- --- --- --- + | | |--> | | |--> nil + --- --- --- --- | | | | --> tulip --> lily @@ -106,14 +108,16 @@ two-element list: @example @group - ___ ___ ___ ___ ___ ___ - |___|___|--> |___|___|--> |___|___|--> nil + --- --- --- --- --- --- + | | |--> | | |--> | | |--> nil + --- --- --- --- --- --- | | | | | | | --> oak --> maple | - | ___ ___ ___ ___ - --> |___|___|--> |___|___|--> nil + | --- --- --- --- + --> | | |--> | | |--> nil + --- --- --- --- | | | | --> pine --> needles @@ -218,7 +222,7 @@ considered a list and @code{not} when it is considered a truth value @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}. @@ -240,7 +244,7 @@ or @code{nil}. @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}. @@ -323,6 +327,10 @@ If @var{n} is negative, @code{nth} returns the first element of (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 @@ -350,8 +358,8 @@ If @var{n} is zero or negative, @code{nthcdr} returns all of @end example @end defun +@defun safe-length list @tindex safe-length -@defun safe-length sequence This function returns the length of @var{list}, with no risk of either an error or an infinite loop. @@ -360,26 +368,30 @@ If @var{list} is not really a list, @code{safe-length} returns 0. If number of distinct elements. @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 @tindex caar -@defun caar list -This is the same as @code{(car (car @var{list}))}. +This is the same as @code{(car (car @var{cons-cell}))}. @end defun +@defun cadr cons-cell @tindex cadr -@defun cadr list -This is the same as @code{(car (cdr @var{list}))} -or @code{(nth 1 @var{list})}. +This is the same as @code{(car (cdr @var{cons-cell}))} +or @code{(nth 1 @var{cons-cell})}. @end defun +@defun cdar cons-cell @tindex cdar -@defun cdar list -This is the same as @code{(cdr (car @var{list}))}. +This is the same as @code{(cdr (car @var{cons-cell}))}. @end defun +@defun cddr cons-cell @tindex cddr -@defun cddr list -This is the same as @code{(cdr (cdr @var{list}))} -or @code{(nthcdr 2 @var{list})}. +This is the same as @code{(cdr (cdr @var{cons-cell}))} +or @code{(nthcdr 2 @var{cons-cell})}. @end defun @node Building Lists @@ -470,9 +482,11 @@ elements have the identical value @var{object}. Compare @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 usually be a list. All arguments except the -last one are copied, so none of the arguments is 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 @@ -482,10 +496,17 @@ 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 in a true list. -See @code{nconc} in @ref{Rearrangement}, for a way to join lists with no -copying. +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 -Here is an example of using @code{append}: + Here is an example of using @code{append}: @example @group @@ -507,7 +528,7 @@ more-trees @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 @@ -517,17 +538,18 @@ original list: @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 @@ -535,7 +557,7 @@ trees @result{} (pine oak) @end group @group -(setq wood (append trees ())) +(setq wood (append trees nil)) @result{} (pine oak) @end group @group @@ -552,8 +574,17 @@ wood 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 @@ -562,7 +593,7 @@ lists: @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 @@ -571,7 +602,7 @@ If no @var{sequences} are given, @code{nil} is returned: @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) @@ -586,16 +617,6 @@ not a list, the sequence's elements do not become elements of the 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 @@ -617,9 +638,11 @@ x @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} @quotation @@ -648,8 +671,9 @@ different element. @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 @@ -707,14 +731,16 @@ changes them both: @example @group - ___ ___ ___ ___ ___ ___ -x1---> |___|___|----> |___|___|--> |___|___|--> nil + --- --- --- --- --- --- +x1---> | | |----> | | |--> | | |--> nil + --- --- --- --- --- --- | --> | | | | | | --> a | --> b --> c | - ___ ___ | -x2--> |___|___|-- + --- --- | +x2--> | | |-- + --- --- | | --> z @@ -748,7 +774,9 @@ x2: | @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 @@ -775,7 +803,7 @@ x 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 @@ -849,7 +877,8 @@ x1 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 See @code{delq}, in @ref{Sets And Lists}, for another function @@ -904,6 +933,8 @@ x @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: @@ -944,7 +975,7 @@ 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: @@ -961,7 +992,7 @@ x @result{} (4 3 2 1) @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) @end group @@ -1006,6 +1037,15 @@ 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 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 @@ -1157,7 +1197,8 @@ and the @code{(4)} in the @code{sample-list} are not @code{eq}: @end example The following two functions are like @code{memq} and @code{delq} but use -@code{equal} rather than @code{eq} to compare elements. +@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 @@ -1215,7 +1256,7 @@ 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 @@ -1313,6 +1354,10 @@ Here is another example, in which the keys and values are not symbols: @end smallexample @end defun + The functions @code{assoc-ignore-representation} and +@code{assoc-ignore-case} are much like @code{assoc} except using +@code{compare-strings} to do the comparison. @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 @@ -1393,6 +1438,26 @@ becomes clearer if the association is written in dotted pair notation: @end smallexample @end defun +@tindex assoc-default +@defun assoc-default key alist 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