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