Mercurial > emacs
annotate doc/lispref/lists.texi @ 103774:5048b64c7cf0
* b2m.c (main): Ensure that each message ends in two newlines.
author | Chong Yidong <cyd@stupidchicken.com> |
---|---|
date | Wed, 08 Jul 2009 03:20:03 +0000 |
parents | 1d59ea1e4daf |
children | 1d1d5d9bd884 |
rev | line source |
---|---|
84080 | 1 @c -*-texinfo-*- |
2 @c This is part of the GNU Emacs Lisp Reference Manual. | |
3 @c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998, 1999, 2001, | |
100974 | 4 @c 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc. |
84080 | 5 @c See the file elisp.texi for copying conditions. |
84116
0ba80d073e27
(setfilename): Go up one more level to ../../info.
Glenn Morris <rgm@gnu.org>
parents:
84080
diff
changeset
|
6 @setfilename ../../info/lists |
84080 | 7 @node Lists, Sequences Arrays Vectors, Strings and Characters, Top |
8 @chapter Lists | |
9 @cindex lists | |
10 @cindex element (of list) | |
11 | |
12 A @dfn{list} represents a sequence of zero or more elements (which may | |
13 be any Lisp objects). The important difference between lists and | |
14 vectors is that two or more lists can share part of their structure; in | |
15 addition, you can insert or delete elements in a list without copying | |
16 the whole list. | |
17 | |
18 @menu | |
19 * Cons Cells:: How lists are made out of cons cells. | |
20 * List-related Predicates:: Is this object a list? Comparing two lists. | |
21 * List Elements:: Extracting the pieces of a list. | |
22 * Building Lists:: Creating list structure. | |
23 * List Variables:: Modifying lists stored in variables. | |
24 * Modifying Lists:: Storing new pieces into an existing list. | |
25 * Sets And Lists:: A list can represent a finite mathematical set. | |
26 * Association Lists:: A list can represent a finite relation or mapping. | |
27 * Rings:: Managing a fixed-size ring of objects. | |
28 @end menu | |
29 | |
30 @node Cons Cells | |
31 @section Lists and Cons Cells | |
32 @cindex lists and cons cells | |
33 | |
34 Lists in Lisp are not a primitive data type; they are built up from | |
35 @dfn{cons cells}. A cons cell is a data object that represents an | |
36 ordered pair. That is, it has two slots, and each slot @dfn{holds}, or | |
37 @dfn{refers to}, some Lisp object. One slot is known as the @sc{car}, | |
38 and the other is known as the @sc{cdr}. (These names are traditional; | |
39 see @ref{Cons Cell Type}.) @sc{cdr} is pronounced ``could-er.'' | |
40 | |
41 We say that ``the @sc{car} of this cons cell is'' whatever object | |
42 its @sc{car} slot currently holds, and likewise for the @sc{cdr}. | |
43 | |
44 A list is a series of cons cells ``chained together,'' so that each | |
45 cell refers to the next one. There is one cons cell for each element of | |
46 the list. By convention, the @sc{car}s of the cons cells hold the | |
47 elements of the list, and the @sc{cdr}s are used to chain the list: the | |
48 @sc{cdr} slot of each cons cell refers to the following cons cell. The | |
49 @sc{cdr} of the last cons cell is @code{nil}. This asymmetry between | |
50 the @sc{car} and the @sc{cdr} is entirely a matter of convention; at the | |
51 level of cons cells, the @sc{car} and @sc{cdr} slots have the same | |
52 characteristics. | |
53 | |
54 @cindex true list | |
55 Since @code{nil} is the conventional value to put in the @sc{cdr} of | |
56 the last cons cell in the list, we call that case a @dfn{true list}. | |
57 | |
58 In Lisp, we consider the symbol @code{nil} a list as well as a | |
59 symbol; it is the list with no elements. For convenience, the symbol | |
60 @code{nil} is considered to have @code{nil} as its @sc{cdr} (and also | |
61 as its @sc{car}). Therefore, the @sc{cdr} of a true list is always a | |
62 true list. | |
63 | |
64 @cindex dotted list | |
65 @cindex circular list | |
66 If the @sc{cdr} of a list's last cons cell is some other value, | |
67 neither @code{nil} nor another cons cell, we call the structure a | |
68 @dfn{dotted list}, since its printed representation would use | |
69 @samp{.}. There is one other possibility: some cons cell's @sc{cdr} | |
70 could point to one of the previous cons cells in the list. We call | |
71 that structure a @dfn{circular list}. | |
72 | |
73 For some purposes, it does not matter whether a list is true, | |
74 circular or dotted. If the program doesn't look far enough down the | |
75 list to see the @sc{cdr} of the final cons cell, it won't care. | |
76 However, some functions that operate on lists demand true lists and | |
77 signal errors if given a dotted list. Most functions that try to find | |
78 the end of a list enter infinite loops if given a circular list. | |
79 | |
80 @cindex list structure | |
81 Because most cons cells are used as part of lists, the phrase | |
82 @dfn{list structure} has come to mean any structure made out of cons | |
83 cells. | |
84 | |
85 The @sc{cdr} of any nonempty true list @var{l} is a list containing all the | |
86 elements of @var{l} except the first. | |
87 | |
88 @xref{Cons Cell Type}, for the read and print syntax of cons cells and | |
89 lists, and for ``box and arrow'' illustrations of lists. | |
90 | |
91 @node List-related Predicates | |
92 @section Predicates on Lists | |
93 | |
94 The following predicates test whether a Lisp object is an atom, | |
95 whether it is a cons cell or is a list, or whether it is the | |
96 distinguished object @code{nil}. (Many of these predicates can be | |
97 defined in terms of the others, but they are used so often that it is | |
98 worth having all of them.) | |
99 | |
100 @defun consp object | |
101 This function returns @code{t} if @var{object} is a cons cell, @code{nil} | |
102 otherwise. @code{nil} is not a cons cell, although it @emph{is} a list. | |
103 @end defun | |
104 | |
105 @defun atom object | |
106 This function returns @code{t} if @var{object} is an atom, @code{nil} | |
107 otherwise. All objects except cons cells are atoms. The symbol | |
108 @code{nil} is an atom and is also a list; it is the only Lisp object | |
109 that is both. | |
110 | |
111 @example | |
112 (atom @var{object}) @equiv{} (not (consp @var{object})) | |
113 @end example | |
114 @end defun | |
115 | |
116 @defun listp object | |
117 This function returns @code{t} if @var{object} is a cons cell or | |
118 @code{nil}. Otherwise, it returns @code{nil}. | |
119 | |
120 @example | |
121 @group | |
122 (listp '(1)) | |
123 @result{} t | |
124 @end group | |
125 @group | |
126 (listp '()) | |
127 @result{} t | |
128 @end group | |
129 @end example | |
130 @end defun | |
131 | |
132 @defun nlistp object | |
133 This function is the opposite of @code{listp}: it returns @code{t} if | |
134 @var{object} is not a list. Otherwise, it returns @code{nil}. | |
135 | |
136 @example | |
137 (listp @var{object}) @equiv{} (not (nlistp @var{object})) | |
138 @end example | |
139 @end defun | |
140 | |
141 @defun null object | |
142 This function returns @code{t} if @var{object} is @code{nil}, and | |
143 returns @code{nil} otherwise. This function is identical to @code{not}, | |
144 but as a matter of clarity we use @code{null} when @var{object} is | |
145 considered a list and @code{not} when it is considered a truth value | |
146 (see @code{not} in @ref{Combining Conditions}). | |
147 | |
148 @example | |
149 @group | |
150 (null '(1)) | |
151 @result{} nil | |
152 @end group | |
153 @group | |
154 (null '()) | |
155 @result{} t | |
156 @end group | |
157 @end example | |
158 @end defun | |
159 | |
160 | |
161 @node List Elements | |
162 @section Accessing Elements of Lists | |
163 @cindex list elements | |
164 | |
165 @defun car cons-cell | |
166 This function returns the value referred to by the first slot of the | |
102183
1d59ea1e4daf
(List Elements): Copyedits.
Chong Yidong <cyd@stupidchicken.com>
parents:
102179
diff
changeset
|
167 cons cell @var{cons-cell}. In other words, it returns the @sc{car} of |
1d59ea1e4daf
(List Elements): Copyedits.
Chong Yidong <cyd@stupidchicken.com>
parents:
102179
diff
changeset
|
168 @var{cons-cell}. |
84080 | 169 |
102183
1d59ea1e4daf
(List Elements): Copyedits.
Chong Yidong <cyd@stupidchicken.com>
parents:
102179
diff
changeset
|
170 As a special case, if @var{cons-cell} is @code{nil}, this function |
1d59ea1e4daf
(List Elements): Copyedits.
Chong Yidong <cyd@stupidchicken.com>
parents:
102179
diff
changeset
|
171 returns @code{nil}. Therefore, any list is a valid argument. An |
1d59ea1e4daf
(List Elements): Copyedits.
Chong Yidong <cyd@stupidchicken.com>
parents:
102179
diff
changeset
|
172 error is signaled if the argument is not a cons cell or @code{nil}. |
84080 | 173 |
174 @example | |
175 @group | |
176 (car '(a b c)) | |
177 @result{} a | |
178 @end group | |
179 @group | |
180 (car '()) | |
181 @result{} nil | |
182 @end group | |
183 @end example | |
184 @end defun | |
185 | |
186 @defun cdr cons-cell | |
102183
1d59ea1e4daf
(List Elements): Copyedits.
Chong Yidong <cyd@stupidchicken.com>
parents:
102179
diff
changeset
|
187 This function returns the value referred to by the second slot of the |
1d59ea1e4daf
(List Elements): Copyedits.
Chong Yidong <cyd@stupidchicken.com>
parents:
102179
diff
changeset
|
188 cons cell @var{cons-cell}. In other words, it returns the @sc{cdr} of |
1d59ea1e4daf
(List Elements): Copyedits.
Chong Yidong <cyd@stupidchicken.com>
parents:
102179
diff
changeset
|
189 @var{cons-cell}. |
84080 | 190 |
102183
1d59ea1e4daf
(List Elements): Copyedits.
Chong Yidong <cyd@stupidchicken.com>
parents:
102179
diff
changeset
|
191 As a special case, if @var{cons-cell} is @code{nil}, this function |
1d59ea1e4daf
(List Elements): Copyedits.
Chong Yidong <cyd@stupidchicken.com>
parents:
102179
diff
changeset
|
192 returns @code{nil}; therefore, any list is a valid argument. An error |
1d59ea1e4daf
(List Elements): Copyedits.
Chong Yidong <cyd@stupidchicken.com>
parents:
102179
diff
changeset
|
193 is signaled if the argument is not a cons cell or @code{nil}. |
84080 | 194 |
195 @example | |
196 @group | |
197 (cdr '(a b c)) | |
198 @result{} (b c) | |
199 @end group | |
200 @group | |
201 (cdr '()) | |
202 @result{} nil | |
203 @end group | |
204 @end example | |
205 @end defun | |
206 | |
207 @defun car-safe object | |
208 This function lets you take the @sc{car} of a cons cell while avoiding | |
209 errors for other data types. It returns the @sc{car} of @var{object} if | |
210 @var{object} is a cons cell, @code{nil} otherwise. This is in contrast | |
211 to @code{car}, which signals an error if @var{object} is not a list. | |
212 | |
213 @example | |
214 @group | |
215 (car-safe @var{object}) | |
216 @equiv{} | |
217 (let ((x @var{object})) | |
218 (if (consp x) | |
219 (car x) | |
220 nil)) | |
221 @end group | |
222 @end example | |
223 @end defun | |
224 | |
225 @defun cdr-safe object | |
226 This function lets you take the @sc{cdr} of a cons cell while | |
227 avoiding errors for other data types. It returns the @sc{cdr} of | |
228 @var{object} if @var{object} is a cons cell, @code{nil} otherwise. | |
229 This is in contrast to @code{cdr}, which signals an error if | |
230 @var{object} is not a list. | |
231 | |
232 @example | |
233 @group | |
234 (cdr-safe @var{object}) | |
235 @equiv{} | |
236 (let ((x @var{object})) | |
237 (if (consp x) | |
238 (cdr x) | |
239 nil)) | |
240 @end group | |
241 @end example | |
242 @end defun | |
243 | |
244 @defmac pop listname | |
245 This macro is a way of examining the @sc{car} of a list, | |
246 and taking it off the list, all at once. | |
247 | |
248 It operates on the list which is stored in the symbol @var{listname}. | |
249 It removes this element from the list by setting @var{listname} | |
250 to the @sc{cdr} of its old value---but it also returns the @sc{car} | |
251 of that list, which is the element being removed. | |
252 | |
253 @example | |
254 x | |
255 @result{} (a b c) | |
256 (pop x) | |
257 @result{} a | |
258 x | |
259 @result{} (b c) | |
260 @end example | |
261 @end defmac | |
262 | |
263 @defun nth n list | |
264 @anchor{Definition of nth} | |
265 This function returns the @var{n}th element of @var{list}. Elements | |
266 are numbered starting with zero, so the @sc{car} of @var{list} is | |
267 element number zero. If the length of @var{list} is @var{n} or less, | |
268 the value is @code{nil}. | |
269 | |
270 If @var{n} is negative, @code{nth} returns the first element of | |
271 @var{list}. | |
272 | |
273 @example | |
274 @group | |
275 (nth 2 '(1 2 3 4)) | |
276 @result{} 3 | |
277 @end group | |
278 @group | |
279 (nth 10 '(1 2 3 4)) | |
280 @result{} nil | |
281 @end group | |
282 @group | |
283 (nth -3 '(1 2 3 4)) | |
284 @result{} 1 | |
285 | |
286 (nth n x) @equiv{} (car (nthcdr n x)) | |
287 @end group | |
288 @end example | |
289 | |
290 The function @code{elt} is similar, but applies to any kind of sequence. | |
291 For historical reasons, it takes its arguments in the opposite order. | |
292 @xref{Sequence Functions}. | |
293 @end defun | |
294 | |
295 @defun nthcdr n list | |
296 This function returns the @var{n}th @sc{cdr} of @var{list}. In other | |
297 words, it skips past the first @var{n} links of @var{list} and returns | |
298 what follows. | |
299 | |
300 If @var{n} is zero or negative, @code{nthcdr} returns all of | |
301 @var{list}. If the length of @var{list} is @var{n} or less, | |
302 @code{nthcdr} returns @code{nil}. | |
303 | |
304 @example | |
305 @group | |
306 (nthcdr 1 '(1 2 3 4)) | |
307 @result{} (2 3 4) | |
308 @end group | |
309 @group | |
310 (nthcdr 10 '(1 2 3 4)) | |
311 @result{} nil | |
312 @end group | |
313 @group | |
314 (nthcdr -3 '(1 2 3 4)) | |
315 @result{} (1 2 3 4) | |
316 @end group | |
317 @end example | |
318 @end defun | |
319 | |
320 @defun last list &optional n | |
321 This function returns the last link of @var{list}. The @code{car} of | |
322 this link is the list's last element. If @var{list} is null, | |
323 @code{nil} is returned. If @var{n} is non-@code{nil}, the | |
324 @var{n}th-to-last link is returned instead, or the whole of @var{list} | |
325 if @var{n} is bigger than @var{list}'s length. | |
326 @end defun | |
327 | |
328 @defun safe-length list | |
329 @anchor{Definition of safe-length} | |
330 This function returns the length of @var{list}, with no risk of either | |
331 an error or an infinite loop. It generally returns the number of | |
332 distinct cons cells in the list. However, for circular lists, | |
333 the value is just an upper bound; it is often too large. | |
334 | |
335 If @var{list} is not @code{nil} or a cons cell, @code{safe-length} | |
336 returns 0. | |
337 @end defun | |
338 | |
339 The most common way to compute the length of a list, when you are not | |
340 worried that it may be circular, is with @code{length}. @xref{Sequence | |
341 Functions}. | |
342 | |
343 @defun caar cons-cell | |
344 This is the same as @code{(car (car @var{cons-cell}))}. | |
345 @end defun | |
346 | |
347 @defun cadr cons-cell | |
348 This is the same as @code{(car (cdr @var{cons-cell}))} | |
349 or @code{(nth 1 @var{cons-cell})}. | |
350 @end defun | |
351 | |
352 @defun cdar cons-cell | |
353 This is the same as @code{(cdr (car @var{cons-cell}))}. | |
354 @end defun | |
355 | |
356 @defun cddr cons-cell | |
357 This is the same as @code{(cdr (cdr @var{cons-cell}))} | |
358 or @code{(nthcdr 2 @var{cons-cell})}. | |
359 @end defun | |
360 | |
361 @defun butlast x &optional n | |
362 This function returns the list @var{x} with the last element, | |
363 or the last @var{n} elements, removed. If @var{n} is greater | |
364 than zero it makes a copy of the list so as not to damage the | |
365 original list. In general, @code{(append (butlast @var{x} @var{n}) | |
366 (last @var{x} @var{n}))} will return a list equal to @var{x}. | |
367 @end defun | |
368 | |
369 @defun nbutlast x &optional n | |
370 This is a version of @code{butlast} that works by destructively | |
371 modifying the @code{cdr} of the appropriate element, rather than | |
372 making a copy of the list. | |
373 @end defun | |
374 | |
375 @node Building Lists | |
376 @comment node-name, next, previous, up | |
377 @section Building Cons Cells and Lists | |
378 @cindex cons cells | |
379 @cindex building lists | |
380 | |
381 Many functions build lists, as lists reside at the very heart of Lisp. | |
382 @code{cons} is the fundamental list-building function; however, it is | |
383 interesting to note that @code{list} is used more times in the source | |
384 code for Emacs than @code{cons}. | |
385 | |
386 @defun cons object1 object2 | |
387 This function is the most basic function for building new list | |
388 structure. It creates a new cons cell, making @var{object1} the | |
389 @sc{car}, and @var{object2} the @sc{cdr}. It then returns the new | |
390 cons cell. The arguments @var{object1} and @var{object2} may be any | |
391 Lisp objects, but most often @var{object2} is a list. | |
392 | |
393 @example | |
394 @group | |
395 (cons 1 '(2)) | |
396 @result{} (1 2) | |
397 @end group | |
398 @group | |
399 (cons 1 '()) | |
400 @result{} (1) | |
401 @end group | |
402 @group | |
403 (cons 1 2) | |
404 @result{} (1 . 2) | |
405 @end group | |
406 @end example | |
407 | |
408 @cindex consing | |
409 @code{cons} is often used to add a single element to the front of a | |
410 list. This is called @dfn{consing the element onto the list}. | |
411 @footnote{There is no strictly equivalent way to add an element to | |
412 the end of a list. You can use @code{(append @var{listname} (list | |
413 @var{newelt}))}, which creates a whole new list by copying @var{listname} | |
414 and adding @var{newelt} to its end. Or you can use @code{(nconc | |
415 @var{listname} (list @var{newelt}))}, which modifies @var{listname} | |
416 by following all the @sc{cdr}s and then replacing the terminating | |
417 @code{nil}. Compare this to adding an element to the beginning of a | |
418 list with @code{cons}, which neither copies nor modifies the list.} | |
419 For example: | |
420 | |
421 @example | |
422 (setq list (cons newelt list)) | |
423 @end example | |
424 | |
425 Note that there is no conflict between the variable named @code{list} | |
426 used in this example and the function named @code{list} described below; | |
427 any symbol can serve both purposes. | |
428 @end defun | |
429 | |
430 @defun list &rest objects | |
431 This function creates a list with @var{objects} as its elements. The | |
432 resulting list is always @code{nil}-terminated. If no @var{objects} | |
433 are given, the empty list is returned. | |
434 | |
435 @example | |
436 @group | |
437 (list 1 2 3 4 5) | |
438 @result{} (1 2 3 4 5) | |
439 @end group | |
440 @group | |
441 (list 1 2 '(3 4 5) 'foo) | |
442 @result{} (1 2 (3 4 5) foo) | |
443 @end group | |
444 @group | |
445 (list) | |
446 @result{} nil | |
447 @end group | |
448 @end example | |
449 @end defun | |
450 | |
451 @defun make-list length object | |
452 This function creates a list of @var{length} elements, in which each | |
453 element is @var{object}. Compare @code{make-list} with | |
454 @code{make-string} (@pxref{Creating Strings}). | |
455 | |
456 @example | |
457 @group | |
458 (make-list 3 'pigs) | |
459 @result{} (pigs pigs pigs) | |
460 @end group | |
461 @group | |
462 (make-list 0 'pigs) | |
463 @result{} nil | |
464 @end group | |
465 @group | |
466 (setq l (make-list 3 '(a b)) | |
467 @result{} ((a b) (a b) (a b)) | |
468 (eq (car l) (cadr l)) | |
469 @result{} t | |
470 @end group | |
471 @end example | |
472 @end defun | |
473 | |
474 @defun append &rest sequences | |
475 @cindex copying lists | |
476 This function returns a list containing all the elements of | |
477 @var{sequences}. The @var{sequences} may be lists, vectors, | |
478 bool-vectors, or strings, but the last one should usually be a list. | |
479 All arguments except the last one are copied, so none of the arguments | |
480 is altered. (See @code{nconc} in @ref{Rearrangement}, for a way to join | |
481 lists with no copying.) | |
482 | |
483 More generally, the final argument to @code{append} may be any Lisp | |
484 object. The final argument is not copied or converted; it becomes the | |
485 @sc{cdr} of the last cons cell in the new list. If the final argument | |
486 is itself a list, then its elements become in effect elements of the | |
487 result list. If the final element is not a list, the result is a | |
488 dotted list since its final @sc{cdr} is not @code{nil} as required | |
489 in a true list. | |
490 @end defun | |
491 | |
492 Here is an example of using @code{append}: | |
493 | |
494 @example | |
495 @group | |
496 (setq trees '(pine oak)) | |
497 @result{} (pine oak) | |
498 (setq more-trees (append '(maple birch) trees)) | |
499 @result{} (maple birch pine oak) | |
500 @end group | |
501 | |
502 @group | |
503 trees | |
504 @result{} (pine oak) | |
505 more-trees | |
506 @result{} (maple birch pine oak) | |
507 @end group | |
508 @group | |
509 (eq trees (cdr (cdr more-trees))) | |
510 @result{} t | |
511 @end group | |
512 @end example | |
513 | |
514 You can see how @code{append} works by looking at a box diagram. The | |
515 variable @code{trees} is set to the list @code{(pine oak)} and then the | |
516 variable @code{more-trees} is set to the list @code{(maple birch pine | |
517 oak)}. However, the variable @code{trees} continues to refer to the | |
518 original list: | |
519 | |
520 @smallexample | |
521 @group | |
522 more-trees trees | |
523 | | | |
524 | --- --- --- --- -> --- --- --- --- | |
525 --> | | |--> | | |--> | | |--> | | |--> nil | |
526 --- --- --- --- --- --- --- --- | |
527 | | | | | |
528 | | | | | |
529 --> maple -->birch --> pine --> oak | |
530 @end group | |
531 @end smallexample | |
532 | |
533 An empty sequence contributes nothing to the value returned by | |
534 @code{append}. As a consequence of this, a final @code{nil} argument | |
535 forces a copy of the previous argument: | |
536 | |
537 @example | |
538 @group | |
539 trees | |
540 @result{} (pine oak) | |
541 @end group | |
542 @group | |
543 (setq wood (append trees nil)) | |
544 @result{} (pine oak) | |
545 @end group | |
546 @group | |
547 wood | |
548 @result{} (pine oak) | |
549 @end group | |
550 @group | |
551 (eq wood trees) | |
552 @result{} nil | |
553 @end group | |
554 @end example | |
555 | |
556 @noindent | |
557 This once was the usual way to copy a list, before the function | |
558 @code{copy-sequence} was invented. @xref{Sequences Arrays Vectors}. | |
559 | |
560 Here we show the use of vectors and strings as arguments to @code{append}: | |
561 | |
562 @example | |
563 @group | |
564 (append [a b] "cd" nil) | |
565 @result{} (a b 99 100) | |
566 @end group | |
567 @end example | |
568 | |
569 With the help of @code{apply} (@pxref{Calling Functions}), we can append | |
570 all the lists in a list of lists: | |
571 | |
572 @example | |
573 @group | |
574 (apply 'append '((a b c) nil (x y z) nil)) | |
575 @result{} (a b c x y z) | |
576 @end group | |
577 @end example | |
578 | |
579 If no @var{sequences} are given, @code{nil} is returned: | |
580 | |
581 @example | |
582 @group | |
583 (append) | |
584 @result{} nil | |
585 @end group | |
586 @end example | |
587 | |
588 Here are some examples where the final argument is not a list: | |
589 | |
590 @example | |
591 (append '(x y) 'z) | |
592 @result{} (x y . z) | |
593 (append '(x y) [z]) | |
594 @result{} (x y . [z]) | |
595 @end example | |
596 | |
597 @noindent | |
598 The second example shows that when the final argument is a sequence but | |
599 not a list, the sequence's elements do not become elements of the | |
600 resulting list. Instead, the sequence becomes the final @sc{cdr}, like | |
601 any other non-list final argument. | |
602 | |
603 @defun reverse list | |
604 This function creates a new list whose elements are the elements of | |
605 @var{list}, but in reverse order. The original argument @var{list} is | |
606 @emph{not} altered. | |
607 | |
608 @example | |
609 @group | |
610 (setq x '(1 2 3 4)) | |
611 @result{} (1 2 3 4) | |
612 @end group | |
613 @group | |
614 (reverse x) | |
615 @result{} (4 3 2 1) | |
616 x | |
617 @result{} (1 2 3 4) | |
618 @end group | |
619 @end example | |
620 @end defun | |
621 | |
622 @defun copy-tree tree &optional vecp | |
623 This function returns a copy of the tree @code{tree}. If @var{tree} is a | |
624 cons cell, this makes a new cons cell with the same @sc{car} and | |
625 @sc{cdr}, then recursively copies the @sc{car} and @sc{cdr} in the | |
626 same way. | |
627 | |
628 Normally, when @var{tree} is anything other than a cons cell, | |
629 @code{copy-tree} simply returns @var{tree}. However, if @var{vecp} is | |
630 non-@code{nil}, it copies vectors too (and operates recursively on | |
631 their elements). | |
632 @end defun | |
633 | |
634 @defun number-sequence from &optional to separation | |
635 This returns a list of numbers starting with @var{from} and | |
636 incrementing by @var{separation}, and ending at or just before | |
637 @var{to}. @var{separation} can be positive or negative and defaults | |
638 to 1. If @var{to} is @code{nil} or numerically equal to @var{from}, | |
639 the value is the one-element list @code{(@var{from})}. If @var{to} is | |
640 less than @var{from} with a positive @var{separation}, or greater than | |
641 @var{from} with a negative @var{separation}, the value is @code{nil} | |
642 because those arguments specify an empty sequence. | |
643 | |
644 If @var{separation} is 0 and @var{to} is neither @code{nil} nor | |
645 numerically equal to @var{from}, @code{number-sequence} signals an | |
646 error, since those arguments specify an infinite sequence. | |
647 | |
648 All arguments can be integers or floating point numbers. However, | |
649 floating point arguments can be tricky, because floating point | |
650 arithmetic is inexact. For instance, depending on the machine, it may | |
651 quite well happen that @code{(number-sequence 0.4 0.6 0.2)} returns | |
652 the one element list @code{(0.4)}, whereas | |
653 @code{(number-sequence 0.4 0.8 0.2)} returns a list with three | |
654 elements. The @var{n}th element of the list is computed by the exact | |
655 formula @code{(+ @var{from} (* @var{n} @var{separation}))}. Thus, if | |
656 one wants to make sure that @var{to} is included in the list, one can | |
657 pass an expression of this exact type for @var{to}. Alternatively, | |
658 one can replace @var{to} with a slightly larger value (or a slightly | |
659 more negative value if @var{separation} is negative). | |
660 | |
661 Some examples: | |
662 | |
663 @example | |
664 (number-sequence 4 9) | |
665 @result{} (4 5 6 7 8 9) | |
666 (number-sequence 9 4 -1) | |
667 @result{} (9 8 7 6 5 4) | |
668 (number-sequence 9 4 -2) | |
669 @result{} (9 7 5) | |
670 (number-sequence 8) | |
671 @result{} (8) | |
672 (number-sequence 8 5) | |
673 @result{} nil | |
674 (number-sequence 5 8 -1) | |
675 @result{} nil | |
676 (number-sequence 1.5 6 2) | |
677 @result{} (1.5 3.5 5.5) | |
678 @end example | |
679 @end defun | |
680 | |
681 @node List Variables | |
682 @section Modifying List Variables | |
683 | |
684 These functions, and one macro, provide convenient ways | |
685 to modify a list which is stored in a variable. | |
686 | |
687 @defmac push newelt listname | |
688 This macro provides an alternative way to write | |
689 @code{(setq @var{listname} (cons @var{newelt} @var{listname}))}. | |
690 | |
691 @example | |
692 (setq l '(a b)) | |
693 @result{} (a b) | |
694 (push 'c l) | |
695 @result{} (c a b) | |
696 l | |
697 @result{} (c a b) | |
698 @end example | |
699 @end defmac | |
700 | |
701 Two functions modify lists that are the values of variables. | |
702 | |
703 @defun add-to-list symbol element &optional append compare-fn | |
704 This function sets the variable @var{symbol} by consing @var{element} | |
705 onto the old value, if @var{element} is not already a member of that | |
706 value. It returns the resulting list, whether updated or not. The | |
707 value of @var{symbol} had better be a list already before the call. | |
708 @code{add-to-list} uses @var{compare-fn} to compare @var{element} | |
709 against existing list members; if @var{compare-fn} is @code{nil}, it | |
710 uses @code{equal}. | |
711 | |
712 Normally, if @var{element} is added, it is added to the front of | |
713 @var{symbol}, but if the optional argument @var{append} is | |
714 non-@code{nil}, it is added at the end. | |
715 | |
716 The argument @var{symbol} is not implicitly quoted; @code{add-to-list} | |
717 is an ordinary function, like @code{set} and unlike @code{setq}. Quote | |
718 the argument yourself if that is what you want. | |
719 @end defun | |
720 | |
721 Here's a scenario showing how to use @code{add-to-list}: | |
722 | |
723 @example | |
724 (setq foo '(a b)) | |
725 @result{} (a b) | |
726 | |
727 (add-to-list 'foo 'c) ;; @r{Add @code{c}.} | |
728 @result{} (c a b) | |
729 | |
730 (add-to-list 'foo 'b) ;; @r{No effect.} | |
731 @result{} (c a b) | |
732 | |
733 foo ;; @r{@code{foo} was changed.} | |
734 @result{} (c a b) | |
735 @end example | |
736 | |
737 An equivalent expression for @code{(add-to-list '@var{var} | |
738 @var{value})} is this: | |
739 | |
740 @example | |
741 (or (member @var{value} @var{var}) | |
742 (setq @var{var} (cons @var{value} @var{var}))) | |
743 @end example | |
744 | |
745 @defun add-to-ordered-list symbol element &optional order | |
746 This function sets the variable @var{symbol} by inserting | |
747 @var{element} into the old value, which must be a list, at the | |
748 position specified by @var{order}. If @var{element} is already a | |
749 member of the list, its position in the list is adjusted according | |
750 to @var{order}. Membership is tested using @code{eq}. | |
751 This function returns the resulting list, whether updated or not. | |
752 | |
753 The @var{order} is typically a number (integer or float), and the | |
754 elements of the list are sorted in non-decreasing numerical order. | |
755 | |
756 @var{order} may also be omitted or @code{nil}. Then the numeric order | |
757 of @var{element} stays unchanged if it already has one; otherwise, | |
758 @var{element} has no numeric order. Elements without a numeric list | |
759 order are placed at the end of the list, in no particular order. | |
760 | |
761 Any other value for @var{order} removes the numeric order of @var{element} | |
762 if it already has one; otherwise, it is equivalent to @code{nil}. | |
763 | |
764 The argument @var{symbol} is not implicitly quoted; | |
765 @code{add-to-ordered-list} is an ordinary function, like @code{set} | |
766 and unlike @code{setq}. Quote the argument yourself if that is what | |
767 you want. | |
768 | |
769 The ordering information is stored in a hash table on @var{symbol}'s | |
770 @code{list-order} property. | |
771 @end defun | |
772 | |
773 Here's a scenario showing how to use @code{add-to-ordered-list}: | |
774 | |
775 @example | |
776 (setq foo '()) | |
777 @result{} nil | |
778 | |
779 (add-to-ordered-list 'foo 'a 1) ;; @r{Add @code{a}.} | |
780 @result{} (a) | |
781 | |
782 (add-to-ordered-list 'foo 'c 3) ;; @r{Add @code{c}.} | |
783 @result{} (a c) | |
784 | |
785 (add-to-ordered-list 'foo 'b 2) ;; @r{Add @code{b}.} | |
786 @result{} (a b c) | |
787 | |
788 (add-to-ordered-list 'foo 'b 4) ;; @r{Move @code{b}.} | |
789 @result{} (a c b) | |
790 | |
791 (add-to-ordered-list 'foo 'd) ;; @r{Append @code{d}.} | |
792 @result{} (a c b d) | |
793 | |
794 (add-to-ordered-list 'foo 'e) ;; @r{Add @code{e}}. | |
795 @result{} (a c b e d) | |
796 | |
797 foo ;; @r{@code{foo} was changed.} | |
798 @result{} (a c b e d) | |
799 @end example | |
800 | |
801 @node Modifying Lists | |
802 @section Modifying Existing List Structure | |
803 @cindex destructive list operations | |
804 | |
805 You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the | |
806 primitives @code{setcar} and @code{setcdr}. We call these ``destructive'' | |
807 operations because they change existing list structure. | |
808 | |
809 @cindex CL note---@code{rplaca} vs @code{setcar} | |
810 @quotation | |
811 @findex rplaca | |
812 @findex rplacd | |
813 @b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and | |
814 @code{rplacd} to alter list structure; they change structure the same | |
815 way as @code{setcar} and @code{setcdr}, but the Common Lisp functions | |
816 return the cons cell while @code{setcar} and @code{setcdr} return the | |
817 new @sc{car} or @sc{cdr}. | |
818 @end quotation | |
819 | |
820 @menu | |
821 * Setcar:: Replacing an element in a list. | |
822 * Setcdr:: Replacing part of the list backbone. | |
823 This can be used to remove or add elements. | |
824 * Rearrangement:: Reordering the elements in a list; combining lists. | |
825 @end menu | |
826 | |
827 @node Setcar | |
828 @subsection Altering List Elements with @code{setcar} | |
829 | |
830 Changing the @sc{car} of a cons cell is done with @code{setcar}. When | |
831 used on a list, @code{setcar} replaces one element of a list with a | |
832 different element. | |
833 | |
834 @defun setcar cons object | |
835 This function stores @var{object} as the new @sc{car} of @var{cons}, | |
836 replacing its previous @sc{car}. In other words, it changes the | |
837 @sc{car} slot of @var{cons} to refer to @var{object}. It returns the | |
838 value @var{object}. For example: | |
839 | |
840 @example | |
841 @group | |
842 (setq x '(1 2)) | |
843 @result{} (1 2) | |
844 @end group | |
845 @group | |
846 (setcar x 4) | |
847 @result{} 4 | |
848 @end group | |
849 @group | |
850 x | |
851 @result{} (4 2) | |
852 @end group | |
853 @end example | |
854 @end defun | |
855 | |
856 When a cons cell is part of the shared structure of several lists, | |
857 storing a new @sc{car} into the cons changes one element of each of | |
858 these lists. Here is an example: | |
859 | |
860 @example | |
861 @group | |
862 ;; @r{Create two lists that are partly shared.} | |
863 (setq x1 '(a b c)) | |
864 @result{} (a b c) | |
865 (setq x2 (cons 'z (cdr x1))) | |
866 @result{} (z b c) | |
867 @end group | |
868 | |
869 @group | |
870 ;; @r{Replace the @sc{car} of a shared link.} | |
871 (setcar (cdr x1) 'foo) | |
872 @result{} foo | |
873 x1 ; @r{Both lists are changed.} | |
874 @result{} (a foo c) | |
875 x2 | |
876 @result{} (z foo c) | |
877 @end group | |
878 | |
879 @group | |
880 ;; @r{Replace the @sc{car} of a link that is not shared.} | |
881 (setcar x1 'baz) | |
882 @result{} baz | |
883 x1 ; @r{Only one list is changed.} | |
884 @result{} (baz foo c) | |
885 x2 | |
886 @result{} (z foo c) | |
887 @end group | |
888 @end example | |
889 | |
890 Here is a graphical depiction of the shared structure of the two lists | |
891 in the variables @code{x1} and @code{x2}, showing why replacing @code{b} | |
892 changes them both: | |
893 | |
894 @example | |
895 @group | |
896 --- --- --- --- --- --- | |
897 x1---> | | |----> | | |--> | | |--> nil | |
898 --- --- --- --- --- --- | |
899 | --> | | | |
900 | | | | | |
901 --> a | --> b --> c | |
902 | | |
903 --- --- | | |
904 x2--> | | |-- | |
905 --- --- | |
906 | | |
907 | | |
908 --> z | |
909 @end group | |
910 @end example | |
911 | |
912 Here is an alternative form of box diagram, showing the same relationship: | |
913 | |
914 @example | |
915 @group | |
916 x1: | |
917 -------------- -------------- -------------- | |
918 | car | cdr | | car | cdr | | car | cdr | | |
919 | a | o------->| b | o------->| c | nil | | |
920 | | | -->| | | | | | | |
921 -------------- | -------------- -------------- | |
922 | | |
923 x2: | | |
924 -------------- | | |
925 | car | cdr | | | |
926 | z | o---- | |
927 | | | | |
928 -------------- | |
929 @end group | |
930 @end example | |
931 | |
932 @node Setcdr | |
933 @subsection Altering the CDR of a List | |
934 | |
935 The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}: | |
936 | |
937 @defun setcdr cons object | |
938 This function stores @var{object} as the new @sc{cdr} of @var{cons}, | |
939 replacing its previous @sc{cdr}. In other words, it changes the | |
940 @sc{cdr} slot of @var{cons} to refer to @var{object}. It returns the | |
941 value @var{object}. | |
942 @end defun | |
943 | |
944 Here is an example of replacing the @sc{cdr} of a list with a | |
945 different list. All but the first element of the list are removed in | |
946 favor of a different sequence of elements. The first element is | |
947 unchanged, because it resides in the @sc{car} of the list, and is not | |
948 reached via the @sc{cdr}. | |
949 | |
950 @example | |
951 @group | |
952 (setq x '(1 2 3)) | |
953 @result{} (1 2 3) | |
954 @end group | |
955 @group | |
956 (setcdr x '(4)) | |
957 @result{} (4) | |
958 @end group | |
959 @group | |
960 x | |
961 @result{} (1 4) | |
962 @end group | |
963 @end example | |
964 | |
965 You can delete elements from the middle of a list by altering the | |
966 @sc{cdr}s of the cons cells in the list. For example, here we delete | |
967 the second element, @code{b}, from the list @code{(a b c)}, by changing | |
968 the @sc{cdr} of the first cons cell: | |
969 | |
970 @example | |
971 @group | |
972 (setq x1 '(a b c)) | |
973 @result{} (a b c) | |
974 (setcdr x1 (cdr (cdr x1))) | |
975 @result{} (c) | |
976 x1 | |
977 @result{} (a c) | |
978 @end group | |
979 @end example | |
980 | |
981 Here is the result in box notation: | |
982 | |
983 @smallexample | |
984 @group | |
985 -------------------- | |
986 | | | |
987 -------------- | -------------- | -------------- | |
988 | car | cdr | | | car | cdr | -->| car | cdr | | |
989 | a | o----- | b | o-------->| c | nil | | |
990 | | | | | | | | | | |
991 -------------- -------------- -------------- | |
992 @end group | |
993 @end smallexample | |
994 | |
995 @noindent | |
996 The second cons cell, which previously held the element @code{b}, still | |
997 exists and its @sc{car} is still @code{b}, but it no longer forms part | |
998 of this list. | |
999 | |
1000 It is equally easy to insert a new element by changing @sc{cdr}s: | |
1001 | |
1002 @example | |
1003 @group | |
1004 (setq x1 '(a b c)) | |
1005 @result{} (a b c) | |
1006 (setcdr x1 (cons 'd (cdr x1))) | |
1007 @result{} (d b c) | |
1008 x1 | |
1009 @result{} (a d b c) | |
1010 @end group | |
1011 @end example | |
1012 | |
1013 Here is this result in box notation: | |
1014 | |
1015 @smallexample | |
1016 @group | |
1017 -------------- ------------- ------------- | |
1018 | car | cdr | | car | cdr | | car | cdr | | |
1019 | a | o | -->| b | o------->| c | nil | | |
1020 | | | | | | | | | | | | |
1021 --------- | -- | ------------- ------------- | |
1022 | | | |
1023 ----- -------- | |
1024 | | | |
1025 | --------------- | | |
1026 | | car | cdr | | | |
1027 -->| d | o------ | |
1028 | | | | |
1029 --------------- | |
1030 @end group | |
1031 @end smallexample | |
1032 | |
1033 @node Rearrangement | |
1034 @subsection Functions that Rearrange Lists | |
1035 @cindex rearrangement of lists | |
1036 @cindex modification of lists | |
1037 | |
1038 Here are some functions that rearrange lists ``destructively'' by | |
1039 modifying the @sc{cdr}s of their component cons cells. We call these | |
1040 functions ``destructive'' because they chew up the original lists passed | |
1041 to them as arguments, relinking their cons cells to form a new list that | |
1042 is the returned value. | |
1043 | |
1044 @ifnottex | |
1045 See @code{delq}, in @ref{Sets And Lists}, for another function | |
1046 that modifies cons cells. | |
1047 @end ifnottex | |
1048 @iftex | |
1049 The function @code{delq} in the following section is another example | |
1050 of destructive list manipulation. | |
1051 @end iftex | |
1052 | |
1053 @defun nconc &rest lists | |
1054 @cindex concatenating lists | |
1055 @cindex joining lists | |
1056 This function returns a list containing all the elements of @var{lists}. | |
1057 Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are | |
1058 @emph{not} copied. Instead, the last @sc{cdr} of each of the | |
1059 @var{lists} is changed to refer to the following list. The last of the | |
1060 @var{lists} is not altered. For example: | |
1061 | |
1062 @example | |
1063 @group | |
1064 (setq x '(1 2 3)) | |
1065 @result{} (1 2 3) | |
1066 @end group | |
1067 @group | |
1068 (nconc x '(4 5)) | |
1069 @result{} (1 2 3 4 5) | |
1070 @end group | |
1071 @group | |
1072 x | |
1073 @result{} (1 2 3 4 5) | |
1074 @end group | |
1075 @end example | |
1076 | |
1077 Since the last argument of @code{nconc} is not itself modified, it is | |
1078 reasonable to use a constant list, such as @code{'(4 5)}, as in the | |
1079 above example. For the same reason, the last argument need not be a | |
1080 list: | |
1081 | |
1082 @example | |
1083 @group | |
1084 (setq x '(1 2 3)) | |
1085 @result{} (1 2 3) | |
1086 @end group | |
1087 @group | |
1088 (nconc x 'z) | |
1089 @result{} (1 2 3 . z) | |
1090 @end group | |
1091 @group | |
1092 x | |
1093 @result{} (1 2 3 . z) | |
1094 @end group | |
1095 @end example | |
1096 | |
1097 However, the other arguments (all but the last) must be lists. | |
1098 | |
1099 A common pitfall is to use a quoted constant list as a non-last | |
1100 argument to @code{nconc}. If you do this, your program will change | |
1101 each time you run it! Here is what happens: | |
1102 | |
1103 @smallexample | |
1104 @group | |
1105 (defun add-foo (x) ; @r{We want this function to add} | |
1106 (nconc '(foo) x)) ; @r{@code{foo} to the front of its arg.} | |
1107 @end group | |
1108 | |
1109 @group | |
1110 (symbol-function 'add-foo) | |
1111 @result{} (lambda (x) (nconc (quote (foo)) x)) | |
1112 @end group | |
1113 | |
1114 @group | |
1115 (setq xx (add-foo '(1 2))) ; @r{It seems to work.} | |
1116 @result{} (foo 1 2) | |
1117 @end group | |
1118 @group | |
1119 (setq xy (add-foo '(3 4))) ; @r{What happened?} | |
1120 @result{} (foo 1 2 3 4) | |
1121 @end group | |
1122 @group | |
1123 (eq xx xy) | |
1124 @result{} t | |
1125 @end group | |
1126 | |
1127 @group | |
1128 (symbol-function 'add-foo) | |
1129 @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x))) | |
1130 @end group | |
1131 @end smallexample | |
1132 @end defun | |
1133 | |
1134 @defun nreverse list | |
1135 @cindex reversing a list | |
1136 This function reverses the order of the elements of @var{list}. | |
1137 Unlike @code{reverse}, @code{nreverse} alters its argument by reversing | |
1138 the @sc{cdr}s in the cons cells forming the list. The cons cell that | |
1139 used to be the last one in @var{list} becomes the first cons cell of the | |
1140 value. | |
1141 | |
1142 For example: | |
1143 | |
1144 @example | |
1145 @group | |
1146 (setq x '(a b c)) | |
1147 @result{} (a b c) | |
1148 @end group | |
1149 @group | |
1150 x | |
1151 @result{} (a b c) | |
1152 (nreverse x) | |
1153 @result{} (c b a) | |
1154 @end group | |
1155 @group | |
1156 ;; @r{The cons cell that was first is now last.} | |
1157 x | |
1158 @result{} (a) | |
1159 @end group | |
1160 @end example | |
1161 | |
1162 To avoid confusion, we usually store the result of @code{nreverse} | |
1163 back in the same variable which held the original list: | |
1164 | |
1165 @example | |
1166 (setq x (nreverse x)) | |
1167 @end example | |
1168 | |
1169 Here is the @code{nreverse} of our favorite example, @code{(a b c)}, | |
1170 presented graphically: | |
1171 | |
1172 @smallexample | |
1173 @group | |
1174 @r{Original list head:} @r{Reversed list:} | |
1175 ------------- ------------- ------------ | |
1176 | car | cdr | | car | cdr | | car | cdr | | |
1177 | a | nil |<-- | b | o |<-- | c | o | | |
1178 | | | | | | | | | | | | | | |
1179 ------------- | --------- | - | -------- | - | |
1180 | | | | | |
1181 ------------- ------------ | |
1182 @end group | |
1183 @end smallexample | |
1184 @end defun | |
1185 | |
1186 @defun sort list predicate | |
1187 @cindex stable sort | |
1188 @cindex sorting lists | |
1189 This function sorts @var{list} stably, though destructively, and | |
1190 returns the sorted list. It compares elements using @var{predicate}. A | |
1191 stable sort is one in which elements with equal sort keys maintain their | |
1192 relative order before and after the sort. Stability is important when | |
1193 successive sorts are used to order elements according to different | |
1194 criteria. | |
1195 | |
1196 The argument @var{predicate} must be a function that accepts two | |
1197 arguments. It is called with two elements of @var{list}. To get an | |
1198 increasing order sort, the @var{predicate} should return non-@code{nil} if the | |
1199 first element is ``less than'' the second, or @code{nil} if not. | |
1200 | |
1201 The comparison function @var{predicate} must give reliable results for | |
1202 any given pair of arguments, at least within a single call to | |
1203 @code{sort}. It must be @dfn{antisymmetric}; that is, if @var{a} is | |
1204 less than @var{b}, @var{b} must not be less than @var{a}. It must be | |
1205 @dfn{transitive}---that is, if @var{a} is less than @var{b}, and @var{b} | |
1206 is less than @var{c}, then @var{a} must be less than @var{c}. If you | |
1207 use a comparison function which does not meet these requirements, the | |
1208 result of @code{sort} is unpredictable. | |
1209 | |
1210 The destructive aspect of @code{sort} is that it rearranges the cons | |
1211 cells forming @var{list} by changing @sc{cdr}s. A nondestructive sort | |
1212 function would create new cons cells to store the elements in their | |
1213 sorted order. If you wish to make a sorted copy without destroying the | |
1214 original, copy it first with @code{copy-sequence} and then sort. | |
1215 | |
1216 Sorting does not change the @sc{car}s of the cons cells in @var{list}; | |
1217 the cons cell that originally contained the element @code{a} in | |
1218 @var{list} still has @code{a} in its @sc{car} after sorting, but it now | |
1219 appears in a different position in the list due to the change of | |
1220 @sc{cdr}s. For example: | |
1221 | |
1222 @example | |
1223 @group | |
1224 (setq nums '(1 3 2 6 5 4 0)) | |
1225 @result{} (1 3 2 6 5 4 0) | |
1226 @end group | |
1227 @group | |
1228 (sort nums '<) | |
1229 @result{} (0 1 2 3 4 5 6) | |
1230 @end group | |
1231 @group | |
1232 nums | |
1233 @result{} (1 2 3 4 5 6) | |
1234 @end group | |
1235 @end example | |
1236 | |
1237 @noindent | |
1238 @strong{Warning}: Note that the list in @code{nums} no longer contains | |
1239 0; this is the same cons cell that it was before, but it is no longer | |
1240 the first one in the list. Don't assume a variable that formerly held | |
1241 the argument now holds the entire sorted list! Instead, save the result | |
1242 of @code{sort} and use that. Most often we store the result back into | |
1243 the variable that held the original list: | |
1244 | |
1245 @example | |
1246 (setq nums (sort nums '<)) | |
1247 @end example | |
1248 | |
1249 @xref{Sorting}, for more functions that perform sorting. | |
1250 See @code{documentation} in @ref{Accessing Documentation}, for a | |
1251 useful example of @code{sort}. | |
1252 @end defun | |
1253 | |
1254 @node Sets And Lists | |
1255 @section Using Lists as Sets | |
1256 @cindex lists as sets | |
1257 @cindex sets | |
1258 | |
1259 A list can represent an unordered mathematical set---simply consider a | |
1260 value an element of a set if it appears in the list, and ignore the | |
1261 order of the list. To form the union of two sets, use @code{append} (as | |
1262 long as you don't mind having duplicate elements). You can remove | |
1263 @code{equal} duplicates using @code{delete-dups}. Other useful | |
1264 functions for sets include @code{memq} and @code{delq}, and their | |
1265 @code{equal} versions, @code{member} and @code{delete}. | |
1266 | |
1267 @cindex CL note---lack @code{union}, @code{intersection} | |
1268 @quotation | |
1269 @b{Common Lisp note:} Common Lisp has functions @code{union} (which | |
1270 avoids duplicate elements) and @code{intersection} for set operations, | |
1271 but GNU Emacs Lisp does not have them. You can write them in Lisp if | |
1272 you wish. | |
1273 @end quotation | |
1274 | |
1275 @defun memq object list | |
1276 @cindex membership in a list | |
1277 This function tests to see whether @var{object} is a member of | |
1278 @var{list}. If it is, @code{memq} returns a list starting with the | |
1279 first occurrence of @var{object}. Otherwise, it returns @code{nil}. | |
1280 The letter @samp{q} in @code{memq} says that it uses @code{eq} to | |
1281 compare @var{object} against the elements of the list. For example: | |
1282 | |
1283 @example | |
1284 @group | |
1285 (memq 'b '(a b c b a)) | |
1286 @result{} (b c b a) | |
1287 @end group | |
1288 @group | |
1289 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.} | |
1290 @result{} nil | |
1291 @end group | |
1292 @end example | |
1293 @end defun | |
1294 | |
1295 @defun delq object list | |
1296 @cindex deleting list elements | |
1297 This function destructively removes all elements @code{eq} to | |
1298 @var{object} from @var{list}. The letter @samp{q} in @code{delq} says | |
1299 that it uses @code{eq} to compare @var{object} against the elements of | |
1300 the list, like @code{memq} and @code{remq}. | |
1301 @end defun | |
1302 | |
1303 When @code{delq} deletes elements from the front of the list, it does so | |
1304 simply by advancing down the list and returning a sublist that starts | |
1305 after those elements: | |
1306 | |
1307 @example | |
1308 @group | |
1309 (delq 'a '(a b c)) @equiv{} (cdr '(a b c)) | |
1310 @end group | |
1311 @end example | |
1312 | |
1313 When an element to be deleted appears in the middle of the list, | |
1314 removing it involves changing the @sc{cdr}s (@pxref{Setcdr}). | |
1315 | |
1316 @example | |
1317 @group | |
1318 (setq sample-list '(a b c (4))) | |
1319 @result{} (a b c (4)) | |
1320 @end group | |
1321 @group | |
1322 (delq 'a sample-list) | |
1323 @result{} (b c (4)) | |
1324 @end group | |
1325 @group | |
1326 sample-list | |
1327 @result{} (a b c (4)) | |
1328 @end group | |
1329 @group | |
1330 (delq 'c sample-list) | |
1331 @result{} (a b (4)) | |
1332 @end group | |
1333 @group | |
1334 sample-list | |
1335 @result{} (a b (4)) | |
1336 @end group | |
1337 @end example | |
1338 | |
1339 Note that @code{(delq 'c sample-list)} modifies @code{sample-list} to | |
1340 splice out the third element, but @code{(delq 'a sample-list)} does not | |
1341 splice anything---it just returns a shorter list. Don't assume that a | |
1342 variable which formerly held the argument @var{list} now has fewer | |
1343 elements, or that it still holds the original list! Instead, save the | |
1344 result of @code{delq} and use that. Most often we store the result back | |
1345 into the variable that held the original list: | |
1346 | |
1347 @example | |
1348 (setq flowers (delq 'rose flowers)) | |
1349 @end example | |
1350 | |
1351 In the following example, the @code{(4)} that @code{delq} attempts to match | |
1352 and the @code{(4)} in the @code{sample-list} are not @code{eq}: | |
1353 | |
1354 @example | |
1355 @group | |
1356 (delq '(4) sample-list) | |
1357 @result{} (a c (4)) | |
1358 @end group | |
1359 | |
1360 If you want to delete elements that are @code{equal} to a given value, | |
1361 use @code{delete} (see below). | |
1362 @end example | |
1363 | |
1364 @defun remq object list | |
1365 This function returns a copy of @var{list}, with all elements removed | |
1366 which are @code{eq} to @var{object}. The letter @samp{q} in @code{remq} | |
1367 says that it uses @code{eq} to compare @var{object} against the elements | |
1368 of @code{list}. | |
1369 | |
1370 @example | |
1371 @group | |
1372 (setq sample-list '(a b c a b c)) | |
1373 @result{} (a b c a b c) | |
1374 @end group | |
1375 @group | |
1376 (remq 'a sample-list) | |
1377 @result{} (b c b c) | |
1378 @end group | |
1379 @group | |
1380 sample-list | |
1381 @result{} (a b c a b c) | |
1382 @end group | |
1383 @end example | |
1384 @end defun | |
1385 | |
1386 @defun memql object list | |
1387 The function @code{memql} tests to see whether @var{object} is a member | |
1388 of @var{list}, comparing members with @var{object} using @code{eql}, | |
1389 so floating point elements are compared by value. | |
1390 If @var{object} is a member, @code{memql} returns a list starting with | |
1391 its first occurrence in @var{list}. Otherwise, it returns @code{nil}. | |
1392 | |
1393 Compare this with @code{memq}: | |
1394 | |
1395 @example | |
1396 @group | |
1397 (memql 1.2 '(1.1 1.2 1.3)) ; @r{@code{1.2} and @code{1.2} are @code{eql}.} | |
1398 @result{} (1.2 1.3) | |
1399 @end group | |
1400 @group | |
1401 (memq 1.2 '(1.1 1.2 1.3)) ; @r{@code{1.2} and @code{1.2} are not @code{eq}.} | |
1402 @result{} nil | |
1403 @end group | |
1404 @end example | |
1405 @end defun | |
1406 | |
1407 The following three functions are like @code{memq}, @code{delq} and | |
1408 @code{remq}, but use @code{equal} rather than @code{eq} to compare | |
1409 elements. @xref{Equality Predicates}. | |
1410 | |
1411 @defun member object list | |
1412 The function @code{member} tests to see whether @var{object} is a member | |
1413 of @var{list}, comparing members with @var{object} using @code{equal}. | |
1414 If @var{object} is a member, @code{member} returns a list starting with | |
1415 its first occurrence in @var{list}. Otherwise, it returns @code{nil}. | |
1416 | |
1417 Compare this with @code{memq}: | |
1418 | |
1419 @example | |
1420 @group | |
1421 (member '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are @code{equal}.} | |
1422 @result{} ((2)) | |
1423 @end group | |
1424 @group | |
1425 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.} | |
1426 @result{} nil | |
1427 @end group | |
1428 @group | |
1429 ;; @r{Two strings with the same contents are @code{equal}.} | |
1430 (member "foo" '("foo" "bar")) | |
1431 @result{} ("foo" "bar") | |
1432 @end group | |
1433 @end example | |
1434 @end defun | |
1435 | |
1436 @defun delete object sequence | |
1437 If @code{sequence} is a list, this function destructively removes all | |
1438 elements @code{equal} to @var{object} from @var{sequence}. For lists, | |
1439 @code{delete} is to @code{delq} as @code{member} is to @code{memq}: it | |
1440 uses @code{equal} to compare elements with @var{object}, like | |
1441 @code{member}; when it finds an element that matches, it cuts the | |
1442 element out just as @code{delq} would. | |
1443 | |
1444 If @code{sequence} is a vector or string, @code{delete} returns a copy | |
1445 of @code{sequence} with all elements @code{equal} to @code{object} | |
1446 removed. | |
1447 | |
1448 For example: | |
1449 | |
1450 @example | |
1451 @group | |
1452 (setq l '((2) (1) (2))) | |
1453 (delete '(2) l) | |
1454 @result{} ((1)) | |
1455 l | |
1456 @result{} ((2) (1)) | |
1457 ;; @r{If you want to change @code{l} reliably,} | |
1458 ;; @r{write @code{(setq l (delete elt l))}.} | |
1459 @end group | |
1460 @group | |
1461 (setq l '((2) (1) (2))) | |
1462 (delete '(1) l) | |
1463 @result{} ((2) (2)) | |
1464 l | |
1465 @result{} ((2) (2)) | |
1466 ;; @r{In this case, it makes no difference whether you set @code{l},} | |
1467 ;; @r{but you should do so for the sake of the other case.} | |
1468 @end group | |
1469 @group | |
1470 (delete '(2) [(2) (1) (2)]) | |
1471 @result{} [(1)] | |
1472 @end group | |
1473 @end example | |
1474 @end defun | |
1475 | |
1476 @defun remove object sequence | |
1477 This function is the non-destructive counterpart of @code{delete}. It | |
1478 returns a copy of @code{sequence}, a list, vector, or string, with | |
1479 elements @code{equal} to @code{object} removed. For example: | |
1480 | |
1481 @example | |
1482 @group | |
1483 (remove '(2) '((2) (1) (2))) | |
1484 @result{} ((1)) | |
1485 @end group | |
1486 @group | |
1487 (remove '(2) [(2) (1) (2)]) | |
1488 @result{} [(1)] | |
1489 @end group | |
1490 @end example | |
1491 @end defun | |
1492 | |
1493 @quotation | |
1494 @b{Common Lisp note:} The functions @code{member}, @code{delete} and | |
1495 @code{remove} in GNU Emacs Lisp are derived from Maclisp, not Common | |
1496 Lisp. The Common Lisp versions do not use @code{equal} to compare | |
1497 elements. | |
1498 @end quotation | |
1499 | |
1500 @defun member-ignore-case object list | |
1501 This function is like @code{member}, except that @var{object} should | |
1502 be a string and that it ignores differences in letter-case and text | |
1503 representation: upper-case and lower-case letters are treated as | |
1504 equal, and unibyte strings are converted to multibyte prior to | |
1505 comparison. | |
1506 @end defun | |
1507 | |
1508 @defun delete-dups list | |
1509 This function destructively removes all @code{equal} duplicates from | |
1510 @var{list}, stores the result in @var{list} and returns it. Of | |
1511 several @code{equal} occurrences of an element in @var{list}, | |
1512 @code{delete-dups} keeps the first one. | |
1513 @end defun | |
1514 | |
1515 See also the function @code{add-to-list}, in @ref{List Variables}, | |
1516 for a way to add an element to a list stored in a variable and used as a | |
1517 set. | |
1518 | |
1519 @node Association Lists | |
1520 @section Association Lists | |
1521 @cindex association list | |
1522 @cindex alist | |
1523 | |
1524 An @dfn{association list}, or @dfn{alist} for short, records a mapping | |
1525 from keys to values. It is a list of cons cells called | |
1526 @dfn{associations}: the @sc{car} of each cons cell is the @dfn{key}, and the | |
1527 @sc{cdr} is the @dfn{associated value}.@footnote{This usage of ``key'' | |
1528 is not related to the term ``key sequence''; it means a value used to | |
1529 look up an item in a table. In this case, the table is the alist, and | |
1530 the alist associations are the items.} | |
1531 | |
1532 Here is an example of an alist. The key @code{pine} is associated with | |
1533 the value @code{cones}; the key @code{oak} is associated with | |
1534 @code{acorns}; and the key @code{maple} is associated with @code{seeds}. | |
1535 | |
1536 @example | |
1537 @group | |
1538 ((pine . cones) | |
1539 (oak . acorns) | |
1540 (maple . seeds)) | |
1541 @end group | |
1542 @end example | |
1543 | |
1544 Both the values and the keys in an alist may be any Lisp objects. | |
1545 For example, in the following alist, the symbol @code{a} is | |
1546 associated with the number @code{1}, and the string @code{"b"} is | |
1547 associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of | |
1548 the alist element: | |
1549 | |
1550 @example | |
1551 ((a . 1) ("b" 2 3)) | |
1552 @end example | |
1553 | |
1554 Sometimes it is better to design an alist to store the associated | |
1555 value in the @sc{car} of the @sc{cdr} of the element. Here is an | |
1556 example of such an alist: | |
1557 | |
1558 @example | |
1559 ((rose red) (lily white) (buttercup yellow)) | |
1560 @end example | |
1561 | |
1562 @noindent | |
1563 Here we regard @code{red} as the value associated with @code{rose}. One | |
1564 advantage of this kind of alist is that you can store other related | |
1565 information---even a list of other items---in the @sc{cdr} of the | |
1566 @sc{cdr}. One disadvantage is that you cannot use @code{rassq} (see | |
1567 below) to find the element containing a given value. When neither of | |
1568 these considerations is important, the choice is a matter of taste, as | |
1569 long as you are consistent about it for any given alist. | |
1570 | |
1571 The same alist shown above could be regarded as having the | |
1572 associated value in the @sc{cdr} of the element; the value associated | |
1573 with @code{rose} would be the list @code{(red)}. | |
1574 | |
1575 Association lists are often used to record information that you might | |
1576 otherwise keep on a stack, since new associations may be added easily to | |
1577 the front of the list. When searching an association list for an | |
1578 association with a given key, the first one found is returned, if there | |
1579 is more than one. | |
1580 | |
1581 In Emacs Lisp, it is @emph{not} an error if an element of an | |
1582 association list is not a cons cell. The alist search functions simply | |
1583 ignore such elements. Many other versions of Lisp signal errors in such | |
1584 cases. | |
1585 | |
1586 Note that property lists are similar to association lists in several | |
1587 respects. A property list behaves like an association list in which | |
1588 each key can occur only once. @xref{Property Lists}, for a comparison | |
1589 of property lists and association lists. | |
1590 | |
1591 @defun assoc key alist | |
1592 This function returns the first association for @var{key} in | |
1593 @var{alist}, comparing @var{key} against the alist elements using | |
1594 @code{equal} (@pxref{Equality Predicates}). It returns @code{nil} if no | |
1595 association in @var{alist} has a @sc{car} @code{equal} to @var{key}. | |
1596 For example: | |
1597 | |
1598 @smallexample | |
1599 (setq trees '((pine . cones) (oak . acorns) (maple . seeds))) | |
1600 @result{} ((pine . cones) (oak . acorns) (maple . seeds)) | |
1601 (assoc 'oak trees) | |
1602 @result{} (oak . acorns) | |
1603 (cdr (assoc 'oak trees)) | |
1604 @result{} acorns | |
1605 (assoc 'birch trees) | |
1606 @result{} nil | |
1607 @end smallexample | |
1608 | |
1609 Here is another example, in which the keys and values are not symbols: | |
1610 | |
1611 @smallexample | |
1612 (setq needles-per-cluster | |
1613 '((2 "Austrian Pine" "Red Pine") | |
1614 (3 "Pitch Pine") | |
1615 (5 "White Pine"))) | |
1616 | |
1617 (cdr (assoc 3 needles-per-cluster)) | |
1618 @result{} ("Pitch Pine") | |
1619 (cdr (assoc 2 needles-per-cluster)) | |
1620 @result{} ("Austrian Pine" "Red Pine") | |
1621 @end smallexample | |
1622 @end defun | |
1623 | |
1624 The function @code{assoc-string} is much like @code{assoc} except | |
1625 that it ignores certain differences between strings. @xref{Text | |
1626 Comparison}. | |
1627 | |
1628 @defun rassoc value alist | |
1629 This function returns the first association with value @var{value} in | |
1630 @var{alist}. It returns @code{nil} if no association in @var{alist} has | |
1631 a @sc{cdr} @code{equal} to @var{value}. | |
1632 | |
1633 @code{rassoc} is like @code{assoc} except that it compares the @sc{cdr} of | |
1634 each @var{alist} association instead of the @sc{car}. You can think of | |
1635 this as ``reverse @code{assoc},'' finding the key for a given value. | |
1636 @end defun | |
1637 | |
1638 @defun assq key alist | |
1639 This function is like @code{assoc} in that it returns the first | |
1640 association for @var{key} in @var{alist}, but it makes the comparison | |
1641 using @code{eq} instead of @code{equal}. @code{assq} returns @code{nil} | |
1642 if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}. | |
1643 This function is used more often than @code{assoc}, since @code{eq} is | |
1644 faster than @code{equal} and most alists use symbols as keys. | |
1645 @xref{Equality Predicates}. | |
1646 | |
1647 @smallexample | |
1648 (setq trees '((pine . cones) (oak . acorns) (maple . seeds))) | |
1649 @result{} ((pine . cones) (oak . acorns) (maple . seeds)) | |
1650 (assq 'pine trees) | |
1651 @result{} (pine . cones) | |
1652 @end smallexample | |
1653 | |
1654 On the other hand, @code{assq} is not usually useful in alists where the | |
1655 keys may not be symbols: | |
1656 | |
1657 @smallexample | |
1658 (setq leaves | |
1659 '(("simple leaves" . oak) | |
1660 ("compound leaves" . horsechestnut))) | |
1661 | |
1662 (assq "simple leaves" leaves) | |
1663 @result{} nil | |
1664 (assoc "simple leaves" leaves) | |
1665 @result{} ("simple leaves" . oak) | |
1666 @end smallexample | |
1667 @end defun | |
1668 | |
1669 @defun rassq value alist | |
1670 This function returns the first association with value @var{value} in | |
1671 @var{alist}. It returns @code{nil} if no association in @var{alist} has | |
1672 a @sc{cdr} @code{eq} to @var{value}. | |
1673 | |
1674 @code{rassq} is like @code{assq} except that it compares the @sc{cdr} of | |
1675 each @var{alist} association instead of the @sc{car}. You can think of | |
1676 this as ``reverse @code{assq},'' finding the key for a given value. | |
1677 | |
1678 For example: | |
1679 | |
1680 @smallexample | |
1681 (setq trees '((pine . cones) (oak . acorns) (maple . seeds))) | |
1682 | |
1683 (rassq 'acorns trees) | |
1684 @result{} (oak . acorns) | |
1685 (rassq 'spores trees) | |
1686 @result{} nil | |
1687 @end smallexample | |
1688 | |
1689 @code{rassq} cannot search for a value stored in the @sc{car} | |
1690 of the @sc{cdr} of an element: | |
1691 | |
1692 @smallexample | |
1693 (setq colors '((rose red) (lily white) (buttercup yellow))) | |
1694 | |
1695 (rassq 'white colors) | |
1696 @result{} nil | |
1697 @end smallexample | |
1698 | |
1699 In this case, the @sc{cdr} of the association @code{(lily white)} is not | |
1700 the symbol @code{white}, but rather the list @code{(white)}. This | |
1701 becomes clearer if the association is written in dotted pair notation: | |
1702 | |
1703 @smallexample | |
1704 (lily white) @equiv{} (lily . (white)) | |
1705 @end smallexample | |
1706 @end defun | |
1707 | |
1708 @defun assoc-default key alist &optional test default | |
1709 This function searches @var{alist} for a match for @var{key}. For each | |
1710 element of @var{alist}, it compares the element (if it is an atom) or | |
1711 the element's @sc{car} (if it is a cons) against @var{key}, by calling | |
1712 @var{test} with two arguments: the element or its @sc{car}, and | |
1713 @var{key}. The arguments are passed in that order so that you can get | |
1714 useful results using @code{string-match} with an alist that contains | |
1715 regular expressions (@pxref{Regexp Search}). If @var{test} is omitted | |
1716 or @code{nil}, @code{equal} is used for comparison. | |
1717 | |
1718 If an alist element matches @var{key} by this criterion, | |
1719 then @code{assoc-default} returns a value based on this element. | |
1720 If the element is a cons, then the value is the element's @sc{cdr}. | |
1721 Otherwise, the return value is @var{default}. | |
1722 | |
1723 If no alist element matches @var{key}, @code{assoc-default} returns | |
1724 @code{nil}. | |
1725 @end defun | |
1726 | |
1727 @defun copy-alist alist | |
1728 @cindex copying alists | |
1729 This function returns a two-level deep copy of @var{alist}: it creates a | |
1730 new copy of each association, so that you can alter the associations of | |
1731 the new alist without changing the old one. | |
1732 | |
1733 @smallexample | |
1734 @group | |
1735 (setq needles-per-cluster | |
1736 '((2 . ("Austrian Pine" "Red Pine")) | |
1737 (3 . ("Pitch Pine")) | |
1738 @end group | |
1739 (5 . ("White Pine")))) | |
1740 @result{} | |
1741 ((2 "Austrian Pine" "Red Pine") | |
1742 (3 "Pitch Pine") | |
1743 (5 "White Pine")) | |
1744 | |
1745 (setq copy (copy-alist needles-per-cluster)) | |
1746 @result{} | |
1747 ((2 "Austrian Pine" "Red Pine") | |
1748 (3 "Pitch Pine") | |
1749 (5 "White Pine")) | |
1750 | |
1751 (eq needles-per-cluster copy) | |
1752 @result{} nil | |
1753 (equal needles-per-cluster copy) | |
1754 @result{} t | |
1755 (eq (car needles-per-cluster) (car copy)) | |
1756 @result{} nil | |
1757 (cdr (car (cdr needles-per-cluster))) | |
1758 @result{} ("Pitch Pine") | |
1759 @group | |
1760 (eq (cdr (car (cdr needles-per-cluster))) | |
1761 (cdr (car (cdr copy)))) | |
1762 @result{} t | |
1763 @end group | |
1764 @end smallexample | |
1765 | |
1766 This example shows how @code{copy-alist} makes it possible to change | |
1767 the associations of one copy without affecting the other: | |
1768 | |
1769 @smallexample | |
1770 @group | |
1771 (setcdr (assq 3 copy) '("Martian Vacuum Pine")) | |
1772 (cdr (assq 3 needles-per-cluster)) | |
1773 @result{} ("Pitch Pine") | |
1774 @end group | |
1775 @end smallexample | |
1776 @end defun | |
1777 | |
1778 @defun assq-delete-all key alist | |
1779 This function deletes from @var{alist} all the elements whose @sc{car} | |
1780 is @code{eq} to @var{key}, much as if you used @code{delq} to delete | |
1781 each such element one by one. It returns the shortened alist, and | |
1782 often modifies the original list structure of @var{alist}. For | |
1783 correct results, use the return value of @code{assq-delete-all} rather | |
1784 than looking at the saved value of @var{alist}. | |
1785 | |
1786 @example | |
1787 (setq alist '((foo 1) (bar 2) (foo 3) (lose 4))) | |
1788 @result{} ((foo 1) (bar 2) (foo 3) (lose 4)) | |
1789 (assq-delete-all 'foo alist) | |
1790 @result{} ((bar 2) (lose 4)) | |
1791 alist | |
1792 @result{} ((foo 1) (bar 2) (lose 4)) | |
1793 @end example | |
1794 @end defun | |
1795 | |
1796 @defun rassq-delete-all value alist | |
1797 This function deletes from @var{alist} all the elements whose @sc{cdr} | |
1798 is @code{eq} to @var{value}. It returns the shortened alist, and | |
1799 often modifies the original list structure of @var{alist}. | |
1800 @code{rassq-delete-all} is like @code{assq-delete-all} except that it | |
1801 compares the @sc{cdr} of each @var{alist} association instead of the | |
1802 @sc{car}. | |
1803 @end defun | |
1804 | |
1805 @node Rings | |
1806 @section Managing a Fixed-Size Ring of Objects | |
1807 | |
1808 @cindex ring data structure | |
1809 This section describes functions for operating on rings. A | |
1810 @dfn{ring} is a fixed-size data structure that supports insertion, | |
1811 deletion, rotation, and modulo-indexed reference and traversal. | |
1812 | |
1813 @defun make-ring size | |
1814 This returns a new ring capable of holding @var{size} objects. | |
1815 @var{size} should be an integer. | |
1816 @end defun | |
1817 | |
1818 @defun ring-p object | |
1819 This returns @code{t} if @var{object} is a ring, @code{nil} otherwise. | |
1820 @end defun | |
1821 | |
1822 @defun ring-size ring | |
1823 This returns the maximum capacity of the @var{ring}. | |
1824 @end defun | |
1825 | |
1826 @defun ring-length ring | |
1827 This returns the number of objects that @var{ring} currently contains. | |
1828 The value will never exceed that returned by @code{ring-size}. | |
1829 @end defun | |
1830 | |
1831 @defun ring-elements ring | |
1832 This returns a list of the objects in @var{ring}, in order, newest first. | |
1833 @end defun | |
1834 | |
1835 @defun ring-copy ring | |
1836 This returns a new ring which is a copy of @var{ring}. | |
1837 The new ring contains the same (@code{eq}) objects as @var{ring}. | |
1838 @end defun | |
1839 | |
1840 @defun ring-empty-p ring | |
1841 This returns @code{t} if @var{ring} is empty, @code{nil} otherwise. | |
1842 @end defun | |
1843 | |
1844 The newest element in the ring always has index 0. Higher indices | |
1845 correspond to older elements. Indices are computed modulo the ring | |
1846 length. Index @minus{}1 corresponds to the oldest element, @minus{}2 | |
1847 to the next-oldest, and so forth. | |
1848 | |
1849 @defun ring-ref ring index | |
1850 This returns the object in @var{ring} found at index @var{index}. | |
1851 @var{index} may be negative or greater than the ring length. If | |
1852 @var{ring} is empty, @code{ring-ref} signals an error. | |
1853 @end defun | |
1854 | |
1855 @defun ring-insert ring object | |
1856 This inserts @var{object} into @var{ring}, making it the newest | |
1857 element, and returns @var{object}. | |
1858 | |
1859 If the ring is full, insertion removes the oldest element to | |
1860 make room for the new element. | |
1861 @end defun | |
1862 | |
1863 @defun ring-remove ring &optional index | |
1864 Remove an object from @var{ring}, and return that object. The | |
1865 argument @var{index} specifies which item to remove; if it is | |
1866 @code{nil}, that means to remove the oldest item. If @var{ring} is | |
1867 empty, @code{ring-remove} signals an error. | |
1868 @end defun | |
1869 | |
1870 @defun ring-insert-at-beginning ring object | |
1871 This inserts @var{object} into @var{ring}, treating it as the oldest | |
1872 element. The return value is not significant. | |
1873 | |
1874 If the ring is full, this function removes the newest element to make | |
1875 room for the inserted element. | |
1876 @end defun | |
1877 | |
1878 @cindex fifo data structure | |
1879 If you are careful not to exceed the ring size, you can | |
1880 use the ring as a first-in-first-out queue. For example: | |
1881 | |
1882 @lisp | |
1883 (let ((fifo (make-ring 5))) | |
1884 (mapc (lambda (obj) (ring-insert fifo obj)) | |
1885 '(0 one "two")) | |
1886 (list (ring-remove fifo) t | |
1887 (ring-remove fifo) t | |
1888 (ring-remove fifo))) | |
1889 @result{} (0 t one t "two") | |
1890 @end lisp | |
1891 | |
1892 @ignore | |
1893 arch-tag: 31fb8a4e-4aa8-4a74-a206-aa00451394d4 | |
1894 @end ignore |