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