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