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