@c -*-texinfo-*-@c This is part of the GNU Emacs Lisp Reference Manual.@c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998, 1999, 2001,@c 2002, 2003, 2004, 2005, 2006, 2007, 2008 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 lists@cindex element (of list) A @dfn{list} represents a sequence of zero or more elements (which maybe any Lisp objects). The important difference between lists andvectors is that two or more lists can share part of their structure; inaddition, you can insert or delete elements in a list without copyingthe whole list.@menu* Cons Cells:: How lists are made out of cons cells.* 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 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 anordered 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 objectits @sc{car} slot currently holds, and likewise for the @sc{cdr}. A list is a series of cons cells ``chained together,'' so that eachcell refers to the next one. There is one cons cell for each element ofthe list. By convention, the @sc{car}s of the cons cells hold theelements 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 betweenthe @sc{car} and the @sc{cdr} is entirely a matter of convention; at thelevel of cons cells, the @sc{car} and @sc{cdr} slots have the samecharacteristics.@cindex true list Since @code{nil} is the conventional value to put in the @sc{cdr} ofthe 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 asymbol; it is the list with no elements. For convenience, the symbol@code{nil} is considered to have @code{nil} as its @sc{cdr} (and alsoas its @sc{car}). Therefore, the @sc{cdr} of a true list is always atrue 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 callthat 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 thelist to see the @sc{cdr} of the final cons cell, it won't care.However, some functions that operate on lists demand true lists andsignal errors if given a dotted list. Most functions that try to findthe 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 conscells. The @sc{cdr} of any nonempty true list @var{l} is a list containing all theelements of @var{l} except the first. @xref{Cons Cell Type}, for the read and print syntax of cons cells andlists, 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,whether it is a cons cell or is a list, or whether it is thedistinguished object @code{nil}. (Many of these predicates can bedefined in terms of the others, but they are used so often that it isworth having all of them.)@defun consp objectThis function returns @code{t} if @var{object} is a cons cell, @code{nil}otherwise. @code{nil} is not a cons cell, although it @emph{is} a list.@end defun@defun atom objectThis 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 objectthat is both.@example(atom @var{object}) @equiv{} (not (consp @var{object}))@end example@end defun@defun listp objectThis function returns @code{t} if @var{object} is a cons cell or@code{nil}. Otherwise, it returns @code{nil}.@example@group(listp '(1)) @result{} t@end group@group(listp '()) @result{} t@end group@end example@end defun@defun nlistp objectThis function is the opposite of @code{listp}: it returns @code{t} if@var{object} is not a list. Otherwise, it returns @code{nil}.@example(listp @var{object}) @equiv{} (not (nlistp @var{object}))@end example@end defun@defun null objectThis function returns @code{t} if @var{object} is @code{nil}, andreturns @code{nil} otherwise. This function is identical to @code{not},but as a matter of clarity we use @code{null} when @var{object} isconsidered a list and @code{not} when it is considered a truth value(see @code{not} in @ref{Combining Conditions}).@example@group(null '(1)) @result{} nil@end group@group(null '()) @result{} t@end group@end example@end defun@node List Elements@section Accessing Elements of Lists@cindex list elements@defun car cons-cellThis function returns the value referred to by the first slot of thecons cell @var{cons-cell}. Expressed another way, this functionreturns the @sc{car} of @var{cons-cell}.As a special case, if @var{cons-cell} is @code{nil}, then @code{car}is defined to return @code{nil}; therefore, any list is a valid argumentfor @code{car}. An error is signaled if the argument is not a cons cellor @code{nil}.@example@group(car '(a b c)) @result{} a@end group@group(car '()) @result{} nil@end group@end example@end defun@defun cdr cons-cellThis function returns the value referred to by the second slot ofthe cons cell @var{cons-cell}. Expressed another way, this functionreturns the @sc{cdr} of @var{cons-cell}.As a special case, if @var{cons-cell} is @code{nil}, then @code{cdr}is defined to return @code{nil}; therefore, any list is a valid argumentfor @code{cdr}. An error is signaled if the argument is not a cons cellor @code{nil}.@example@group(cdr '(a b c)) @result{} (b c)@end group@group(cdr '()) @result{} nil@end group@end example@end defun@defun car-safe objectThis function lets you take the @sc{car} of a cons cell while avoidingerrors for other data types. It returns the @sc{car} of @var{object} if@var{object} is a cons cell, @code{nil} otherwise. This is in contrastto @code{car}, which signals an error if @var{object} is not a list.@example@group(car-safe @var{object})@equiv{}(let ((x @var{object})) (if (consp x) (car x) nil))@end group@end example@end defun@defun cdr-safe objectThis function lets you take the @sc{cdr} of a cons cell whileavoiding errors for other data types. It returns the @sc{cdr} of@var{object} if @var{object} is a cons cell, @code{nil} otherwise.This is in contrast to @code{cdr}, which signals an error if@var{object} is not a list.@example@group(cdr-safe @var{object})@equiv{}(let ((x @var{object})) (if (consp x) (cdr x) nil))@end group@end example@end defun@defmac pop listnameThis macro is a way of examining the @sc{car} of a list,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}to the @sc{cdr} of its old value---but it also returns the @sc{car}of that list, which is the element being removed.@examplex @result{} (a b c)(pop x) @result{} ax @result{} (b c)@end example@end defmac@defun nth n list@anchor{Definition of nth}This function returns the @var{n}th element of @var{list}. Elementsare numbered starting with zero, so the @sc{car} of @var{list} iselement number zero. If the length of @var{list} is @var{n} or less,the value is @code{nil}.If @var{n} is negative, @code{nth} returns the first element of@var{list}.@example@group(nth 2 '(1 2 3 4)) @result{} 3@end group@group(nth 10 '(1 2 3 4)) @result{} nil@end group@group(nth -3 '(1 2 3 4)) @result{} 1(nth n x) @equiv{} (car (nthcdr n x))@end group@end exampleThe 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 listThis function returns the @var{n}th @sc{cdr} of @var{list}. In otherwords, it skips past the first @var{n} links of @var{list} and returnswhat follows.If @var{n} is zero or negative, @code{nthcdr} returns all of@var{list}. If the length of @var{list} is @var{n} or less,@code{nthcdr} returns @code{nil}.@example@group(nthcdr 1 '(1 2 3 4)) @result{} (2 3 4)@end group@group(nthcdr 10 '(1 2 3 4)) @result{} nil@end group@group(nthcdr -3 '(1 2 3 4)) @result{} (1 2 3 4)@end group@end example@end defun@defun last list &optional nThis function returns the last link of @var{list}. The @code{car} ofthis link is the list's last element. If @var{list} is null,@code{nil} is returned. If @var{n} is non-@code{nil}, the@var{n}th-to-last link is returned instead, or the whole of @var{list}if @var{n} is bigger than @var{list}'s length.@end defun@defun safe-length list@anchor{Definition of safe-length}This function returns the length of @var{list}, with no risk of eitheran error or an infinite loop. It generally returns the number ofdistinct 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 @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 notworried that it may be circular, is with @code{length}. @xref{SequenceFunctions}.@defun caar cons-cellThis is the same as @code{(car (car @var{cons-cell}))}.@end defun@defun cadr cons-cellThis is the same as @code{(car (cdr @var{cons-cell}))}or @code{(nth 1 @var{cons-cell})}.@end defun@defun cdar cons-cellThis is the same as @code{(cdr (car @var{cons-cell}))}.@end defun@defun cddr cons-cellThis is the same as @code{(cdr (cdr @var{cons-cell}))}or @code{(nthcdr 2 @var{cons-cell})}.@end defun@defun butlast x &optional nThis function returns the list @var{x} with the last element,or the last @var{n} elements, removed. If @var{n} is greaterthan zero it makes a copy of the list so as not to damage theoriginal list. In general, @code{(append (butlast @var{x} @var{n})(last @var{x} @var{n}))} will return a list equal to @var{x}.@end defun@defun nbutlast x &optional nThis is a version of @code{butlast} that works by destructivelymodifying the @code{cdr} of the appropriate element, rather thanmaking 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 Many functions build lists, as lists reside at the very heart of Lisp.@code{cons} is the fundamental list-building function; however, it isinteresting to note that @code{list} is used more times in the sourcecode for Emacs than @code{cons}.@defun cons object1 object2This function is the most basic function for building new liststructure. It creates a new cons cell, making @var{object1} the@sc{car}, and @var{object2} the @sc{cdr}. It then returns the newcons cell. The arguments @var{object1} and @var{object2} may be anyLisp objects, but most often @var{object2} is a list.@example@group(cons 1 '(2)) @result{} (1 2)@end group@group(cons 1 '()) @result{} (1)@end group@group(cons 1 2) @result{} (1 . 2)@end group@end example@cindex consing@code{cons} is often used to add a single element to the front of alist. This is called @dfn{consing the element onto the list}.@footnote{There is no strictly equivalent way to add an element tothe end of a list. You can use @code{(append @var{listname} (list@var{newelt}))}, which creates a whole new list by copying @var{listname}and adding @var{newelt} to its end. Or you can use @code{(nconc@var{listname} (list @var{newelt}))}, which modifies @var{listname}by following all the @sc{cdr}s and then replacing the terminating@code{nil}. Compare this to adding an element to the beginning of alist with @code{cons}, which neither copies nor modifies the list.}For example:@example(setq list (cons newelt list))@end exampleNote that there is no conflict between the variable named @code{list}used in this example and the function named @code{list} described below;any symbol can serve both purposes.@end defun@defun list &rest objectsThis function creates a list with @var{objects} as its elements. Theresulting list is always @code{nil}-terminated. If no @var{objects}are given, the empty list is returned.@example@group(list 1 2 3 4 5) @result{} (1 2 3 4 5)@end group@group(list 1 2 '(3 4 5) 'foo) @result{} (1 2 (3 4 5) foo)@end group@group(list) @result{} nil@end group@end example@end defun@defun make-list length objectThis function creates a list of @var{length} elements, in which eachelement is @var{object}. Compare @code{make-list} with@code{make-string} (@pxref{Creating Strings}).@example@group(make-list 3 'pigs) @result{} (pigs pigs pigs)@end group@group(make-list 0 'pigs) @result{} nil@end group@group(setq l (make-list 3 '(a b)) @result{} ((a b) (a b) (a b))(eq (car l) (cadr l)) @result{} t@end group@end example@end defun@defun append &rest sequences@cindex copying listsThis function returns a list containing all the elements of@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 argumentsis altered. (See @code{nconc} in @ref{Rearrangement}, for a way to joinlists with no copying.)More generally, the final argument to @code{append} may be any Lispobject. The final argument is not copied or converted; it becomes the@sc{cdr} of the last cons cell in the new list. If the final argumentis itself a list, then its elements become in effect elements of theresult list. If the final element is not a list, the result is adotted list since its final @sc{cdr} is not @code{nil} as requiredin a true list.In Emacs 20 and before, the @code{append} function also allowedintegers as (non last) arguments. It converted them to strings ofdigits, making up the decimal print representation of the integer, andthen used the strings instead of the original integers. This obsoleteusage no longer works. The proper way to convert an integer to adecimal number in this way is with @code{format} (@pxref{FormattingStrings}) or @code{number-to-string} (@pxref{String Conversion}).@end defun Here is an example of using @code{append}:@example@group(setq trees '(pine oak)) @result{} (pine oak)(setq more-trees (append '(maple birch) trees)) @result{} (maple birch pine oak)@end group@grouptrees @result{} (pine oak)more-trees @result{} (maple birch pine oak)@end group@group(eq trees (cdr (cdr more-trees))) @result{} t@end group@end example You can see how @code{append} works by looking at a box diagram. Thevariable @code{trees} is set to the list @code{(pine oak)} and then thevariable @code{more-trees} is set to the list @code{(maple birch pineoak)}. However, the variable @code{trees} continues to refer to theoriginal list:@smallexample@groupmore-trees trees| || --- --- --- --- -> --- --- --- --- --> | | |--> | | |--> | | |--> | | |--> nil --- --- --- --- --- --- --- --- | | | | | | | | --> maple -->birch --> pine --> oak@end group@end smallexample An empty sequence contributes nothing to the value returned by@code{append}. As a consequence of this, a final @code{nil} argumentforces a copy of the previous argument:@example@grouptrees @result{} (pine oak)@end group@group(setq wood (append trees nil)) @result{} (pine oak)@end group@groupwood @result{} (pine oak)@end group@group(eq wood trees) @result{} nil@end group@end example@noindentThis once was the usual way to copy a list, before the function@code{copy-sequence} was invented. @xref{Sequences Arrays Vectors}. 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 appendall the lists in a list of lists:@example@group(apply 'append '((a b c) nil (x y z) nil)) @result{} (a b c x y z)@end group@end example If no @var{sequences} are given, @code{nil} is returned:@example@group(append) @result{} nil@end group@end example Here are some examples where the final argument is not a list:@example(append '(x y) 'z) @result{} (x y . z)(append '(x y) [z]) @result{} (x y . [z])@end example@noindentThe second example shows that when the final argument is a sequence butnot a list, the sequence's elements do not become elements of theresulting list. Instead, the sequence becomes the final @sc{cdr}, likeany other non-list final argument.@defun reverse listThis function creates a new list whose elements are the elements of@var{list}, but in reverse order. The original argument @var{list} is@emph{not} altered.@example@group(setq x '(1 2 3 4)) @result{} (1 2 3 4)@end group@group(reverse x) @result{} (4 3 2 1)x @result{} (1 2 3 4)@end group@end example@end defun@defun copy-tree tree &optional vecpThis function returns a copy of the tree @code{tree}. If @var{tree} is acons cell, this makes a new cons cell with the same @sc{car} and@sc{cdr}, then recursively copies the @sc{car} and @sc{cdr} in thesame way.Normally, when @var{tree} is anything other than a cons cell,@code{copy-tree} simply returns @var{tree}. However, if @var{vecp} isnon-@code{nil}, it copies vectors too (and operates recursively ontheir elements).@end defun@defun number-sequence from &optional to separationThis returns a list of numbers starting with @var{from} andincrementing by @var{separation}, and ending at or just before@var{to}. @var{separation} can be positive or negative and defaultsto 1. If @var{to} is @code{nil} or numerically equal to @var{from},the value is the one-element list @code{(@var{from})}. If @var{to} isless 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} nornumerically equal to @var{from}, @code{number-sequence} signals anerror, 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 pointarithmetic is inexact. For instance, depending on the machine, it mayquite well happen that @code{(number-sequence 0.4 0.6 0.2)} returnsthe one element list @code{(0.4)}, whereas@code{(number-sequence 0.4 0.8 0.2)} returns a list with threeelements. The @var{n}th element of the list is computed by the exactformula @code{(+ @var{from} (* @var{n} @var{separation}))}. Thus, ifone wants to make sure that @var{to} is included in the list, one canpass an expression of this exact type for @var{to}. Alternatively,one can replace @var{to} with a slightly larger value (or a slightlymore negative value if @var{separation} is negative).Some examples:@example(number-sequence 4 9) @result{} (4 5 6 7 8 9)(number-sequence 9 4 -1) @result{} (9 8 7 6 5 4)(number-sequence 9 4 -2) @result{} (9 7 5)(number-sequence 8) @result{} (8)(number-sequence 8 5) @result{} nil(number-sequence 5 8 -1) @result{} nil(number-sequence 1.5 6 2) @result{} (1.5 3.5 5.5)@end example@end defun@node List Variables@section Modifying List Variables These functions, and one macro, provide convenient waysto modify a list which is stored in a variable.@defmac push newelt listnameThis 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-fnThis function sets the variable @var{symbol} by consing @var{element}onto the old value, if @var{element} is not already a member of thatvalue. It returns the resulting list, whether updated or not. Thevalue 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}, ituses @code{equal}.Normally, if @var{element} is added, it is added to the front of@var{symbol}, but if the optional argument @var{append} isnon-@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}. Quotethe argument yourself if that is what you want.@end defunHere'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 orderThis function sets the variable @var{symbol} by inserting@var{element} into the old value, which must be a list, at theposition specified by @var{order}. If @var{element} is already amember of the list, its position in the list is adjusted accordingto @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 theelements of the list are sorted in non-decreasing numerical order.@var{order} may also be omitted or @code{nil}. Then the numeric orderof @var{element} stays unchanged if it already has one; otherwise,@var{element} has no numeric order. Elements without a numeric listorder 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 whatyou want.The ordering information is stored in a hash table on @var{symbol}'s@code{list-order} property.@end defunHere'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 You can modify the @sc{car} and @sc{cdr} contents of a cons cell with theprimitives @code{setcar} and @code{setcdr}. We call these ``destructive''operations because they change existing list structure.@cindex CL note---@code{rplaca} vs @code{setcar}@quotation@findex rplaca@findex rplacd@b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and@code{rplacd} to alter list structure; they change structure the sameway as @code{setcar} and @code{setcdr}, but the Common Lisp functionsreturn the cons cell while @code{setcar} and @code{setcdr} return thenew @sc{car} or @sc{cdr}.@end quotation@menu* Setcar:: Replacing an element in a list.* Setcdr:: Replacing part of the list backbone. This can be used to remove or add elements.* Rearrangement:: Reordering the elements in a list; combining lists.@end menu@node Setcar@subsection Altering List Elements with @code{setcar} Changing the @sc{car} of a cons cell is done with @code{setcar}. Whenused on a list, @code{setcar} replaces one element of a list with adifferent element.@defun setcar cons objectThis function stores @var{object} as the new @sc{car} of @var{cons},replacing its previous @sc{car}. In other words, it changes the@sc{car} slot of @var{cons} to refer to @var{object}. It returns thevalue @var{object}. For example:@example@group(setq x '(1 2)) @result{} (1 2)@end group@group(setcar x 4) @result{} 4@end group@groupx @result{} (4 2)@end group@end example@end defun When a cons cell is part of the shared structure of several lists,storing a new @sc{car} into the cons changes one element of each ofthese lists. Here is an example:@example@group;; @r{Create two lists that are partly shared.}(setq x1 '(a b c)) @result{} (a b c)(setq x2 (cons 'z (cdr x1))) @result{} (z b c)@end group@group;; @r{Replace the @sc{car} of a shared link.}(setcar (cdr x1) 'foo) @result{} foox1 ; @r{Both lists are changed.} @result{} (a foo c)x2 @result{} (z foo c)@end group@group;; @r{Replace the @sc{car} of a link that is not shared.}(setcar x1 'baz) @result{} bazx1 ; @r{Only one list is changed.} @result{} (baz foo c)x2 @result{} (z foo c)@end group@end example Here is a graphical depiction of the shared structure of the two listsin the variables @code{x1} and @code{x2}, showing why replacing @code{b}changes them both:@example@group --- --- --- --- --- ---x1---> | | |----> | | |--> | | |--> nil --- --- --- --- --- --- | --> | | | | | | --> a | --> b --> c | --- --- |x2--> | | |-- --- --- | | --> z@end group@end example Here is an alternative form of box diagram, showing the same relationship:@example@groupx1: -------------- -------------- --------------| car | cdr | | car | cdr | | car | cdr || a | o------->| b | o------->| c | nil || | | -->| | | | | | -------------- | -------------- -------------- |x2: | -------------- || car | cdr | || z | o----| | | --------------@end group@end example@node Setcdr@subsection Altering the CDR of a List The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}:@defun setcdr cons objectThis function stores @var{object} as the new @sc{cdr} of @var{cons},replacing its previous @sc{cdr}. In other words, it changes the@sc{cdr} slot of @var{cons} to refer to @var{object}. It returns thevalue @var{object}.@end defun Here is an example of replacing the @sc{cdr} of a list with adifferent list. All but the first element of the list are removed infavor of a different sequence of elements. The first element isunchanged, because it resides in the @sc{car} of the list, and is notreached via the @sc{cdr}.@example@group(setq x '(1 2 3)) @result{} (1 2 3)@end group@group(setcdr x '(4)) @result{} (4)@end group@groupx @result{} (1 4)@end group@end example 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 deletethe second element, @code{b}, from the list @code{(a b c)}, by changingthe @sc{cdr} of the first cons cell:@example@group(setq x1 '(a b c)) @result{} (a b c)(setcdr x1 (cdr (cdr x1))) @result{} (c)x1 @result{} (a c)@end group@end example Here is the result in box notation:@smallexample@group -------------------- | | -------------- | -------------- | --------------| car | cdr | | | car | cdr | -->| car | cdr || a | o----- | b | o-------->| c | nil || | | | | | | | | -------------- -------------- --------------@end group@end smallexample@noindentThe second cons cell, which previously held the element @code{b}, stillexists and its @sc{car} is still @code{b}, but it no longer forms partof this list. It is equally easy to insert a new element by changing @sc{cdr}s:@example@group(setq x1 '(a b c)) @result{} (a b c)(setcdr x1 (cons 'd (cdr x1))) @result{} (d b c)x1 @result{} (a d b c)@end group@end example Here is this result in box notation:@smallexample@group -------------- ------------- -------------| car | cdr | | car | cdr | | car | cdr || a | o | -->| b | o------->| c | nil || | | | | | | | | | | --------- | -- | ------------- ------------- | | ----- -------- | | | --------------- | | | car | cdr | | -->| d | o------ | | | ---------------@end group@end smallexample@node Rearrangement@subsection Functions that Rearrange Lists@cindex rearrangement of lists@cindex modification of lists Here are some functions that rearrange lists ``destructively'' bymodifying the @sc{cdr}s of their component cons cells. We call thesefunctions ``destructive'' because they chew up the original lists passedto them as arguments, relinking their cons cells to form a new list thatis the returned value.@ifnottex See @code{delq}, in @ref{Sets And Lists}, for another functionthat modifies cons cells.@end ifnottex@iftex The function @code{delq} in the following section is another exampleof destructive list manipulation.@end iftex@defun nconc &rest lists@cindex concatenating lists@cindex joining listsThis function returns a list containing all the elements of @var{lists}.Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are@emph{not} copied. Instead, the last @sc{cdr} of each of the@var{lists} is changed to refer to the following list. The last of the@var{lists} is not altered. For example:@example@group(setq x '(1 2 3)) @result{} (1 2 3)@end group@group(nconc x '(4 5)) @result{} (1 2 3 4 5)@end group@groupx @result{} (1 2 3 4 5)@end group@end example Since the last argument of @code{nconc} is not itself modified, it isreasonable to use a constant list, such as @code{'(4 5)}, as in theabove example. For the same reason, the last argument need not be alist:@example@group(setq x '(1 2 3)) @result{} (1 2 3)@end group@group(nconc x 'z) @result{} (1 2 3 . z)@end group@groupx @result{} (1 2 3 . z)@end group@end exampleHowever, the other arguments (all but the last) must be lists.A common pitfall is to use a quoted constant list as a non-lastargument to @code{nconc}. If you do this, your program will changeeach time you run it! Here is what happens:@smallexample@group(defun add-foo (x) ; @r{We want this function to add} (nconc '(foo) x)) ; @r{@code{foo} to the front of its arg.}@end group@group(symbol-function 'add-foo) @result{} (lambda (x) (nconc (quote (foo)) x))@end group@group(setq xx (add-foo '(1 2))) ; @r{It seems to work.} @result{} (foo 1 2)@end group@group(setq xy (add-foo '(3 4))) ; @r{What happened?} @result{} (foo 1 2 3 4)@end group@group(eq xx xy) @result{} t@end group@group(symbol-function 'add-foo) @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x)))@end group@end smallexample@end defun@defun nreverse list@cindex reversing a list This function reverses the order of the elements of @var{list}.Unlike @code{reverse}, @code{nreverse} alters its argument by reversingthe @sc{cdr}s in the cons cells forming the list. The cons cell thatused to be the last one in @var{list} becomes the first cons cell of thevalue. For example:@example@group(setq x '(a b c)) @result{} (a b c)@end group@groupx @result{} (a b c)(nreverse x) @result{} (c b a)@end group@group;; @r{The cons cell that was first is now last.}x @result{} (a)@end group@end example To avoid confusion, we usually store the result of @code{nreverse}back in the same variable which held the original list:@example(setq x (nreverse x))@end example Here is the @code{nreverse} of our favorite example, @code{(a b c)},presented graphically:@smallexample@group@r{Original list head:} @r{Reversed list:} ------------- ------------- ------------| car | cdr | | car | cdr | | car | cdr || a | nil |<-- | b | o |<-- | c | o || | | | | | | | | | | | | ------------- | --------- | - | -------- | - | | | | ------------- ------------@end group@end smallexample@end defun@defun sort list predicate@cindex stable sort@cindex sorting listsThis function sorts @var{list} stably, though destructively, andreturns the sorted list. It compares elements using @var{predicate}. Astable sort is one in which elements with equal sort keys maintain theirrelative order before and after the sort. Stability is important whensuccessive sorts are used to order elements according to differentcriteria.The argument @var{predicate} must be a function that accepts twoarguments. It is called with two elements of @var{list}. To get anincreasing order sort, the @var{predicate} should return non-@code{nil} if thefirst element is ``less than'' the second, or @code{nil} if not.The comparison function @var{predicate} must give reliable results forany given pair of arguments, at least within a single call to@code{sort}. It must be @dfn{antisymmetric}; that is, if @var{a} isless 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 youuse a comparison function which does not meet these requirements, theresult of @code{sort} is unpredictable.The destructive aspect of @code{sort} is that it rearranges the conscells forming @var{list} by changing @sc{cdr}s. A nondestructive sortfunction would create new cons cells to store the elements in theirsorted order. If you wish to make a sorted copy without destroying theoriginal, copy it first with @code{copy-sequence} and then sort.Sorting does not change the @sc{car}s of the cons cells in @var{list};the cons cell that originally contained the element @code{a} in@var{list} still has @code{a} in its @sc{car} after sorting, but it nowappears in a different position in the list due to the change of@sc{cdr}s. For example:@example@group(setq nums '(1 3 2 6 5 4 0)) @result{} (1 3 2 6 5 4 0)@end group@group(sort nums '<) @result{} (0 1 2 3 4 5 6)@end group@groupnums @result{} (1 2 3 4 5 6)@end group@end example@noindent@strong{Warning}: Note that the list in @code{nums} no longer contains0; this is the same cons cell that it was before, but it is no longerthe first one in the list. Don't assume a variable that formerly heldthe argument now holds the entire sorted list! Instead, save the resultof @code{sort} and use that. Most often we store the result back intothe variable that held the original list:@example(setq nums (sort nums '<))@end example@xref{Sorting}, for more functions that perform sorting.See @code{documentation} in @ref{Accessing Documentation}, for auseful example of @code{sort}.@end defun@node Sets And Lists@section Using Lists as Sets@cindex lists as sets@cindex sets A list can represent an unordered mathematical set---simply consider avalue an element of a set if it appears in the list, and ignore theorder of the list. To form the union of two sets, use @code{append} (aslong as you don't mind having duplicate elements). You can remove@code{equal} duplicates using @code{delete-dups}. Other usefulfunctions for sets include @code{memq} and @code{delq}, and their@code{equal} versions, @code{member} and @code{delete}.@cindex CL note---lack @code{union}, @code{intersection}@quotation@b{Common Lisp note:} Common Lisp has functions @code{union} (whichavoids duplicate elements) and @code{intersection} for set operations,but GNU Emacs Lisp does not have them. You can write them in Lisp ifyou wish.@end quotation@defun memq object list@cindex membership in a listThis function tests to see whether @var{object} is a member of@var{list}. If it is, @code{memq} returns a list starting with thefirst occurrence of @var{object}. Otherwise, it returns @code{nil}.The letter @samp{q} in @code{memq} says that it uses @code{eq} tocompare @var{object} against the elements of the list. For example:@example@group(memq 'b '(a b c b a)) @result{} (b c b a)@end group@group(memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.} @result{} nil@end group@end example@end defun@defun delq object list@cindex deleting list elementsThis function destructively removes all elements @code{eq} to@var{object} from @var{list}. The letter @samp{q} in @code{delq} saysthat it uses @code{eq} to compare @var{object} against the elements ofthe list, like @code{memq} and @code{remq}.@end defunWhen @code{delq} deletes elements from the front of the list, it does sosimply by advancing down the list and returning a sublist that startsafter those elements:@example@group(delq 'a '(a b c)) @equiv{} (cdr '(a b c))@end group@end exampleWhen an element to be deleted appears in the middle of the list,removing it involves changing the @sc{cdr}s (@pxref{Setcdr}).@example@group(setq sample-list '(a b c (4))) @result{} (a b c (4))@end group@group(delq 'a sample-list) @result{} (b c (4))@end group@groupsample-list @result{} (a b c (4))@end group@group(delq 'c sample-list) @result{} (a b (4))@end group@groupsample-list @result{} (a b (4))@end group@end exampleNote that @code{(delq 'c sample-list)} modifies @code{sample-list} tosplice out the third element, but @code{(delq 'a sample-list)} does notsplice anything---it just returns a shorter list. Don't assume that avariable which formerly held the argument @var{list} now has fewerelements, or that it still holds the original list! Instead, save theresult of @code{delq} and use that. Most often we store the result backinto the variable that held the original list:@example(setq flowers (delq 'rose flowers))@end exampleIn the following example, the @code{(4)} that @code{delq} attempts to matchand the @code{(4)} in the @code{sample-list} are not @code{eq}:@example@group(delq '(4) sample-list) @result{} (a c (4))@end groupIf you want to delete elements that are @code{equal} to a given value,use @code{delete} (see below).@end example@defun remq object listThis function returns a copy of @var{list}, with all elements removedwhich are @code{eq} to @var{object}. The letter @samp{q} in @code{remq}says that it uses @code{eq} to compare @var{object} against the elementsof @code{list}.@example@group(setq sample-list '(a b c a b c)) @result{} (a b c a b c)@end group@group(remq 'a sample-list) @result{} (b c b c)@end group@groupsample-list @result{} (a b c a b c)@end group@end example@end defun@defun memql object listThe function @code{memql} tests to see whether @var{object} is a memberof @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 withits 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 defunThe following three functions are like @code{memq}, @code{delq} and@code{remq}, but use @code{equal} rather than @code{eq} to compareelements. @xref{Equality Predicates}.@defun member object listThe function @code{member} tests to see whether @var{object} is a memberof @var{list}, comparing members with @var{object} using @code{equal}.If @var{object} is a member, @code{member} returns a list starting withits first occurrence in @var{list}. Otherwise, it returns @code{nil}.Compare this with @code{memq}:@example@group(member '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are @code{equal}.} @result{} ((2))@end group@group(memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.} @result{} nil@end group@group;; @r{Two strings with the same contents are @code{equal}.}(member "foo" '("foo" "bar")) @result{} ("foo" "bar")@end group@end example@end defun@defun delete object sequenceIf @code{sequence} is a list, this function destructively removes allelements @code{equal} to @var{object} from @var{sequence}. For lists,@code{delete} is to @code{delq} as @code{member} is to @code{memq}: ituses @code{equal} to compare elements with @var{object}, like@code{member}; when it finds an element that matches, it cuts theelement out just as @code{delq} would.If @code{sequence} is a vector or string, @code{delete} returns a copyof @code{sequence} with all elements @code{equal} to @code{object}removed.For example:@example@group(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)]) @result{} [(1)]@end group@end example@end defun@defun remove object sequenceThis function is the non-destructive counterpart of @code{delete}. Itreturns a copy of @code{sequence}, a list, vector, or string, withelements @code{equal} to @code{object} removed. For example:@example@group(remove '(2) '((2) (1) (2))) @result{} ((1))@end group@group(remove '(2) [(2) (1) (2)]) @result{} [(1)]@end group@end example@end defun@quotation@b{Common Lisp note:} The functions @code{member}, @code{delete} and@code{remove} in GNU Emacs Lisp are derived from Maclisp, not CommonLisp. The Common Lisp versions do not use @code{equal} to compareelements.@end quotation@defun member-ignore-case object listThis function is like @code{member}, except that @var{object} shouldbe a string and that it ignores differences in letter-case and textrepresentation: upper-case and lower-case letters are treated asequal, and unibyte strings are converted to multibyte prior tocomparison.@end defun@defun delete-dups listThis function destructively removes all @code{equal} duplicates from@var{list}, stores the result in @var{list} and returns it. Ofseveral @code{equal} occurrences of an element in @var{list},@code{delete-dups} keeps the first one.@end defun See also the function @code{add-to-list}, in @ref{List Variables},for a way to add an element to a list stored in a variable and used as aset.@node Association Lists@section Association Lists@cindex association list@cindex alist An @dfn{association list}, or @dfn{alist} for short, records a mappingfrom keys to values. It is a list of cons cells called@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 tolook up an item in a table. In this case, the table is the alist, andthe alist associations are the items.} Here is an example of an alist. The key @code{pine} is associated withthe value @code{cones}; the key @code{oak} is associated with@code{acorns}; and the key @code{maple} is associated with @code{seeds}.@example@group((pine . cones) (oak . acorns) (maple . seeds))@end group@end example Both the values and the keys in an alist may be any Lisp objects.For example, in the following alist, the symbol @code{a} isassociated with the number @code{1}, and the string @code{"b"} isassociated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} ofthe alist element:@example((a . 1) ("b" 2 3))@end example Sometimes it is better to design an alist to store the associatedvalue in the @sc{car} of the @sc{cdr} of the element. Here is anexample of such an alist:@example((rose red) (lily white) (buttercup yellow))@end example@noindentHere we regard @code{red} as the value associated with @code{rose}. Oneadvantage of this kind of alist is that you can store other relatedinformation---even a list of other items---in the @sc{cdr} of the@sc{cdr}. One disadvantage is that you cannot use @code{rassq} (seebelow) to find the element containing a given value. When neither ofthese considerations is important, the choice is a matter of taste, aslong as you are consistent about it for any given alist. The same alist shown above could be regarded as having theassociated value in the @sc{cdr} of the element; the value associatedwith @code{rose} would be the list @code{(red)}. Association lists are often used to record information that you mightotherwise keep on a stack, since new associations may be added easily tothe front of the list. When searching an association list for anassociation with a given key, the first one found is returned, if thereis more than one. In Emacs Lisp, it is @emph{not} an error if an element of anassociation list is not a cons cell. The alist search functions simplyignore such elements. Many other versions of Lisp signal errors in suchcases. Note that property lists are similar to association lists in severalrespects. A property list behaves like an association list in whicheach key can occur only once. @xref{Property Lists}, for a comparisonof property lists and association lists.@defun assoc key alistThis function returns the first association for @var{key} in@var{alist}, comparing @var{key} against the alist elements using@code{equal} (@pxref{Equality Predicates}). It returns @code{nil} if noassociation in @var{alist} has a @sc{car} @code{equal} to @var{key}.For example:@smallexample(setq trees '((pine . cones) (oak . acorns) (maple . seeds))) @result{} ((pine . cones) (oak . acorns) (maple . seeds))(assoc 'oak trees) @result{} (oak . acorns)(cdr (assoc 'oak trees)) @result{} acorns(assoc 'birch trees) @result{} nil@end smallexampleHere is another example, in which the keys and values are not symbols:@smallexample(setq needles-per-cluster '((2 "Austrian Pine" "Red Pine") (3 "Pitch Pine") (5 "White Pine")))(cdr (assoc 3 needles-per-cluster)) @result{} ("Pitch Pine")(cdr (assoc 2 needles-per-cluster)) @result{} ("Austrian Pine" "Red Pine")@end smallexample@end defun The function @code{assoc-string} is much like @code{assoc} exceptthat it ignores certain differences between strings. @xref{TextComparison}.@defun rassoc value alistThis function returns the first association with value @var{value} in@var{alist}. It returns @code{nil} if no association in @var{alist} hasa @sc{cdr} @code{equal} to @var{value}.@code{rassoc} is like @code{assoc} except that it compares the @sc{cdr} ofeach @var{alist} association instead of the @sc{car}. You can think ofthis as ``reverse @code{assoc},'' finding the key for a given value.@end defun@defun assq key alistThis function is like @code{assoc} in that it returns the firstassociation for @var{key} in @var{alist}, but it makes the comparisonusing @code{eq} instead of @code{equal}. @code{assq} returns @code{nil}if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}.This function is used more often than @code{assoc}, since @code{eq} isfaster than @code{equal} and most alists use symbols as keys.@xref{Equality Predicates}.@smallexample(setq trees '((pine . cones) (oak . acorns) (maple . seeds))) @result{} ((pine . cones) (oak . acorns) (maple . seeds))(assq 'pine trees) @result{} (pine . cones)@end smallexampleOn the other hand, @code{assq} is not usually useful in alists where thekeys may not be symbols:@smallexample(setq leaves '(("simple leaves" . oak) ("compound leaves" . horsechestnut)))(assq "simple leaves" leaves) @result{} nil(assoc "simple leaves" leaves) @result{} ("simple leaves" . oak)@end smallexample@end defun@defun rassq value alistThis function returns the first association with value @var{value} in@var{alist}. It returns @code{nil} if no association in @var{alist} hasa @sc{cdr} @code{eq} to @var{value}.@code{rassq} is like @code{assq} except that it compares the @sc{cdr} ofeach @var{alist} association instead of the @sc{car}. You can think ofthis as ``reverse @code{assq},'' finding the key for a given value.For example:@smallexample(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))(rassq 'acorns trees) @result{} (oak . acorns)(rassq 'spores trees) @result{} nil@end smallexample@code{rassq} cannot search for a value stored in the @sc{car}of the @sc{cdr} of an element:@smallexample(setq colors '((rose red) (lily white) (buttercup yellow)))(rassq 'white colors) @result{} nil@end smallexampleIn this case, the @sc{cdr} of the association @code{(lily white)} is notthe symbol @code{white}, but rather the list @code{(white)}. Thisbecomes clearer if the association is written in dotted pair notation:@smallexample(lily white) @equiv{} (lily . (white))@end smallexample@end defun@defun assoc-default key alist &optional test defaultThis function searches @var{alist} for a match for @var{key}. For eachelement of @var{alist}, it compares the element (if it is an atom) orthe 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 getuseful results using @code{string-match} with an alist that containsregular expressions (@pxref{Regexp Search}). If @var{test} is omittedor @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 alistsThis function returns a two-level deep copy of @var{alist}: it creates anew copy of each association, so that you can alter the associations ofthe new alist without changing the old one.@smallexample@group(setq needles-per-cluster '((2 . ("Austrian Pine" "Red Pine")) (3 . ("Pitch Pine"))@end group (5 . ("White Pine"))))@result{}((2 "Austrian Pine" "Red Pine") (3 "Pitch Pine") (5 "White Pine"))(setq copy (copy-alist needles-per-cluster))@result{}((2 "Austrian Pine" "Red Pine") (3 "Pitch Pine") (5 "White Pine"))(eq needles-per-cluster copy) @result{} nil(equal needles-per-cluster copy) @result{} t(eq (car needles-per-cluster) (car copy)) @result{} nil(cdr (car (cdr needles-per-cluster))) @result{} ("Pitch Pine")@group(eq (cdr (car (cdr needles-per-cluster))) (cdr (car (cdr copy)))) @result{} t@end group@end smallexample This example shows how @code{copy-alist} makes it possible to changethe associations of one copy without affecting the other:@smallexample@group(setcdr (assq 3 copy) '("Martian Vacuum Pine"))(cdr (assq 3 needles-per-cluster)) @result{} ("Pitch Pine")@end group@end smallexample@end defun@defun assq-delete-all key alistThis 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 deleteeach such element one by one. It returns the shortened alist, andoften modifies the original list structure of @var{alist}. Forcorrect results, use the return value of @code{assq-delete-all} ratherthan looking at the saved value of @var{alist}.@example(setq alist '((foo 1) (bar 2) (foo 3) (lose 4))) @result{} ((foo 1) (bar 2) (foo 3) (lose 4))(assq-delete-all 'foo alist) @result{} ((bar 2) (lose 4))alist @result{} ((foo 1) (bar 2) (lose 4))@end example@end defun@defun rassq-delete-all value alistThis function deletes from @var{alist} all the elements whose @sc{cdr}is @code{eq} to @var{value}. It returns the shortened alist, andoften modifies the original list structure of @var{alist}.@code{rassq-delete-all} is like @code{assq-delete-all} except that itcompares 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 sizeThis returns a new ring capable of holding @var{size} objects.@var{size} should be an integer.@end defun@defun ring-p objectThis returns @code{t} if @var{object} is a ring, @code{nil} otherwise.@end defun@defun ring-size ringThis returns the maximum capacity of the @var{ring}.@end defun@defun ring-length ringThis 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 ringThis returns a list of the objects in @var{ring}, in order, newest first.@end defun@defun ring-copy ringThis 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 ringThis returns @code{t} if @var{ring} is empty, @code{nil} otherwise.@end defun The newest element in the ring always has index 0. Higher indicescorrespond to older elements. Indices are computed modulo the ringlength. Index @minus{}1 corresponds to the oldest element, @minus{}2to the next-oldest, and so forth.@defun ring-ref ring indexThis 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 objectThis inserts @var{object} into @var{ring}, making it the newestelement, and returns @var{object}.If the ring is full, insertion removes the oldest element tomake room for the new element.@end defun@defun ring-remove ring &optional indexRemove an object from @var{ring}, and return that object. Theargument @var{index} specifies which item to remove; if it is@code{nil}, that means to remove the oldest item. If @var{ring} isempty, @code{ring-remove} signals an error.@end defun@defun ring-insert-at-beginning ring objectThis inserts @var{object} into @var{ring}, treating it as the oldestelement. The return value is not significant.If the ring is full, this function removes the newest element to makeroom for the inserted element.@end defun@cindex fifo data structure If you are careful not to exceed the ring size, you canuse 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