Mercurial > emacs
annotate lispref/lists.texi @ 9526:c84536ef5fa9
(x_new_font): Don't keep looping after the FONT property.
author | Richard M. Stallman <rms@gnu.org> |
---|---|
date | Fri, 14 Oct 1994 04:45:04 +0000 |
parents | 2d4db32cccd5 |
children | 206af14bcffa |
rev | line source |
---|---|
6558 | 1 @c -*-texinfo-*- |
2 @c This is part of the GNU Emacs Lisp Reference Manual. | |
3 @c Copyright (C) 1990, 1991, 1992, 1993, 1994 Free Software Foundation, Inc. | |
4 @c See the file elisp.texi for copying conditions. | |
5 @setfilename ../info/lists | |
6 @node Lists, Sequences Arrays Vectors, Strings and Characters, Top | |
7 @chapter Lists | |
8 @cindex list | |
9 @cindex element (of list) | |
10 | |
11 A @dfn{list} represents a sequence of zero or more elements (which may | |
12 be any Lisp objects). The important difference between lists and | |
13 vectors is that two or more lists can share part of their structure; in | |
14 addition, you can insert or delete elements in a list without copying | |
15 the whole list. | |
16 | |
17 @menu | |
18 * Cons Cells:: How lists are made out of cons cells. | |
19 * Lists as Boxes:: Graphical notation to explain lists. | |
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 * Modifying Lists:: Storing new pieces into an existing list. | |
24 * Sets And Lists:: A list can represent a finite mathematical set. | |
25 * Association Lists:: A list can represent a finite relation or mapping. | |
26 @end menu | |
27 | |
28 @node Cons Cells | |
29 @section Lists and Cons Cells | |
30 @cindex lists and cons cells | |
31 @cindex @code{nil} and lists | |
32 | |
33 Lists in Lisp are not a primitive data type; they are built up from | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
34 @dfn{cons cells}. A cons cell is a data object that represents an |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
35 ordered pair. It records two Lisp objects, one labeled as the @sc{car}, |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
36 and the other labeled as the @sc{cdr}. These names are traditional; see |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
37 @ref{Cons Cell Type}. @sc{cdr} is pronounced ``could-er.'' |
6558 | 38 |
39 A list is a series of cons cells chained together, one cons cell per | |
40 element of the list. By convention, the @sc{car}s of the cons cells are | |
41 the elements of the list, and the @sc{cdr}s are used to chain the list: | |
42 the @sc{cdr} of each cons cell is the following cons cell. The @sc{cdr} | |
43 of the last cons cell is @code{nil}. This asymmetry between the | |
44 @sc{car} and the @sc{cdr} is entirely a matter of convention; at the | |
45 level of cons cells, the @sc{car} and @sc{cdr} slots have the same | |
46 characteristics. | |
47 | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
48 @cindex list structure |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
49 Because most cons cells are used as part of lists, the phrase |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
50 @dfn{list structure} has come to mean any structure made out of cons |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
51 cells. |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
52 |
6558 | 53 The symbol @code{nil} is considered a list as well as a symbol; it is |
54 the list with no elements. For convenience, the symbol @code{nil} is | |
55 considered to have @code{nil} as its @sc{cdr} (and also as its | |
56 @sc{car}). | |
57 | |
58 The @sc{cdr} of any nonempty list @var{l} is a list containing all the | |
59 elements of @var{l} except the first. | |
60 | |
61 @node Lists as Boxes | |
62 @comment node-name, next, previous, up | |
63 @section Lists as Linked Pairs of Boxes | |
64 @cindex box representation for lists | |
65 @cindex lists represented as boxes | |
66 @cindex cons cell as box | |
67 | |
68 A cons cell can be illustrated as a pair of boxes. The first box | |
69 represents the @sc{car} and the second box represents the @sc{cdr}. | |
70 Here is an illustration of the two-element list, @code{(tulip lily)}, | |
71 made from two cons cells: | |
72 | |
73 @example | |
74 @group | |
75 --------------- --------------- | |
76 | car | cdr | | car | cdr | | |
77 | tulip | o---------->| lily | nil | | |
78 | | | | | | | |
79 --------------- --------------- | |
80 @end group | |
81 @end example | |
82 | |
83 Each pair of boxes represents a cons cell. Each box ``refers to'', | |
84 ``points to'' or ``contains'' a Lisp object. (These terms are | |
85 synonymous.) The first box, which is the @sc{car} of the first cons | |
86 cell, contains the symbol @code{tulip}. The arrow from the @sc{cdr} of | |
87 the first cons cell to the second cons cell indicates that the @sc{cdr} | |
88 of the first cons cell points to the second cons cell. | |
89 | |
90 The same list can be illustrated in a different sort of box notation | |
91 like this: | |
92 | |
93 @example | |
94 @group | |
95 ___ ___ ___ ___ | |
96 |___|___|--> |___|___|--> nil | |
97 | | | |
98 | | | |
99 --> tulip --> lily | |
100 @end group | |
101 @end example | |
102 | |
103 Here is a more complex illustration, showing the three-element list, | |
104 @code{((pine needles) oak maple)}, the first element of which is a | |
105 two-element list: | |
106 | |
107 @example | |
108 @group | |
109 ___ ___ ___ ___ ___ ___ | |
110 |___|___|--> |___|___|--> |___|___|--> nil | |
111 | | | | |
112 | | | | |
113 | --> oak --> maple | |
114 | | |
115 | ___ ___ ___ ___ | |
116 --> |___|___|--> |___|___|--> nil | |
117 | | | |
118 | | | |
119 --> pine --> needles | |
120 @end group | |
121 @end example | |
122 | |
123 The same list represented in the first box notation looks like this: | |
124 | |
125 @example | |
126 @group | |
127 -------------- -------------- -------------- | |
128 | car | cdr | | car | cdr | | car | cdr | | |
129 | o | o------->| oak | o------->| maple | nil | | |
130 | | | | | | | | | | | |
131 -- | --------- -------------- -------------- | |
132 | | |
133 | | |
134 | -------------- ---------------- | |
135 | | car | cdr | | car | cdr | | |
136 ------>| pine | o------->| needles | nil | | |
137 | | | | | | | |
138 -------------- ---------------- | |
139 @end group | |
140 @end example | |
141 | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
142 @xref{Cons Cell Type}, for the read and print syntax of cons cells and |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
143 lists, and for more ``box and arrow'' illustrations of lists. |
6558 | 144 |
145 @node List-related Predicates | |
146 @section Predicates on Lists | |
147 | |
148 The following predicates test whether a Lisp object is an atom, is a | |
149 cons cell or is a list, or whether it is the distinguished object | |
150 @code{nil}. (Many of these predicates can be defined in terms of the | |
151 others, but they are used so often that it is worth having all of them.) | |
152 | |
153 @defun consp object | |
154 This function returns @code{t} if @var{object} is a cons cell, @code{nil} | |
155 otherwise. @code{nil} is not a cons cell, although it @emph{is} a list. | |
156 @end defun | |
157 | |
158 @defun atom object | |
159 @cindex atoms | |
160 This function returns @code{t} if @var{object} is an atom, @code{nil} | |
161 otherwise. All objects except cons cells are atoms. The symbol | |
162 @code{nil} is an atom and is also a list; it is the only Lisp object | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
163 that is both. |
6558 | 164 |
165 @example | |
166 (atom @var{object}) @equiv{} (not (consp @var{object})) | |
167 @end example | |
168 @end defun | |
169 | |
170 @defun listp object | |
171 This function returns @code{t} if @var{object} is a cons cell or | |
172 @code{nil}. Otherwise, it returns @code{nil}. | |
173 | |
174 @example | |
175 @group | |
176 (listp '(1)) | |
177 @result{} t | |
178 @end group | |
179 @group | |
180 (listp '()) | |
181 @result{} t | |
182 @end group | |
183 @end example | |
184 @end defun | |
185 | |
186 @defun nlistp object | |
187 This function is the opposite of @code{listp}: it returns @code{t} if | |
188 @var{object} is not a list. Otherwise, it returns @code{nil}. | |
189 | |
190 @example | |
191 (listp @var{object}) @equiv{} (not (nlistp @var{object})) | |
192 @end example | |
193 @end defun | |
194 | |
195 @defun null object | |
196 This function returns @code{t} if @var{object} is @code{nil}, and | |
197 returns @code{nil} otherwise. This function is identical to @code{not}, | |
198 but as a matter of clarity we use @code{null} when @var{object} is | |
199 considered a list and @code{not} when it is considered a truth value | |
200 (see @code{not} in @ref{Combining Conditions}). | |
201 | |
202 @example | |
203 @group | |
204 (null '(1)) | |
205 @result{} nil | |
206 @end group | |
207 @group | |
208 (null '()) | |
209 @result{} t | |
210 @end group | |
211 @end example | |
212 @end defun | |
213 | |
7734 | 214 @need 2000 |
6558 | 215 |
216 @node List Elements | |
217 @section Accessing Elements of Lists | |
218 @cindex list elements | |
219 | |
220 @defun car cons-cell | |
221 This function returns the value pointed to by the first pointer of the | |
222 cons cell @var{cons-cell}. Expressed another way, this function | |
223 returns the @sc{car} of @var{cons-cell}. | |
224 | |
225 As a special case, if @var{cons-cell} is @code{nil}, then @code{car} | |
226 is defined to return @code{nil}; therefore, any list is a valid argument | |
227 for @code{car}. An error is signaled if the argument is not a cons cell | |
228 or @code{nil}. | |
229 | |
230 @example | |
231 @group | |
232 (car '(a b c)) | |
233 @result{} a | |
234 @end group | |
235 @group | |
236 (car '()) | |
237 @result{} nil | |
238 @end group | |
239 @end example | |
240 @end defun | |
241 | |
242 @defun cdr cons-cell | |
243 This function returns the value pointed to by the second pointer of | |
244 the cons cell @var{cons-cell}. Expressed another way, this function | |
245 returns the @sc{cdr} of @var{cons-cell}. | |
246 | |
247 As a special case, if @var{cons-cell} is @code{nil}, then @code{cdr} | |
248 is defined to return @code{nil}; therefore, any list is a valid argument | |
249 for @code{cdr}. An error is signaled if the argument is not a cons cell | |
250 or @code{nil}. | |
251 | |
252 @example | |
253 @group | |
254 (cdr '(a b c)) | |
255 @result{} (b c) | |
256 @end group | |
257 @group | |
258 (cdr '()) | |
259 @result{} nil | |
260 @end group | |
261 @end example | |
262 @end defun | |
263 | |
264 @defun car-safe object | |
265 This function lets you take the @sc{car} of a cons cell while avoiding | |
266 errors for other data types. It returns the @sc{car} of @var{object} if | |
267 @var{object} is a cons cell, @code{nil} otherwise. This is in contrast | |
268 to @code{car}, which signals an error if @var{object} is not a list. | |
269 | |
270 @example | |
271 @group | |
272 (car-safe @var{object}) | |
273 @equiv{} | |
274 (let ((x @var{object})) | |
275 (if (consp x) | |
276 (car x) | |
277 nil)) | |
278 @end group | |
279 @end example | |
280 @end defun | |
281 | |
282 @defun cdr-safe object | |
283 This function lets you take the @sc{cdr} of a cons cell while | |
284 avoiding errors for other data types. It returns the @sc{cdr} of | |
285 @var{object} if @var{object} is a cons cell, @code{nil} otherwise. | |
286 This is in contrast to @code{cdr}, which signals an error if | |
287 @var{object} is not a list. | |
288 | |
289 @example | |
290 @group | |
291 (cdr-safe @var{object}) | |
292 @equiv{} | |
293 (let ((x @var{object})) | |
294 (if (consp x) | |
295 (cdr x) | |
296 nil)) | |
297 @end group | |
298 @end example | |
299 @end defun | |
300 | |
301 @defun nth n list | |
302 This function returns the @var{n}th element of @var{list}. Elements | |
303 are numbered starting with zero, so the @sc{car} of @var{list} is | |
304 element number zero. If the length of @var{list} is @var{n} or less, | |
305 the value is @code{nil}. | |
306 | |
307 If @var{n} is negative, @code{nth} returns the first element of | |
308 @var{list}. | |
309 | |
310 @example | |
311 @group | |
312 (nth 2 '(1 2 3 4)) | |
313 @result{} 3 | |
314 @end group | |
315 @group | |
316 (nth 10 '(1 2 3 4)) | |
317 @result{} nil | |
318 @end group | |
319 @group | |
320 (nth -3 '(1 2 3 4)) | |
321 @result{} 1 | |
322 | |
323 (nth n x) @equiv{} (car (nthcdr n x)) | |
324 @end group | |
325 @end example | |
326 @end defun | |
327 | |
328 @defun nthcdr n list | |
329 This function returns the @var{n}th @sc{cdr} of @var{list}. In other | |
330 words, it removes the first @var{n} links of @var{list} and returns | |
331 what follows. | |
332 | |
333 If @var{n} is zero or negative, @code{nthcdr} returns all of | |
334 @var{list}. If the length of @var{list} is @var{n} or less, | |
335 @code{nthcdr} returns @code{nil}. | |
336 | |
337 @example | |
338 @group | |
339 (nthcdr 1 '(1 2 3 4)) | |
340 @result{} (2 3 4) | |
341 @end group | |
342 @group | |
343 (nthcdr 10 '(1 2 3 4)) | |
344 @result{} nil | |
345 @end group | |
346 @group | |
347 (nthcdr -3 '(1 2 3 4)) | |
348 @result{} (1 2 3 4) | |
349 @end group | |
350 @end example | |
351 @end defun | |
352 | |
353 @node Building Lists | |
354 @comment node-name, next, previous, up | |
355 @section Building Cons Cells and Lists | |
356 @cindex cons cells | |
357 @cindex building lists | |
358 | |
359 Many functions build lists, as lists reside at the very heart of Lisp. | |
360 @code{cons} is the fundamental list-building function; however, it is | |
361 interesting to note that @code{list} is used more times in the source | |
362 code for Emacs than @code{cons}. | |
363 | |
364 @defun cons object1 object2 | |
365 This function is the fundamental function used to build new list | |
366 structure. It creates a new cons cell, making @var{object1} the | |
367 @sc{car}, and @var{object2} the @sc{cdr}. It then returns the new cons | |
368 cell. The arguments @var{object1} and @var{object2} may be any Lisp | |
369 objects, but most often @var{object2} is a list. | |
370 | |
371 @example | |
372 @group | |
373 (cons 1 '(2)) | |
374 @result{} (1 2) | |
375 @end group | |
376 @group | |
377 (cons 1 '()) | |
378 @result{} (1) | |
379 @end group | |
380 @group | |
381 (cons 1 2) | |
382 @result{} (1 . 2) | |
383 @end group | |
384 @end example | |
385 | |
386 @cindex consing | |
387 @code{cons} is often used to add a single element to the front of a | |
388 list. This is called @dfn{consing the element onto the list}. For | |
389 example: | |
390 | |
391 @example | |
392 (setq list (cons newelt list)) | |
393 @end example | |
394 | |
395 Note that there is no conflict between the variable named @code{list} | |
396 used in this example and the function named @code{list} described below; | |
397 any symbol can serve both purposes. | |
398 @end defun | |
399 | |
400 @defun list &rest objects | |
401 This function creates a list with @var{objects} as its elements. The | |
402 resulting list is always @code{nil}-terminated. If no @var{objects} | |
403 are given, the empty list is returned. | |
404 | |
405 @example | |
406 @group | |
407 (list 1 2 3 4 5) | |
408 @result{} (1 2 3 4 5) | |
409 @end group | |
410 @group | |
411 (list 1 2 '(3 4 5) 'foo) | |
412 @result{} (1 2 (3 4 5) foo) | |
413 @end group | |
414 @group | |
415 (list) | |
416 @result{} nil | |
417 @end group | |
418 @end example | |
419 @end defun | |
420 | |
421 @defun make-list length object | |
422 This function creates a list of length @var{length}, in which all the | |
423 elements have the identical value @var{object}. Compare | |
424 @code{make-list} with @code{make-string} (@pxref{Creating Strings}). | |
425 | |
426 @example | |
427 @group | |
428 (make-list 3 'pigs) | |
429 @result{} (pigs pigs pigs) | |
430 @end group | |
431 @group | |
432 (make-list 0 'pigs) | |
433 @result{} nil | |
434 @end group | |
435 @end example | |
436 @end defun | |
437 | |
438 @defun append &rest sequences | |
439 @cindex copying lists | |
440 This function returns a list containing all the elements of | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
441 @var{sequences}. The @var{sequences} may be lists, vectors, or strings, |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
442 but the last one should be a list. All arguments except the last one |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
443 are copied, so none of them are altered. |
6558 | 444 |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
445 More generally, the final argument to @code{append} may be any Lisp |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
446 object. The final argument is not copied or converted; it becomes the |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
447 @sc{cdr} of the last cons cell in the new list. If the final argument |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
448 is itself a list, then its elements become in effect elements of the |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
449 result list. If the final element is not a list, the result is a |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
450 ``dotted list'' since its final @sc{cdr} is not @code{nil} as required |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
451 in a true list. |
6558 | 452 |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
453 See @code{nconc} in @ref{Rearrangement}, for a way to join lists with no |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
454 copying. |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
455 |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
456 Here is an example of using @code{append}: |
6558 | 457 |
458 @example | |
459 @group | |
460 (setq trees '(pine oak)) | |
461 @result{} (pine oak) | |
462 (setq more-trees (append '(maple birch) trees)) | |
463 @result{} (maple birch pine oak) | |
464 @end group | |
465 | |
466 @group | |
467 trees | |
468 @result{} (pine oak) | |
469 more-trees | |
470 @result{} (maple birch pine oak) | |
471 @end group | |
472 @group | |
473 (eq trees (cdr (cdr more-trees))) | |
474 @result{} t | |
475 @end group | |
476 @end example | |
477 | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
478 You can see how @code{append} works by looking at a box diagram. The |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
479 variable @code{trees} is set to the list @code{(pine oak)} and then the |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
480 variable @code{more-trees} is set to the list @code{(maple birch pine |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
481 oak)}. However, the variable @code{trees} continues to refer to the |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
482 original list: |
6558 | 483 |
484 @smallexample | |
485 @group | |
486 more-trees trees | |
487 | | | |
488 | ___ ___ ___ ___ -> ___ ___ ___ ___ | |
489 --> |___|___|--> |___|___|--> |___|___|--> |___|___|--> nil | |
490 | | | | | |
491 | | | | | |
492 --> maple -->birch --> pine --> oak | |
493 @end group | |
494 @end smallexample | |
495 | |
496 An empty sequence contributes nothing to the value returned by | |
497 @code{append}. As a consequence of this, a final @code{nil} argument | |
498 forces a copy of the previous argument. | |
499 | |
500 @example | |
501 @group | |
502 trees | |
503 @result{} (pine oak) | |
504 @end group | |
505 @group | |
506 (setq wood (append trees ())) | |
507 @result{} (pine oak) | |
508 @end group | |
509 @group | |
510 wood | |
511 @result{} (pine oak) | |
512 @end group | |
513 @group | |
514 (eq wood trees) | |
515 @result{} nil | |
516 @end group | |
517 @end example | |
518 | |
519 @noindent | |
520 This once was the usual way to copy a list, before the function | |
521 @code{copy-sequence} was invented. @xref{Sequences Arrays Vectors}. | |
522 | |
523 With the help of @code{apply}, we can append all the lists in a list of | |
524 lists: | |
525 | |
526 @example | |
527 @group | |
528 (apply 'append '((a b c) nil (x y z) nil)) | |
529 @result{} (a b c x y z) | |
530 @end group | |
531 @end example | |
532 | |
533 If no @var{sequences} are given, @code{nil} is returned: | |
534 | |
535 @example | |
536 @group | |
537 (append) | |
538 @result{} nil | |
539 @end group | |
540 @end example | |
541 | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
542 Here are some examples where the final argument is not a list: |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
543 |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
544 @example |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
545 (append '(x y) 'z) |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
546 @result{} (x y z) |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
547 (append '(x y) [z]) |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
548 @result{} (x y [z]) |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
549 @end example |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
550 |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
551 @noindent |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
552 The second example shows that when the final argument is a sequence but |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
553 not a list, the sequence's elements do not become elements of the |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
554 resulting list. Instead, the sequence becomes the final @sc{cdr}, like |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
555 any other non-list final argument. |
6558 | 556 |
557 Integers are also allowed as arguments to @code{append}. They are | |
558 converted to strings of digits making up the decimal print | |
559 representation of the integer, and these strings are then appended. | |
560 Here's what happens: | |
561 | |
562 @example | |
563 @group | |
564 (setq trees '(pine oak)) | |
565 @result{} (pine oak) | |
566 @end group | |
567 @group | |
568 (char-to-string 54) | |
569 @result{} "6" | |
570 @end group | |
571 @group | |
572 (setq longer-list (append trees 6 '(spruce))) | |
573 @result{} (pine oak 54 spruce) | |
574 @end group | |
575 @group | |
576 (setq x-list (append trees 6 6)) | |
577 @result{} (pine oak 54 . 6) | |
578 @end group | |
579 @end example | |
580 | |
581 This special case exists for compatibility with Mocklisp, and we don't | |
582 recommend you take advantage of it. If you want to convert an integer | |
583 in this way, use @code{format} (@pxref{Formatting Strings}) or | |
584 @code{number-to-string} (@pxref{String Conversion}). | |
585 @end defun | |
586 | |
587 @defun reverse list | |
588 This function creates a new list whose elements are the elements of | |
589 @var{list}, but in reverse order. The original argument @var{list} is | |
590 @emph{not} altered. | |
591 | |
592 @example | |
593 @group | |
594 (setq x '(1 2 3 4)) | |
595 @result{} (1 2 3 4) | |
596 @end group | |
597 @group | |
598 (reverse x) | |
599 @result{} (4 3 2 1) | |
600 x | |
601 @result{} (1 2 3 4) | |
602 @end group | |
603 @end example | |
604 @end defun | |
605 | |
606 @node Modifying Lists | |
607 @section Modifying Existing List Structure | |
608 | |
609 You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the | |
610 primitives @code{setcar} and @code{setcdr}. | |
611 | |
612 @cindex CL note---@code{rplaca} vrs @code{setcar} | |
613 @quotation | |
614 @findex rplaca | |
615 @findex rplacd | |
616 @b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and | |
617 @code{rplacd} to alter list structure; they change structure the same | |
618 way as @code{setcar} and @code{setcdr}, but the Common Lisp functions | |
619 return the cons cell while @code{setcar} and @code{setcdr} return the | |
620 new @sc{car} or @sc{cdr}. | |
621 @end quotation | |
622 | |
623 @menu | |
624 * Setcar:: Replacing an element in a list. | |
625 * Setcdr:: Replacing part of the list backbone. | |
626 This can be used to remove or add elements. | |
627 * Rearrangement:: Reordering the elements in a list; combining lists. | |
628 @end menu | |
629 | |
630 @node Setcar | |
631 @subsection Altering List Elements with @code{setcar} | |
632 | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
633 Changing the @sc{car} of a cons cell is done with @code{setcar}. When |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
634 used on a list, @code{setcar} replaces one element of a list with a |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
635 different element. |
6558 | 636 |
637 @defun setcar cons object | |
638 This function stores @var{object} as the new @sc{car} of @var{cons}, | |
639 replacing its previous @sc{car}. It returns the value @var{object}. | |
640 For example: | |
641 | |
642 @example | |
643 @group | |
644 (setq x '(1 2)) | |
645 @result{} (1 2) | |
646 @end group | |
647 @group | |
648 (setcar x 4) | |
649 @result{} 4 | |
650 @end group | |
651 @group | |
652 x | |
653 @result{} (4 2) | |
654 @end group | |
655 @end example | |
656 @end defun | |
657 | |
658 When a cons cell is part of the shared structure of several lists, | |
659 storing a new @sc{car} into the cons changes one element of each of | |
660 these lists. Here is an example: | |
661 | |
662 @example | |
663 @group | |
664 ;; @r{Create two lists that are partly shared.} | |
665 (setq x1 '(a b c)) | |
666 @result{} (a b c) | |
667 (setq x2 (cons 'z (cdr x1))) | |
668 @result{} (z b c) | |
669 @end group | |
670 | |
671 @group | |
672 ;; @r{Replace the @sc{car} of a shared link.} | |
673 (setcar (cdr x1) 'foo) | |
674 @result{} foo | |
675 x1 ; @r{Both lists are changed.} | |
676 @result{} (a foo c) | |
677 x2 | |
678 @result{} (z foo c) | |
679 @end group | |
680 | |
681 @group | |
682 ;; @r{Replace the @sc{car} of a link that is not shared.} | |
683 (setcar x1 'baz) | |
684 @result{} baz | |
685 x1 ; @r{Only one list is changed.} | |
686 @result{} (baz foo c) | |
687 x2 | |
688 @result{} (z foo c) | |
689 @end group | |
690 @end example | |
691 | |
692 Here is a graphical depiction of the shared structure of the two lists | |
693 in the variables @code{x1} and @code{x2}, showing why replacing @code{b} | |
694 changes them both: | |
695 | |
696 @example | |
697 @group | |
698 ___ ___ ___ ___ ___ ___ | |
699 x1---> |___|___|----> |___|___|--> |___|___|--> nil | |
700 | --> | | | |
701 | | | | | |
702 --> a | --> b --> c | |
703 | | |
704 ___ ___ | | |
705 x2--> |___|___|-- | |
706 | | |
707 | | |
708 --> z | |
709 @end group | |
710 @end example | |
711 | |
712 Here is an alternative form of box diagram, showing the same relationship: | |
713 | |
714 @example | |
715 @group | |
716 x1: | |
717 -------------- -------------- -------------- | |
718 | car | cdr | | car | cdr | | car | cdr | | |
719 | a | o------->| b | o------->| c | nil | | |
720 | | | -->| | | | | | | |
721 -------------- | -------------- -------------- | |
722 | | |
723 x2: | | |
724 -------------- | | |
725 | car | cdr | | | |
726 | z | o---- | |
727 | | | | |
728 -------------- | |
729 @end group | |
730 @end example | |
731 | |
732 @node Setcdr | |
733 @subsection Altering the CDR of a List | |
734 | |
735 The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}: | |
736 | |
737 @defun setcdr cons object | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
738 This function stores @var{object} as the new @sc{cdr} of @var{cons}, |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
739 replacing its previous @sc{cdr}. It returns the value @var{object}. |
6558 | 740 @end defun |
741 | |
742 Here is an example of replacing the @sc{cdr} of a list with a | |
743 different list. All but the first element of the list are removed in | |
744 favor of a different sequence of elements. The first element is | |
745 unchanged, because it resides in the @sc{car} of the list, and is not | |
746 reached via the @sc{cdr}. | |
747 | |
748 @example | |
749 @group | |
750 (setq x '(1 2 3)) | |
751 @result{} (1 2 3) | |
752 @end group | |
753 @group | |
754 (setcdr x '(4)) | |
755 @result{} (4) | |
756 @end group | |
757 @group | |
758 x | |
759 @result{} (1 4) | |
760 @end group | |
761 @end example | |
762 | |
763 You can delete elements from the middle of a list by altering the | |
764 @sc{cdr}s of the cons cells in the list. For example, here we delete | |
765 the second element, @code{b}, from the list @code{(a b c)}, by changing | |
766 the @sc{cdr} of the first cell: | |
767 | |
768 @example | |
769 @group | |
770 (setq x1 '(a b c)) | |
771 @result{} (a b c) | |
772 (setcdr x1 (cdr (cdr x1))) | |
773 @result{} (c) | |
774 x1 | |
775 @result{} (a c) | |
776 @end group | |
777 @end example | |
778 | |
779 Here is the result in box notation: | |
780 | |
781 @example | |
782 @group | |
783 -------------------- | |
784 | | | |
785 -------------- | -------------- | -------------- | |
786 | car | cdr | | | car | cdr | -->| car | cdr | | |
787 | a | o----- | b | o-------->| c | nil | | |
788 | | | | | | | | | | |
789 -------------- -------------- -------------- | |
790 @end group | |
791 @end example | |
792 | |
793 @noindent | |
794 The second cons cell, which previously held the element @code{b}, still | |
795 exists and its @sc{car} is still @code{b}, but it no longer forms part | |
796 of this list. | |
797 | |
798 It is equally easy to insert a new element by changing @sc{cdr}s: | |
799 | |
800 @example | |
801 @group | |
802 (setq x1 '(a b c)) | |
803 @result{} (a b c) | |
804 (setcdr x1 (cons 'd (cdr x1))) | |
805 @result{} (d b c) | |
806 x1 | |
807 @result{} (a d b c) | |
808 @end group | |
809 @end example | |
810 | |
811 Here is this result in box notation: | |
812 | |
813 @smallexample | |
814 @group | |
815 -------------- ------------- ------------- | |
816 | car | cdr | | car | cdr | | car | cdr | | |
817 | a | o | -->| b | o------->| c | nil | | |
818 | | | | | | | | | | | | |
819 --------- | -- | ------------- ------------- | |
820 | | | |
821 ----- -------- | |
822 | | | |
823 | --------------- | | |
824 | | car | cdr | | | |
825 -->| d | o------ | |
826 | | | | |
827 --------------- | |
828 @end group | |
829 @end smallexample | |
830 | |
831 @node Rearrangement | |
832 @subsection Functions that Rearrange Lists | |
833 @cindex rearrangement of lists | |
834 @cindex modification of lists | |
835 | |
836 Here are some functions that rearrange lists ``destructively'' by | |
837 modifying the @sc{cdr}s of their component cons cells. We call these | |
838 functions ``destructive'' because they chew up the original lists passed | |
839 to them as arguments, to produce a new list that is the returned value. | |
840 | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
841 @ifinfo |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
842 See @code{delq}, in @ref{Sets And Lists}, for another function |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
843 that modifies cons cells. |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
844 @end ifinfo |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
845 @iftex |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
846 The function @code{delq} in the following section is another example |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
847 of destructive list manipulation. |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
848 @end iftex |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
849 |
6558 | 850 @defun nconc &rest lists |
851 @cindex concatenating lists | |
852 @cindex joining lists | |
853 This function returns a list containing all the elements of @var{lists}. | |
854 Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are | |
855 @emph{not} copied. Instead, the last @sc{cdr} of each of the | |
856 @var{lists} is changed to refer to the following list. The last of the | |
857 @var{lists} is not altered. For example: | |
858 | |
859 @example | |
860 @group | |
861 (setq x '(1 2 3)) | |
862 @result{} (1 2 3) | |
863 @end group | |
864 @group | |
865 (nconc x '(4 5)) | |
866 @result{} (1 2 3 4 5) | |
867 @end group | |
868 @group | |
869 x | |
870 @result{} (1 2 3 4 5) | |
871 @end group | |
872 @end example | |
873 | |
874 Since the last argument of @code{nconc} is not itself modified, it is | |
875 reasonable to use a constant list, such as @code{'(4 5)}, as in the | |
876 above example. For the same reason, the last argument need not be a | |
877 list: | |
878 | |
879 @example | |
880 @group | |
881 (setq x '(1 2 3)) | |
882 @result{} (1 2 3) | |
883 @end group | |
884 @group | |
885 (nconc x 'z) | |
886 @result{} (1 2 3 . z) | |
887 @end group | |
888 @group | |
889 x | |
890 @result{} (1 2 3 . z) | |
891 @end group | |
892 @end example | |
893 | |
894 A common pitfall is to use a quoted constant list as a non-last | |
895 argument to @code{nconc}. If you do this, your program will change | |
896 each time you run it! Here is what happens: | |
897 | |
898 @smallexample | |
899 @group | |
900 (defun add-foo (x) ; @r{We want this function to add} | |
901 (nconc '(foo) x)) ; @r{@code{foo} to the front of its arg.} | |
902 @end group | |
903 | |
904 @group | |
905 (symbol-function 'add-foo) | |
906 @result{} (lambda (x) (nconc (quote (foo)) x)) | |
907 @end group | |
908 | |
909 @group | |
910 (setq xx (add-foo '(1 2))) ; @r{It seems to work.} | |
911 @result{} (foo 1 2) | |
912 @end group | |
913 @group | |
914 (setq xy (add-foo '(3 4))) ; @r{What happened?} | |
915 @result{} (foo 1 2 3 4) | |
916 @end group | |
917 @group | |
918 (eq xx xy) | |
919 @result{} t | |
920 @end group | |
921 | |
922 @group | |
923 (symbol-function 'add-foo) | |
924 @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x))) | |
925 @end group | |
926 @end smallexample | |
927 @end defun | |
928 | |
929 @defun nreverse list | |
930 @cindex reversing a list | |
931 This function reverses the order of the elements of @var{list}. | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
932 Unlike @code{reverse}, @code{nreverse} alters its argument by reversing |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
933 the @sc{cdr}s in the cons cells forming the list. The cons cell that |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
934 used to be the last one in @var{list} becomes the first cell of the |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
935 value. |
6558 | 936 |
937 For example: | |
938 | |
939 @example | |
940 @group | |
941 (setq x '(1 2 3 4)) | |
942 @result{} (1 2 3 4) | |
943 @end group | |
944 @group | |
945 x | |
946 @result{} (1 2 3 4) | |
947 (nreverse x) | |
948 @result{} (4 3 2 1) | |
949 @end group | |
950 @group | |
951 ;; @r{The cell that was first is now last.} | |
952 x | |
953 @result{} (1) | |
954 @end group | |
955 @end example | |
956 | |
957 To avoid confusion, we usually store the result of @code{nreverse} | |
958 back in the same variable which held the original list: | |
959 | |
960 @example | |
961 (setq x (nreverse x)) | |
962 @end example | |
963 | |
964 Here is the @code{nreverse} of our favorite example, @code{(a b c)}, | |
965 presented graphically: | |
966 | |
967 @smallexample | |
968 @group | |
969 @r{Original list head:} @r{Reversed list:} | |
970 ------------- ------------- ------------ | |
971 | car | cdr | | car | cdr | | car | cdr | | |
972 | a | nil |<-- | b | o |<-- | c | o | | |
973 | | | | | | | | | | | | | | |
974 ------------- | --------- | - | -------- | - | |
975 | | | | | |
976 ------------- ------------ | |
977 @end group | |
978 @end smallexample | |
979 @end defun | |
980 | |
981 @defun sort list predicate | |
982 @cindex stable sort | |
983 @cindex sorting lists | |
984 This function sorts @var{list} stably, though destructively, and | |
985 returns the sorted list. It compares elements using @var{predicate}. A | |
986 stable sort is one in which elements with equal sort keys maintain their | |
987 relative order before and after the sort. Stability is important when | |
988 successive sorts are used to order elements according to different | |
989 criteria. | |
990 | |
991 The argument @var{predicate} must be a function that accepts two | |
992 arguments. It is called with two elements of @var{list}. To get an | |
993 increasing order sort, the @var{predicate} should return @code{t} if the | |
994 first element is ``less than'' the second, or @code{nil} if not. | |
995 | |
996 The destructive aspect of @code{sort} is that it rearranges the cons | |
997 cells forming @var{list} by changing @sc{cdr}s. A nondestructive sort | |
998 function would create new cons cells to store the elements in their | |
999 sorted order. If you wish to make a sorted copy without destroying the | |
1000 original, copy it first with @code{copy-sequence} and then sort. | |
1001 | |
1002 Sorting does not change the @sc{car}s of the cons cells in @var{list}; | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1003 each cons cell in the result contains the same element that it contained |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1004 before. The result differs from the argument @var{list} because the |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1005 cells themselves have been reordered. |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1006 |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1007 Sorting does not change the @sc{car}s of the cons cells in @var{list}; |
6558 | 1008 the cons cell that originally contained the element @code{a} in |
1009 @var{list} still has @code{a} in its @sc{car} after sorting, but it now | |
1010 appears in a different position in the list due to the change of | |
1011 @sc{cdr}s. For example: | |
1012 | |
1013 @example | |
1014 @group | |
1015 (setq nums '(1 3 2 6 5 4 0)) | |
1016 @result{} (1 3 2 6 5 4 0) | |
1017 @end group | |
1018 @group | |
1019 (sort nums '<) | |
1020 @result{} (0 1 2 3 4 5 6) | |
1021 @end group | |
1022 @group | |
1023 nums | |
1024 @result{} (1 2 3 4 5 6) | |
1025 @end group | |
1026 @end example | |
1027 | |
1028 @noindent | |
1029 Note that the list in @code{nums} no longer contains 0; this is the same | |
1030 cons cell that it was before, but it is no longer the first one in the | |
1031 list. Don't assume a variable that formerly held the argument now holds | |
1032 the entire sorted list! Instead, save the result of @code{sort} and use | |
1033 that. Most often we store the result back into the variable that held | |
1034 the original list: | |
1035 | |
1036 @example | |
1037 (setq nums (sort nums '<)) | |
1038 @end example | |
1039 | |
1040 @xref{Sorting}, for more functions that perform sorting. | |
1041 See @code{documentation} in @ref{Accessing Documentation}, for a | |
1042 useful example of @code{sort}. | |
1043 @end defun | |
1044 | |
1045 @node Sets And Lists | |
1046 @section Using Lists as Sets | |
1047 @cindex lists as sets | |
1048 @cindex sets | |
1049 | |
1050 A list can represent an unordered mathematical set---simply consider a | |
1051 value an element of a set if it appears in the list, and ignore the | |
1052 order of the list. To form the union of two sets, use @code{append} (as | |
1053 long as you don't mind having duplicate elements). Other useful | |
1054 functions for sets include @code{memq} and @code{delq}, and their | |
1055 @code{equal} versions, @code{member} and @code{delete}. | |
1056 | |
1057 @cindex CL note---lack @code{union}, @code{set} | |
1058 @quotation | |
1059 @b{Common Lisp note:} Common Lisp has functions @code{union} (which | |
1060 avoids duplicate elements) and @code{intersection} for set operations, | |
1061 but GNU Emacs Lisp does not have them. You can write them in Lisp if | |
1062 you wish. | |
1063 @end quotation | |
1064 | |
1065 @defun memq object list | |
1066 @cindex membership in a list | |
1067 This function tests to see whether @var{object} is a member of | |
1068 @var{list}. If it is, @code{memq} returns a list starting with the | |
1069 first occurrence of @var{object}. Otherwise, it returns @code{nil}. | |
1070 The letter @samp{q} in @code{memq} says that it uses @code{eq} to | |
1071 compare @var{object} against the elements of the list. For example: | |
1072 | |
1073 @example | |
1074 @group | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1075 (memq 'b '(a b c b a)) |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1076 @result{} (b c b a) |
6558 | 1077 @end group |
1078 @group | |
1079 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.} | |
1080 @result{} nil | |
1081 @end group | |
1082 @end example | |
1083 @end defun | |
1084 | |
1085 @defun delq object list | |
1086 @cindex deletion of elements | |
1087 This function destructively removes all elements @code{eq} to | |
1088 @var{object} from @var{list}. The letter @samp{q} in @code{delq} says | |
1089 that it uses @code{eq} to compare @var{object} against the elements of | |
1090 the list, like @code{memq}. | |
1091 @end defun | |
1092 | |
1093 When @code{delq} deletes elements from the front of the list, it does so | |
1094 simply by advancing down the list and returning a sublist that starts | |
1095 after those elements: | |
1096 | |
1097 @example | |
1098 @group | |
1099 (delq 'a '(a b c)) @equiv{} (cdr '(a b c)) | |
1100 @end group | |
1101 @end example | |
1102 | |
1103 When an element to be deleted appears in the middle of the list, | |
1104 removing it involves changing the @sc{cdr}s (@pxref{Setcdr}). | |
1105 | |
1106 @example | |
1107 @group | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1108 (setq sample-list '(a b c (4))) |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1109 @result{} (a b c (4)) |
6558 | 1110 @end group |
1111 @group | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1112 (delq 'a sample-list) |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1113 @result{} (b c (4)) |
6558 | 1114 @end group |
1115 @group | |
1116 sample-list | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1117 @result{} (a b c (4)) |
6558 | 1118 @end group |
1119 @group | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1120 (delq 'c sample-list) |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1121 @result{} (a c (4)) |
6558 | 1122 @end group |
1123 @group | |
1124 sample-list | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1125 @result{} (a c (4)) |
6558 | 1126 @end group |
1127 @end example | |
1128 | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1129 Note that @code{(delq 'b sample-list)} modifies @code{sample-list} to |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1130 splice out the second element, but @code{(delq 'a sample-list)} does not |
6558 | 1131 splice anything---it just returns a shorter list. Don't assume that a |
1132 variable which formerly held the argument @var{list} now has fewer | |
1133 elements, or that it still holds the original list! Instead, save the | |
1134 result of @code{delq} and use that. Most often we store the result back | |
1135 into the variable that held the original list: | |
1136 | |
1137 @example | |
1138 (setq flowers (delq 'rose flowers)) | |
1139 @end example | |
1140 | |
1141 In the following example, the @code{(4)} that @code{delq} attempts to match | |
1142 and the @code{(4)} in the @code{sample-list} are not @code{eq}: | |
1143 | |
1144 @example | |
1145 @group | |
1146 (delq '(4) sample-list) | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1147 @result{} (a c (4)) |
6558 | 1148 @end group |
1149 @end example | |
1150 | |
1151 The following two functions are like @code{memq} and @code{delq} but use | |
1152 @code{equal} rather than @code{eq} to compare elements. They are new in | |
1153 Emacs 19. | |
1154 | |
1155 @defun member object list | |
1156 The function @code{member} tests to see whether @var{object} is a member | |
1157 of @var{list}, comparing members with @var{object} using @code{equal}. | |
1158 If @var{object} is a member, @code{member} returns a list starting with | |
1159 its first occurrence in @var{list}. Otherwise, it returns @code{nil}. | |
1160 | |
1161 Compare this with @code{memq}: | |
1162 | |
1163 @example | |
1164 @group | |
1165 (member '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are @code{equal}.} | |
1166 @result{} ((2)) | |
1167 @end group | |
1168 @group | |
1169 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.} | |
1170 @result{} nil | |
1171 @end group | |
1172 @group | |
1173 ;; @r{Two strings with the same contents are @code{equal}.} | |
1174 (member "foo" '("foo" "bar")) | |
1175 @result{} ("foo" "bar") | |
1176 @end group | |
1177 @end example | |
1178 @end defun | |
1179 | |
1180 @defun delete object list | |
1181 This function destructively removes all elements @code{equal} to | |
1182 @var{object} from @var{list}. It is to @code{delq} as @code{member} is | |
1183 to @code{memq}: it uses @code{equal} to compare elements with | |
1184 @var{object}, like @code{member}; when it finds an element that matches, | |
1185 it removes the element just as @code{delq} would. For example: | |
1186 | |
1187 @example | |
1188 @group | |
1189 (delete '(2) '((2) (1) (2))) | |
1190 @result{} '((1)) | |
1191 @end group | |
1192 @end example | |
1193 @end defun | |
1194 | |
1195 @quotation | |
1196 @b{Common Lisp note:} The functions @code{member} and @code{delete} in | |
1197 GNU Emacs Lisp are derived from Maclisp, not Common Lisp. The Common | |
1198 Lisp versions do not use @code{equal} to compare elements. | |
1199 @end quotation | |
1200 | |
1201 @node Association Lists | |
1202 @section Association Lists | |
1203 @cindex association list | |
1204 @cindex alist | |
1205 | |
1206 An @dfn{association list}, or @dfn{alist} for short, records a mapping | |
1207 from keys to values. It is a list of cons cells called | |
1208 @dfn{associations}: the @sc{car} of each cell is the @dfn{key}, and the | |
1209 @sc{cdr} is the @dfn{associated value}.@footnote{This usage of ``key'' | |
1210 is not related to the term ``key sequence''; it means a value used to | |
1211 look up an item in a table. In this case, the table is the alist, and | |
1212 the alist associations are the items.} | |
1213 | |
1214 Here is an example of an alist. The key @code{pine} is associated with | |
1215 the value @code{cones}; the key @code{oak} is associated with | |
1216 @code{acorns}; and the key @code{maple} is associated with @code{seeds}. | |
1217 | |
1218 @example | |
1219 @group | |
1220 '((pine . cones) | |
1221 (oak . acorns) | |
1222 (maple . seeds)) | |
1223 @end group | |
1224 @end example | |
1225 | |
1226 The associated values in an alist may be any Lisp objects; so may the | |
1227 keys. For example, in the following alist, the symbol @code{a} is | |
1228 associated with the number @code{1}, and the string @code{"b"} is | |
1229 associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of | |
1230 the alist element: | |
1231 | |
1232 @example | |
1233 ((a . 1) ("b" 2 3)) | |
1234 @end example | |
1235 | |
1236 Sometimes it is better to design an alist to store the associated | |
1237 value in the @sc{car} of the @sc{cdr} of the element. Here is an | |
1238 example: | |
1239 | |
1240 @example | |
1241 '((rose red) (lily white) (buttercup yellow)) | |
1242 @end example | |
1243 | |
1244 @noindent | |
1245 Here we regard @code{red} as the value associated with @code{rose}. One | |
1246 advantage of this method is that you can store other related | |
1247 information---even a list of other items---in the @sc{cdr} of the | |
1248 @sc{cdr}. One disadvantage is that you cannot use @code{rassq} (see | |
1249 below) to find the element containing a given value. When neither of | |
1250 these considerations is important, the choice is a matter of taste, as | |
1251 long as you are consistent about it for any given alist. | |
1252 | |
1253 Note that the same alist shown above could be regarded as having the | |
1254 associated value in the @sc{cdr} of the element; the value associated | |
1255 with @code{rose} would be the list @code{(red)}. | |
1256 | |
1257 Association lists are often used to record information that you might | |
1258 otherwise keep on a stack, since new associations may be added easily to | |
1259 the front of the list. When searching an association list for an | |
1260 association with a given key, the first one found is returned, if there | |
1261 is more than one. | |
1262 | |
1263 In Emacs Lisp, it is @emph{not} an error if an element of an | |
1264 association list is not a cons cell. The alist search functions simply | |
1265 ignore such elements. Many other versions of Lisp signal errors in such | |
1266 cases. | |
1267 | |
1268 Note that property lists are similar to association lists in several | |
1269 respects. A property list behaves like an association list in which | |
1270 each key can occur only once. @xref{Property Lists}, for a comparison | |
1271 of property lists and association lists. | |
1272 | |
1273 @defun assoc key alist | |
1274 This function returns the first association for @var{key} in | |
1275 @var{alist}. It compares @var{key} against the alist elements using | |
1276 @code{equal} (@pxref{Equality Predicates}). It returns @code{nil} if no | |
1277 association in @var{alist} has a @sc{car} @code{equal} to @var{key}. | |
1278 For example: | |
1279 | |
1280 @smallexample | |
1281 (setq trees '((pine . cones) (oak . acorns) (maple . seeds))) | |
1282 @result{} ((pine . cones) (oak . acorns) (maple . seeds)) | |
1283 (assoc 'oak trees) | |
1284 @result{} (oak . acorns) | |
1285 (cdr (assoc 'oak trees)) | |
1286 @result{} acorns | |
1287 (assoc 'birch trees) | |
1288 @result{} nil | |
1289 @end smallexample | |
1290 | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1291 Here is another example, in which the keys and values are not symbols: |
6558 | 1292 |
1293 @smallexample | |
1294 (setq needles-per-cluster | |
1295 '((2 "Austrian Pine" "Red Pine") | |
1296 (3 "Pitch Pine") | |
1297 (5 "White Pine"))) | |
1298 | |
1299 (cdr (assoc 3 needles-per-cluster)) | |
1300 @result{} ("Pitch Pine") | |
1301 (cdr (assoc 2 needles-per-cluster)) | |
1302 @result{} ("Austrian Pine" "Red Pine") | |
1303 @end smallexample | |
1304 @end defun | |
1305 | |
1306 @defun assq key alist | |
1307 This function is like @code{assoc} in that it returns the first | |
1308 association for @var{key} in @var{alist}, but it makes the comparison | |
1309 using @code{eq} instead of @code{equal}. @code{assq} returns @code{nil} | |
1310 if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}. | |
1311 This function is used more often than @code{assoc}, since @code{eq} is | |
1312 faster than @code{equal} and most alists use symbols as keys. | |
1313 @xref{Equality Predicates}. | |
1314 | |
1315 @smallexample | |
1316 (setq trees '((pine . cones) (oak . acorns) (maple . seeds))) | |
1317 @result{} ((pine . cones) (oak . acorns) (maple . seeds)) | |
1318 (assq 'pine trees) | |
1319 @result{} (pine . cones) | |
1320 @end smallexample | |
1321 | |
1322 On the other hand, @code{assq} is not usually useful in alists where the | |
1323 keys may not be symbols: | |
1324 | |
1325 @smallexample | |
1326 (setq leaves | |
1327 '(("simple leaves" . oak) | |
1328 ("compound leaves" . horsechestnut))) | |
1329 | |
1330 (assq "simple leaves" leaves) | |
1331 @result{} nil | |
1332 (assoc "simple leaves" leaves) | |
1333 @result{} ("simple leaves" . oak) | |
1334 @end smallexample | |
1335 @end defun | |
1336 | |
1337 @defun rassq value alist | |
1338 This function returns the first association with value @var{value} in | |
1339 @var{alist}. It returns @code{nil} if no association in @var{alist} has | |
1340 a @sc{cdr} @code{eq} to @var{value}. | |
1341 | |
1342 @code{rassq} is like @code{assq} except that it compares the @sc{cdr} of | |
1343 each @var{alist} association instead of the @sc{car}. You can think of | |
1344 this as ``reverse @code{assq}'', finding the key for a given value. | |
1345 | |
1346 For example: | |
1347 | |
1348 @smallexample | |
1349 (setq trees '((pine . cones) (oak . acorns) (maple . seeds))) | |
1350 | |
1351 (rassq 'acorns trees) | |
1352 @result{} (oak . acorns) | |
1353 (rassq 'spores trees) | |
1354 @result{} nil | |
1355 @end smallexample | |
1356 | |
1357 Note that @code{rassq} cannot search for a value stored in the @sc{car} | |
1358 of the @sc{cdr} of an element: | |
1359 | |
1360 @smallexample | |
1361 (setq colors '((rose red) (lily white) (buttercup yellow))) | |
1362 | |
1363 (rassq 'white colors) | |
1364 @result{} nil | |
1365 @end smallexample | |
1366 | |
1367 In this case, the @sc{cdr} of the association @code{(lily white)} is not | |
1368 the symbol @code{white}, but rather the list @code{(white)}. This | |
1369 becomes clearer if the association is written in dotted pair notation: | |
1370 | |
1371 @smallexample | |
1372 (lily white) @equiv{} (lily . (white)) | |
1373 @end smallexample | |
1374 @end defun | |
1375 | |
1376 @defun copy-alist alist | |
1377 @cindex copying alists | |
1378 This function returns a two-level deep copy of @var{alist}: it creates a | |
1379 new copy of each association, so that you can alter the associations of | |
1380 the new alist without changing the old one. | |
1381 | |
1382 @smallexample | |
1383 @group | |
1384 (setq needles-per-cluster | |
1385 '((2 . ("Austrian Pine" "Red Pine")) | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1386 (3 . ("Pitch Pine")) |
7734 | 1387 @end group |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1388 (5 . ("White Pine")))) |
6558 | 1389 @result{} |
1390 ((2 "Austrian Pine" "Red Pine") | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1391 (3 "Pitch Pine") |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1392 (5 "White Pine")) |
6558 | 1393 |
1394 (setq copy (copy-alist needles-per-cluster)) | |
1395 @result{} | |
1396 ((2 "Austrian Pine" "Red Pine") | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1397 (3 "Pitch Pine") |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1398 (5 "White Pine")) |
6558 | 1399 |
1400 (eq needles-per-cluster copy) | |
1401 @result{} nil | |
1402 (equal needles-per-cluster copy) | |
1403 @result{} t | |
1404 (eq (car needles-per-cluster) (car copy)) | |
1405 @result{} nil | |
1406 (cdr (car (cdr needles-per-cluster))) | |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1407 @result{} ("Pitch Pine") |
7734 | 1408 @group |
6558 | 1409 (eq (cdr (car (cdr needles-per-cluster))) |
1410 (cdr (car (cdr copy)))) | |
1411 @result{} t | |
1412 @end group | |
7337
cd57cd335fff
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
7118
diff
changeset
|
1413 @end smallexample |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1414 |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1415 This example shows how @code{copy-alist} makes it possible to change |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1416 the associations of one copy without affecting the other: |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1417 |
7337
cd57cd335fff
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
7118
diff
changeset
|
1418 @smallexample |
7118
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1419 @group |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1420 (setcdr (assq 3 needles-per-cluster) |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1421 '("Martian Vacuum Pine")) |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1422 (cdr (assq 3 needles-per-cluster)) |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1423 @result{} ("Pitch Pine") |
08d61ef58d13
*** empty log message ***
Richard M. Stallman <rms@gnu.org>
parents:
6558
diff
changeset
|
1424 @end group |
6558 | 1425 @end smallexample |
1426 @end defun | |
1427 | |
1428 |