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