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