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