lispref/lists.texi

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