1@c -*-texinfo-*- 2@c This is part of the GNU Emacs Lisp Reference Manual. 3@c Copyright (C) 1990--1995, 1998--1999, 2001--2021 Free Software 4@c Foundation, Inc. 5@c See the file elisp.texi for copying conditions. 6@node Lists 7@chapter Lists 8@cindex lists 9@cindex element (of list) 10 11 A @dfn{list} represents a sequence of zero or more elements (which may 12be any Lisp objects). The important difference between lists and 13vectors is that two or more lists can share part of their structure; in 14addition, you can insert or delete elements in a list without copying 15the whole list. 16 17@menu 18* Cons Cells:: How lists are made out of cons cells. 19* List-related Predicates:: Is this object a list? Comparing two lists. 20* List Elements:: Extracting the pieces of a list. 21* Building Lists:: Creating list structure. 22* List Variables:: Modifying lists stored in variables. 23* Modifying Lists:: Storing new pieces into an existing list. 24* Sets And Lists:: A list can represent a finite mathematical set. 25* Association Lists:: A list can represent a finite relation or mapping. 26* Property Lists:: A list of paired elements. 27@end menu 28 29@node Cons Cells 30@section Lists and Cons Cells 31@cindex lists and cons cells 32 33 Lists in Lisp are not a primitive data type; they are built up from 34@dfn{cons cells} (@pxref{Cons Cell Type}). A cons cell is a data 35object that represents an ordered pair. That is, it has two slots, 36and each slot @dfn{holds}, or @dfn{refers to}, some Lisp object. One 37slot is known as the @sc{car}, and the other is known as the @sc{cdr}. 38(These names are traditional; see @ref{Cons Cell Type}.) @sc{cdr} is 39pronounced ``could-er''. 40 41 We say that ``the @sc{car} of this cons cell is'' whatever object 42its @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 45cell refers to the next one. There is one cons cell for each element 46of the list. By convention, the @sc{car}s of the cons cells hold the 47elements of the list, and the @sc{cdr}s are used to chain the list 48(this asymmetry between @sc{car} and @sc{cdr} is entirely a matter of 49convention; at the level of cons cells, the @sc{car} and @sc{cdr} 50slots have similar properties). Hence, the @sc{cdr} slot of each cons 51cell in a list refers to the following cons cell. 52 53@cindex proper list 54@cindex true list 55 Also by convention, the @sc{cdr} of the last cons cell in a list is 56@code{nil}. We call such a @code{nil}-terminated structure a 57@dfn{proper list}@footnote{It is sometimes also referred to as a 58@dfn{true list}, but we generally do not use this terminology in this 59manual.}. In Emacs Lisp, the symbol @code{nil} is both a symbol and a 60list with no elements. For convenience, the symbol @code{nil} is 61considered to have @code{nil} as its @sc{cdr} (and also as its 62@sc{car}). 63 64 Hence, the @sc{cdr} of a proper list is always a proper list. The 65@sc{cdr} of a nonempty proper list is a proper list containing all the 66elements except the first. 67 68@cindex dotted list 69@cindex circular list 70 If the @sc{cdr} of a list's last cons cell is some value other than 71@code{nil}, we call the structure a @dfn{dotted list}, since its 72printed representation would use dotted pair notation (@pxref{Dotted 73Pair Notation}). There is one other possibility: some cons cell's 74@sc{cdr} could point to one of the previous cons cells in the list. 75We call that structure a @dfn{circular list}. 76 77 For some purposes, it does not matter whether a list is proper, 78circular or dotted. If a program doesn't look far enough down the 79list to see the @sc{cdr} of the final cons cell, it won't care. 80However, some functions that operate on lists demand proper lists and 81signal errors if given a dotted list. Most functions that try to find 82the end of a list enter infinite loops if given a circular list. 83 84@cindex list structure 85 Because most cons cells are used as part of lists, we refer to any 86structure made out of cons cells as a @dfn{list structure}. 87 88@node List-related Predicates 89@section Predicates on Lists 90@cindex predicates for lists 91@cindex list predicates 92 93 The following predicates test whether a Lisp object is an atom, 94whether it is a cons cell or is a list, or whether it is the 95distinguished object @code{nil}. (Many of these predicates can be 96defined in terms of the others, but they are used so often that it is 97worth having them.) 98 99@defun consp object 100This function returns @code{t} if @var{object} is a cons cell, @code{nil} 101otherwise. @code{nil} is not a cons cell, although it @emph{is} a list. 102@end defun 103 104@defun atom object 105This function returns @code{t} if @var{object} is an atom, @code{nil} 106otherwise. All objects except cons cells are atoms. The symbol 107@code{nil} is an atom and is also a list; it is the only Lisp object 108that is both. 109 110@example 111(atom @var{object}) @equiv{} (not (consp @var{object})) 112@end example 113@end defun 114 115@defun listp object 116This function returns @code{t} if @var{object} is a cons cell or 117@code{nil}. Otherwise, it returns @code{nil}. 118 119@example 120@group 121(listp '(1)) 122 @result{} t 123@end group 124@group 125(listp '()) 126 @result{} t 127@end group 128@end example 129@end defun 130 131@defun nlistp object 132This function is the opposite of @code{listp}: it returns @code{t} if 133@var{object} is not a list. Otherwise, it returns @code{nil}. 134 135@example 136(listp @var{object}) @equiv{} (not (nlistp @var{object})) 137@end example 138@end defun 139 140@defun null object 141This function returns @code{t} if @var{object} is @code{nil}, and 142returns @code{nil} otherwise. This function is identical to @code{not}, 143but as a matter of clarity we use @code{null} when @var{object} is 144considered a list and @code{not} when it is considered a truth value 145(see @code{not} in @ref{Combining Conditions}). 146 147@example 148@group 149(null '(1)) 150 @result{} nil 151@end group 152@group 153(null '()) 154 @result{} t 155@end group 156@end example 157@end defun 158 159@defun proper-list-p object 160This function returns the length of @var{object} if it is a proper 161list, @code{nil} otherwise (@pxref{Cons Cells}). In addition to 162satisfying @code{listp}, a proper list is neither circular nor dotted. 163 164@example 165@group 166(proper-list-p '(a b c)) 167 @result{} 3 168@end group 169@group 170(proper-list-p '(a b . c)) 171 @result{} nil 172@end group 173@end example 174@end defun 175 176@node List Elements 177@section Accessing Elements of Lists 178@cindex list elements 179 180@defun car cons-cell 181This function returns the value referred to by the first slot of the 182cons cell @var{cons-cell}. In other words, it returns the @sc{car} of 183@var{cons-cell}. 184 185As a special case, if @var{cons-cell} is @code{nil}, this function 186returns @code{nil}. Therefore, any list is a valid argument. An 187error is signaled if the argument is not a cons cell or @code{nil}. 188 189@example 190@group 191(car '(a b c)) 192 @result{} a 193@end group 194@group 195(car '()) 196 @result{} nil 197@end group 198@end example 199@end defun 200 201@defun cdr cons-cell 202This function returns the value referred to by the second slot of the 203cons cell @var{cons-cell}. In other words, it returns the @sc{cdr} of 204@var{cons-cell}. 205 206As a special case, if @var{cons-cell} is @code{nil}, this function 207returns @code{nil}; therefore, any list is a valid argument. An error 208is signaled if the argument is not a cons cell or @code{nil}. 209 210@example 211@group 212(cdr '(a b c)) 213 @result{} (b c) 214@end group 215@group 216(cdr '()) 217 @result{} nil 218@end group 219@end example 220@end defun 221 222@defun car-safe object 223This function lets you take the @sc{car} of a cons cell while avoiding 224errors for other data types. It returns the @sc{car} of @var{object} if 225@var{object} is a cons cell, @code{nil} otherwise. This is in contrast 226to @code{car}, which signals an error if @var{object} is not a list. 227 228@example 229@group 230(car-safe @var{object}) 231@equiv{} 232(let ((x @var{object})) 233 (if (consp x) 234 (car x) 235 nil)) 236@end group 237@end example 238@end defun 239 240@defun cdr-safe object 241This function lets you take the @sc{cdr} of a cons cell while 242avoiding errors for other data types. It returns the @sc{cdr} of 243@var{object} if @var{object} is a cons cell, @code{nil} otherwise. 244This is in contrast to @code{cdr}, which signals an error if 245@var{object} is not a list. 246 247@example 248@group 249(cdr-safe @var{object}) 250@equiv{} 251(let ((x @var{object})) 252 (if (consp x) 253 (cdr x) 254 nil)) 255@end group 256@end example 257@end defun 258 259@defmac pop listname 260This macro provides a convenient way to examine the @sc{car} of a 261list, and take it off the list, all at once. It operates on the list 262stored in @var{listname}. It removes the first element from the list, 263saves the @sc{cdr} into @var{listname}, then returns the removed 264element. 265 266In the simplest case, @var{listname} is an unquoted symbol naming a 267list; in that case, this macro is equivalent to @w{@code{(prog1 268(car listname) (setq listname (cdr listname)))}}. 269 270@example 271x 272 @result{} (a b c) 273(pop x) 274 @result{} a 275x 276 @result{} (b c) 277@end example 278 279More generally, @var{listname} can be a generalized variable. In that 280case, this macro saves into @var{listname} using @code{setf}. 281@xref{Generalized Variables}. 282 283For the @code{push} macro, which adds an element to a list, 284@xref{List Variables}. 285@end defmac 286 287@defun nth n list 288@anchor{Definition of nth} 289This function returns the @var{n}th element of @var{list}. Elements 290are numbered starting with zero, so the @sc{car} of @var{list} is 291element number zero. If the length of @var{list} is @var{n} or less, 292the value is @code{nil}. 293 294@c Behavior for -ve n undefined since 2013/08; see bug#15059. 295@ignore 296If @var{n} is negative, @code{nth} returns the first element of @var{list}. 297@end ignore 298 299@example 300@group 301(nth 2 '(1 2 3 4)) 302 @result{} 3 303@end group 304@group 305(nth 10 '(1 2 3 4)) 306 @result{} nil 307 308(nth n x) @equiv{} (car (nthcdr n x)) 309@end group 310@end example 311 312The function @code{elt} is similar, but applies to any kind of sequence. 313For historical reasons, it takes its arguments in the opposite order. 314@xref{Sequence Functions}. 315@end defun 316 317@defun nthcdr n list 318This function returns the @var{n}th @sc{cdr} of @var{list}. In other 319words, it skips past the first @var{n} links of @var{list} and returns 320what follows. 321 322@c "or negative" removed 2013/08; see bug#15059. 323If @var{n} is zero, @code{nthcdr} returns all of 324@var{list}. If the length of @var{list} is @var{n} or less, 325@code{nthcdr} returns @code{nil}. 326 327@example 328@group 329(nthcdr 1 '(1 2 3 4)) 330 @result{} (2 3 4) 331@end group 332@group 333(nthcdr 10 '(1 2 3 4)) 334 @result{} nil 335@end group 336@group 337(nthcdr 0 '(1 2 3 4)) 338 @result{} (1 2 3 4) 339@end group 340@end example 341@end defun 342 343@defun last list &optional n 344This function returns the last link of @var{list}. The @code{car} of 345this link is the list's last element. If @var{list} is null, 346@code{nil} is returned. If @var{n} is non-@code{nil}, the 347@var{n}th-to-last link is returned instead, or the whole of @var{list} 348if @var{n} is bigger than @var{list}'s length. 349@end defun 350 351@defun safe-length list 352@anchor{Definition of safe-length} 353This function returns the length of @var{list}, with no risk of either 354an error or an infinite loop. It generally returns the number of 355distinct cons cells in the list. However, for circular lists, 356the value is just an upper bound; it is often too large. 357 358If @var{list} is not @code{nil} or a cons cell, @code{safe-length} 359returns 0. 360@end defun 361 362 The most common way to compute the length of a list, when you are not 363worried that it may be circular, is with @code{length}. @xref{Sequence 364Functions}. 365 366@defun caar cons-cell 367This is the same as @code{(car (car @var{cons-cell}))}. 368@end defun 369 370@defun cadr cons-cell 371This is the same as @code{(car (cdr @var{cons-cell}))} 372or @code{(nth 1 @var{cons-cell})}. 373@end defun 374 375@defun cdar cons-cell 376This is the same as @code{(cdr (car @var{cons-cell}))}. 377@end defun 378 379@defun cddr cons-cell 380This is the same as @code{(cdr (cdr @var{cons-cell}))} 381or @code{(nthcdr 2 @var{cons-cell})}. 382@end defun 383 384@findex caaar 385@findex caadr 386@findex cadar 387@findex caddr 388@findex cdaar 389@findex cdadr 390@findex cddar 391@findex cdddr 392@findex caaaar 393@findex caaadr 394@findex caadar 395@findex caaddr 396@findex cadaar 397@findex cadadr 398@findex caddar 399@findex cadddr 400@findex cdaaar 401@findex cdaadr 402@findex cdadar 403@findex cdaddr 404@findex cddaar 405@findex cddadr 406@findex cdddar 407@findex cddddr 408In addition to the above, 24 additional compositions of @code{car} and 409@code{cdr} are defined as @code{c@var{xxx}r} and @code{c@var{xxxx}r}, 410where each @code{@var{x}} is either @code{a} or @code{d}. @code{cadr}, 411@code{caddr}, and @code{cadddr} pick out the second, third or fourth 412elements of a list, respectively. @file{cl-lib} provides the same 413under the names @code{cl-second}, @code{cl-third}, and 414@code{cl-fourth}. @xref{List Functions,,, cl, Common Lisp 415Extensions}. 416 417@defun butlast x &optional n 418This function returns the list @var{x} with the last element, 419or the last @var{n} elements, removed. If @var{n} is greater 420than zero it makes a copy of the list so as not to damage the 421original list. In general, @code{(append (butlast @var{x} @var{n}) 422(last @var{x} @var{n}))} will return a list equal to @var{x}. 423@end defun 424 425@defun nbutlast x &optional n 426This is a version of @code{butlast} that works by destructively 427modifying the @code{cdr} of the appropriate element, rather than 428making a copy of the list. 429@end defun 430 431@node Building Lists 432@section Building Cons Cells and Lists 433@cindex cons cells 434@cindex building lists 435 436 Many functions build lists, as lists reside at the very heart of Lisp. 437@code{cons} is the fundamental list-building function; however, it is 438interesting to note that @code{list} is used more times in the source 439code for Emacs than @code{cons}. 440 441@defun cons object1 object2 442This function is the most basic function for building new list 443structure. It creates a new cons cell, making @var{object1} the 444@sc{car}, and @var{object2} the @sc{cdr}. It then returns the new 445cons cell. The arguments @var{object1} and @var{object2} may be any 446Lisp objects, but most often @var{object2} is a list. 447 448@example 449@group 450(cons 1 '(2)) 451 @result{} (1 2) 452@end group 453@group 454(cons 1 '()) 455 @result{} (1) 456@end group 457@group 458(cons 1 2) 459 @result{} (1 . 2) 460@end group 461@end example 462 463@cindex consing 464@code{cons} is often used to add a single element to the front of a 465list. This is called @dfn{consing the element onto the list}. 466@footnote{There is no strictly equivalent way to add an element to 467the end of a list. You can use @code{(append @var{listname} (list 468@var{newelt}))}, which creates a whole new list by copying @var{listname} 469and adding @var{newelt} to its end. Or you can use @code{(nconc 470@var{listname} (list @var{newelt}))}, which modifies @var{listname} 471by following all the @sc{cdr}s and then replacing the terminating 472@code{nil}. Compare this to adding an element to the beginning of a 473list with @code{cons}, which neither copies nor modifies the list.} 474For example: 475 476@example 477(setq list (cons newelt list)) 478@end example 479 480Note that there is no conflict between the variable named @code{list} 481used in this example and the function named @code{list} described below; 482any symbol can serve both purposes. 483@end defun 484 485@defun list &rest objects 486This function creates a list with @var{objects} as its elements. The 487resulting list is always @code{nil}-terminated. If no @var{objects} 488are given, the empty list is returned. 489 490@example 491@group 492(list 1 2 3 4 5) 493 @result{} (1 2 3 4 5) 494@end group 495@group 496(list 1 2 '(3 4 5) 'foo) 497 @result{} (1 2 (3 4 5) foo) 498@end group 499@group 500(list) 501 @result{} nil 502@end group 503@end example 504@end defun 505 506@defun make-list length object 507This function creates a list of @var{length} elements, in which each 508element is @var{object}. Compare @code{make-list} with 509@code{make-string} (@pxref{Creating Strings}). 510 511@example 512@group 513(make-list 3 'pigs) 514 @result{} (pigs pigs pigs) 515@end group 516@group 517(make-list 0 'pigs) 518 @result{} nil 519@end group 520@group 521(setq l (make-list 3 '(a b))) 522 @result{} ((a b) (a b) (a b)) 523(eq (car l) (cadr l)) 524 @result{} t 525@end group 526@end example 527@end defun 528 529@defun append &rest sequences 530@cindex copying lists 531This function returns a list containing all the elements of 532@var{sequences}. The @var{sequences} may be lists, vectors, 533bool-vectors, or strings, but the last one should usually be a list. 534All arguments except the last one are copied, so none of the arguments 535is altered. (See @code{nconc} in @ref{Rearrangement}, for a way to join 536lists with no copying.) 537 538More generally, the final argument to @code{append} may be any Lisp 539object. The final argument is not copied or converted; it becomes the 540@sc{cdr} of the last cons cell in the new list. If the final argument 541is itself a list, then its elements become in effect elements of the 542result list. If the final element is not a list, the result is a 543dotted list since its final @sc{cdr} is not @code{nil} as required 544in a proper list (@pxref{Cons Cells}). 545@end defun 546 547 Here is an example of using @code{append}: 548 549@example 550@group 551(setq trees '(pine oak)) 552 @result{} (pine oak) 553(setq more-trees (append '(maple birch) trees)) 554 @result{} (maple birch pine oak) 555@end group 556 557@group 558trees 559 @result{} (pine oak) 560more-trees 561 @result{} (maple birch pine oak) 562@end group 563@group 564(eq trees (cdr (cdr more-trees))) 565 @result{} t 566@end group 567@end example 568 569 You can see how @code{append} works by looking at a box diagram. The 570variable @code{trees} is set to the list @code{(pine oak)} and then the 571variable @code{more-trees} is set to the list @code{(maple birch pine 572oak)}. However, the variable @code{trees} continues to refer to the 573original list: 574 575@smallexample 576@group 577more-trees trees 578| | 579| --- --- --- --- -> --- --- --- --- 580 --> | | |--> | | |--> | | |--> | | |--> nil 581 --- --- --- --- --- --- --- --- 582 | | | | 583 | | | | 584 --> maple -->birch --> pine --> oak 585@end group 586@end smallexample 587 588 An empty sequence contributes nothing to the value returned by 589@code{append}. As a consequence of this, a final @code{nil} argument 590forces a copy of the previous argument: 591 592@example 593@group 594trees 595 @result{} (pine oak) 596@end group 597@group 598(setq wood (append trees nil)) 599 @result{} (pine oak) 600@end group 601@group 602wood 603 @result{} (pine oak) 604@end group 605@group 606(eq wood trees) 607 @result{} nil 608@end group 609@end example 610 611@noindent 612This once was the usual way to copy a list, before the function 613@code{copy-sequence} was invented. @xref{Sequences Arrays Vectors}. 614 615 Here we show the use of vectors and strings as arguments to @code{append}: 616 617@example 618@group 619(append [a b] "cd" nil) 620 @result{} (a b 99 100) 621@end group 622@end example 623 624 With the help of @code{apply} (@pxref{Calling Functions}), we can append 625all the lists in a list of lists: 626 627@example 628@group 629(apply 'append '((a b c) nil (x y z) nil)) 630 @result{} (a b c x y z) 631@end group 632@end example 633 634 If no @var{sequences} are given, @code{nil} is returned: 635 636@example 637@group 638(append) 639 @result{} nil 640@end group 641@end example 642 643 Here are some examples where the final argument is not a list: 644 645@example 646(append '(x y) 'z) 647 @result{} (x y . z) 648(append '(x y) [z]) 649 @result{} (x y . [z]) 650@end example 651 652@noindent 653The second example shows that when the final argument is a sequence but 654not a list, the sequence's elements do not become elements of the 655resulting list. Instead, the sequence becomes the final @sc{cdr}, like 656any other non-list final argument. 657 658@defun copy-tree tree &optional vecp 659This function returns a copy of the tree @var{tree}. If @var{tree} is a 660cons cell, this makes a new cons cell with the same @sc{car} and 661@sc{cdr}, then recursively copies the @sc{car} and @sc{cdr} in the 662same way. 663 664Normally, when @var{tree} is anything other than a cons cell, 665@code{copy-tree} simply returns @var{tree}. However, if @var{vecp} is 666non-@code{nil}, it copies vectors too (and operates recursively on 667their elements). 668@end defun 669 670@defun flatten-tree tree 671This function returns a ``flattened'' copy of @var{tree}, that is, 672a list containing all the non-@code{nil} terminal nodes, or leaves, of 673the tree of cons cells rooted at @var{tree}. Leaves in the returned 674list are in the same order as in @var{tree}. 675@end defun 676 677@example 678(flatten-tree '(1 (2 . 3) nil (4 5 (6)) 7)) 679 @result{}(1 2 3 4 5 6 7) 680@end example 681 682@defun number-sequence from &optional to separation 683This function returns a list of numbers starting with @var{from} and 684incrementing by @var{separation}, and ending at or just before 685@var{to}. @var{separation} can be positive or negative and defaults 686to 1. If @var{to} is @code{nil} or numerically equal to @var{from}, 687the value is the one-element list @code{(@var{from})}. If @var{to} is 688less than @var{from} with a positive @var{separation}, or greater than 689@var{from} with a negative @var{separation}, the value is @code{nil} 690because those arguments specify an empty sequence. 691 692If @var{separation} is 0 and @var{to} is neither @code{nil} nor 693numerically equal to @var{from}, @code{number-sequence} signals an 694error, since those arguments specify an infinite sequence. 695 696All arguments are numbers. 697Floating-point arguments can be tricky, because floating-point 698arithmetic is inexact. For instance, depending on the machine, it may 699quite well happen that @code{(number-sequence 0.4 0.6 0.2)} returns 700the one element list @code{(0.4)}, whereas 701@code{(number-sequence 0.4 0.8 0.2)} returns a list with three 702elements. The @var{n}th element of the list is computed by the exact 703formula @code{(+ @var{from} (* @var{n} @var{separation}))}. Thus, if 704one wants to make sure that @var{to} is included in the list, one can 705pass an expression of this exact type for @var{to}. Alternatively, 706one can replace @var{to} with a slightly larger value (or a slightly 707more negative value if @var{separation} is negative). 708 709Some examples: 710 711@example 712(number-sequence 4 9) 713 @result{} (4 5 6 7 8 9) 714(number-sequence 9 4 -1) 715 @result{} (9 8 7 6 5 4) 716(number-sequence 9 4 -2) 717 @result{} (9 7 5) 718(number-sequence 8) 719 @result{} (8) 720(number-sequence 8 5) 721 @result{} nil 722(number-sequence 5 8 -1) 723 @result{} nil 724(number-sequence 1.5 6 2) 725 @result{} (1.5 3.5 5.5) 726@end example 727@end defun 728 729@node List Variables 730@section Modifying List Variables 731@cindex modify a list 732@cindex list modification 733 734 These functions, and one macro, provide convenient ways 735to modify a list which is stored in a variable. 736 737@defmac push element listname 738This macro creates a new list whose @sc{car} is @var{element} and 739whose @sc{cdr} is the list specified by @var{listname}, and saves that 740list in @var{listname}. In the simplest case, @var{listname} is an 741unquoted symbol naming a list, and this macro is equivalent 742to @w{@code{(setq @var{listname} (cons @var{element} @var{listname}))}}. 743 744@example 745(setq l '(a b)) 746 @result{} (a b) 747(push 'c l) 748 @result{} (c a b) 749l 750 @result{} (c a b) 751@end example 752 753More generally, @code{listname} can be a generalized variable. In 754that case, this macro does the equivalent of @w{@code{(setf 755@var{listname} (cons @var{element} @var{listname}))}}. 756@xref{Generalized Variables}. 757 758For the @code{pop} macro, which removes the first element from a list, 759@xref{List Elements}. 760@end defmac 761 762 Two functions modify lists that are the values of variables. 763 764@defun add-to-list symbol element &optional append compare-fn 765This function sets the variable @var{symbol} by consing @var{element} 766onto the old value, if @var{element} is not already a member of that 767value. It returns the resulting list, whether updated or not. The 768value of @var{symbol} had better be a list already before the call. 769@code{add-to-list} uses @var{compare-fn} to compare @var{element} 770against existing list members; if @var{compare-fn} is @code{nil}, it 771uses @code{equal}. 772 773Normally, if @var{element} is added, it is added to the front of 774@var{symbol}, but if the optional argument @var{append} is 775non-@code{nil}, it is added at the end. 776 777The argument @var{symbol} is not implicitly quoted; @code{add-to-list} 778is an ordinary function, like @code{set} and unlike @code{setq}. Quote 779the argument yourself if that is what you want. 780 781Do not use this function when @var{symbol} refers to a lexical 782variable. 783@end defun 784 785Here's a scenario showing how to use @code{add-to-list}: 786 787@example 788(setq foo '(a b)) 789 @result{} (a b) 790 791(add-to-list 'foo 'c) ;; @r{Add @code{c}.} 792 @result{} (c a b) 793 794(add-to-list 'foo 'b) ;; @r{No effect.} 795 @result{} (c a b) 796 797foo ;; @r{@code{foo} was changed.} 798 @result{} (c a b) 799@end example 800 801 An equivalent expression for @code{(add-to-list '@var{var} 802@var{value})} is this: 803 804@example 805(if (member @var{value} @var{var}) 806 @var{var} 807 (setq @var{var} (cons @var{value} @var{var}))) 808@end example 809 810@defun add-to-ordered-list symbol element &optional order 811This function sets the variable @var{symbol} by inserting 812@var{element} into the old value, which must be a list, at the 813position specified by @var{order}. If @var{element} is already a 814member of the list, its position in the list is adjusted according 815to @var{order}. Membership is tested using @code{eq}. 816This function returns the resulting list, whether updated or not. 817 818The @var{order} is typically a number (integer or float), and the 819elements of the list are sorted in non-decreasing numerical order. 820 821@var{order} may also be omitted or @code{nil}. Then the numeric order 822of @var{element} stays unchanged if it already has one; otherwise, 823@var{element} has no numeric order. Elements without a numeric list 824order are placed at the end of the list, in no particular order. 825 826Any other value for @var{order} removes the numeric order of @var{element} 827if it already has one; otherwise, it is equivalent to @code{nil}. 828 829The argument @var{symbol} is not implicitly quoted; 830@code{add-to-ordered-list} is an ordinary function, like @code{set} 831and unlike @code{setq}. Quote the argument yourself if necessary. 832 833The ordering information is stored in a hash table on @var{symbol}'s 834@code{list-order} property. 835@var{symbol} cannot refer to a lexical variable. 836@end defun 837 838Here's a scenario showing how to use @code{add-to-ordered-list}: 839 840@example 841(setq foo '()) 842 @result{} nil 843 844(add-to-ordered-list 'foo 'a 1) ;; @r{Add @code{a}.} 845 @result{} (a) 846 847(add-to-ordered-list 'foo 'c 3) ;; @r{Add @code{c}.} 848 @result{} (a c) 849 850(add-to-ordered-list 'foo 'b 2) ;; @r{Add @code{b}.} 851 @result{} (a b c) 852 853(add-to-ordered-list 'foo 'b 4) ;; @r{Move @code{b}.} 854 @result{} (a c b) 855 856(add-to-ordered-list 'foo 'd) ;; @r{Append @code{d}.} 857 @result{} (a c b d) 858 859(add-to-ordered-list 'foo 'e) ;; @r{Add @code{e}}. 860 @result{} (a c b e d) 861 862foo ;; @r{@code{foo} was changed.} 863 @result{} (a c b e d) 864@end example 865 866@node Modifying Lists 867@section Modifying Existing List Structure 868@cindex destructive list operations 869@cindex mutable lists 870 871 You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the 872primitives @code{setcar} and @code{setcdr}. These are destructive 873operations because they change existing list structure. 874Destructive operations should be applied only to mutable lists, 875that is, lists constructed via @code{cons}, @code{list} or similar 876operations. Lists created by quoting are part of the program and 877should not be changed by destructive operations. @xref{Mutability}. 878 879@cindex CL note---@code{rplaca} vs @code{setcar} 880@quotation 881@findex rplaca 882@findex rplacd 883@b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and 884@code{rplacd} to alter list structure; they change structure the same 885way as @code{setcar} and @code{setcdr}, but the Common Lisp functions 886return the cons cell while @code{setcar} and @code{setcdr} return the 887new @sc{car} or @sc{cdr}. 888@end quotation 889 890@menu 891* Setcar:: Replacing an element in a list. 892* Setcdr:: Replacing part of the list backbone. 893 This can be used to remove or add elements. 894* Rearrangement:: Reordering the elements in a list; combining lists. 895@end menu 896 897@node Setcar 898@subsection Altering List Elements with @code{setcar} 899@cindex replace list element 900@cindex list, replace element 901 902 Changing the @sc{car} of a cons cell is done with @code{setcar}. When 903used on a list, @code{setcar} replaces one element of a list with a 904different element. 905 906@defun setcar cons object 907This function stores @var{object} as the new @sc{car} of @var{cons}, 908replacing its previous @sc{car}. In other words, it changes the 909@sc{car} slot of @var{cons} to refer to @var{object}. It returns the 910value @var{object}. For example: 911 912@example 913@group 914(setq x (list 1 2)) 915 @result{} (1 2) 916@end group 917@group 918(setcar x 4) 919 @result{} 4 920@end group 921@group 922x 923 @result{} (4 2) 924@end group 925@end example 926@end defun 927 928 When a cons cell is part of the shared structure of several lists, 929storing a new @sc{car} into the cons changes one element of each of 930these lists. Here is an example: 931 932@example 933@group 934;; @r{Create two lists that are partly shared.} 935(setq x1 (list 'a 'b 'c)) 936 @result{} (a b c) 937(setq x2 (cons 'z (cdr x1))) 938 @result{} (z b c) 939@end group 940 941@group 942;; @r{Replace the @sc{car} of a shared link.} 943(setcar (cdr x1) 'foo) 944 @result{} foo 945x1 ; @r{Both lists are changed.} 946 @result{} (a foo c) 947x2 948 @result{} (z foo c) 949@end group 950 951@group 952;; @r{Replace the @sc{car} of a link that is not shared.} 953(setcar x1 'baz) 954 @result{} baz 955x1 ; @r{Only one list is changed.} 956 @result{} (baz foo c) 957x2 958 @result{} (z foo c) 959@end group 960@end example 961 962 Here is a graphical depiction of the shared structure of the two lists 963in the variables @code{x1} and @code{x2}, showing why replacing @code{b} 964changes them both: 965 966@example 967@group 968 --- --- --- --- --- --- 969x1---> | | |----> | | |--> | | |--> nil 970 --- --- --- --- --- --- 971 | --> | | 972 | | | | 973 --> a | --> b --> c 974 | 975 --- --- | 976x2--> | | |-- 977 --- --- 978 | 979 | 980 --> z 981@end group 982@end example 983 984 Here is an alternative form of box diagram, showing the same relationship: 985 986@example 987@group 988x1: 989 -------------- -------------- -------------- 990| car | cdr | | car | cdr | | car | cdr | 991| a | o------->| b | o------->| c | nil | 992| | | -->| | | | | | 993 -------------- | -------------- -------------- 994 | 995x2: | 996 -------------- | 997| car | cdr | | 998| z | o---- 999| | | 1000 -------------- 1001@end group 1002@end example 1003 1004@node Setcdr 1005@subsection Altering the CDR of a List 1006@cindex replace part of list 1007 1008 The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}: 1009 1010@defun setcdr cons object 1011This function stores @var{object} as the new @sc{cdr} of @var{cons}, 1012replacing its previous @sc{cdr}. In other words, it changes the 1013@sc{cdr} slot of @var{cons} to refer to @var{object}. It returns the 1014value @var{object}. 1015@end defun 1016 1017 Here is an example of replacing the @sc{cdr} of a list with a 1018different list. All but the first element of the list are removed in 1019favor of a different sequence of elements. The first element is 1020unchanged, because it resides in the @sc{car} of the list, and is not 1021reached via the @sc{cdr}. 1022 1023@example 1024@group 1025(setq x (list 1 2 3)) 1026 @result{} (1 2 3) 1027@end group 1028@group 1029(setcdr x '(4)) 1030 @result{} (4) 1031@end group 1032@group 1033x 1034 @result{} (1 4) 1035@end group 1036@end example 1037 1038 You can delete elements from the middle of a list by altering the 1039@sc{cdr}s of the cons cells in the list. For example, here we delete 1040the second element, @code{b}, from the list @code{(a b c)}, by changing 1041the @sc{cdr} of the first cons cell: 1042 1043@example 1044@group 1045(setq x1 (list 'a 'b 'c)) 1046 @result{} (a b c) 1047(setcdr x1 (cdr (cdr x1))) 1048 @result{} (c) 1049x1 1050 @result{} (a c) 1051@end group 1052@end example 1053 1054 Here is the result in box notation: 1055 1056@smallexample 1057@group 1058 -------------------- 1059 | | 1060 -------------- | -------------- | -------------- 1061| car | cdr | | | car | cdr | -->| car | cdr | 1062| a | o----- | b | o-------->| c | nil | 1063| | | | | | | | | 1064 -------------- -------------- -------------- 1065@end group 1066@end smallexample 1067 1068@noindent 1069The second cons cell, which previously held the element @code{b}, still 1070exists and its @sc{car} is still @code{b}, but it no longer forms part 1071of this list. 1072 1073 It is equally easy to insert a new element by changing @sc{cdr}s: 1074 1075@example 1076@group 1077(setq x1 (list 'a 'b 'c)) 1078 @result{} (a b c) 1079(setcdr x1 (cons 'd (cdr x1))) 1080 @result{} (d b c) 1081x1 1082 @result{} (a d b c) 1083@end group 1084@end example 1085 1086 Here is this result in box notation: 1087 1088@smallexample 1089@group 1090 -------------- ------------- ------------- 1091| car | cdr | | car | cdr | | car | cdr | 1092| a | o | -->| b | o------->| c | nil | 1093| | | | | | | | | | | 1094 --------- | -- | ------------- ------------- 1095 | | 1096 ----- -------- 1097 | | 1098 | --------------- | 1099 | | car | cdr | | 1100 -->| d | o------ 1101 | | | 1102 --------------- 1103@end group 1104@end smallexample 1105 1106@node Rearrangement 1107@subsection Functions that Rearrange Lists 1108@cindex rearrangement of lists 1109@cindex reordering, of elements in lists 1110@cindex modification of lists 1111 1112 Here are some functions that rearrange lists destructively by 1113modifying the @sc{cdr}s of their component cons cells. These functions 1114are destructive because they chew up the original lists passed 1115to them as arguments, relinking their cons cells to form a new list that 1116is the returned value. 1117 1118@ifnottex 1119 See @code{delq}, in @ref{Sets And Lists}, for another function 1120that modifies cons cells. 1121@end ifnottex 1122@iftex 1123 The function @code{delq} in the following section is another example 1124of destructive list manipulation. 1125@end iftex 1126 1127@defun nconc &rest lists 1128@cindex concatenating lists 1129@cindex joining lists 1130This function returns a list containing all the elements of @var{lists}. 1131Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are 1132@emph{not} copied. Instead, the last @sc{cdr} of each of the 1133@var{lists} is changed to refer to the following list. The last of the 1134@var{lists} is not altered. For example: 1135 1136@example 1137@group 1138(setq x (list 1 2 3)) 1139 @result{} (1 2 3) 1140@end group 1141@group 1142(nconc x '(4 5)) 1143 @result{} (1 2 3 4 5) 1144@end group 1145@group 1146x 1147 @result{} (1 2 3 4 5) 1148@end group 1149@end example 1150 1151 Since the last argument of @code{nconc} is not itself modified, it is 1152reasonable to use a constant list, such as @code{'(4 5)}, as in the 1153above example. For the same reason, the last argument need not be a 1154list: 1155 1156@example 1157@group 1158(setq x (list 1 2 3)) 1159 @result{} (1 2 3) 1160@end group 1161@group 1162(nconc x 'z) 1163 @result{} (1 2 3 . z) 1164@end group 1165@group 1166x 1167 @result{} (1 2 3 . z) 1168@end group 1169@end example 1170 1171However, the other arguments (all but the last) should be mutable lists. 1172 1173A common pitfall is to use a constant list as a non-last 1174argument to @code{nconc}. If you do this, the resulting behavior 1175is undefined. It is possible that your program will change 1176each time you run it! Here is what might happen (though this 1177is not guaranteed to happen): 1178 1179@smallexample 1180@group 1181(defun add-foo (x) ; @r{We want this function to add} 1182 (nconc '(foo) x)) ; @r{@code{foo} to the front of its arg.} 1183@end group 1184 1185@group 1186(symbol-function 'add-foo) 1187 @result{} (lambda (x) (nconc '(foo) x)) 1188@end group 1189 1190@group 1191(setq xx (add-foo '(1 2))) ; @r{It seems to work.} 1192 @result{} (foo 1 2) 1193@end group 1194@group 1195(setq xy (add-foo '(3 4))) ; @r{What happened?} 1196 @result{} (foo 1 2 3 4) 1197@end group 1198@group 1199(eq xx xy) 1200 @result{} t 1201@end group 1202 1203@group 1204(symbol-function 'add-foo) 1205 @result{} (lambda (x) (nconc '(foo 1 2 3 4) x)) 1206@end group 1207@end smallexample 1208@end defun 1209 1210@node Sets And Lists 1211@section Using Lists as Sets 1212@cindex lists as sets 1213@cindex sets 1214 1215 A list can represent an unordered mathematical set---simply consider a 1216value an element of a set if it appears in the list, and ignore the 1217order of the list. To form the union of two sets, use @code{append} (as 1218long as you don't mind having duplicate elements). You can remove 1219@code{equal} duplicates using @code{delete-dups}. Other useful 1220functions for sets include @code{memq} and @code{delq}, and their 1221@code{equal} versions, @code{member} and @code{delete}. 1222 1223@cindex CL note---lack @code{union}, @code{intersection} 1224@quotation 1225@b{Common Lisp note:} Common Lisp has functions @code{union} (which 1226avoids duplicate elements) and @code{intersection} for set operations. 1227In Emacs Lisp, variants of these facilities are provided by the 1228@file{cl-lib} library. @xref{Lists as Sets,,,cl,Common Lisp Extensions}. 1229@end quotation 1230 1231@defun memq object list 1232@cindex membership in a list 1233This function tests to see whether @var{object} is a member of 1234@var{list}. If it is, @code{memq} returns a list starting with the 1235first occurrence of @var{object}. Otherwise, it returns @code{nil}. 1236The letter @samp{q} in @code{memq} says that it uses @code{eq} to 1237compare @var{object} against the elements of the list. For example: 1238 1239@example 1240@group 1241(memq 'b '(a b c b a)) 1242 @result{} (b c b a) 1243@end group 1244@group 1245(memq '(2) '((1) (2))) ; @r{The two @code{(2)}s need not be @code{eq}.} 1246 @result{} @r{Unspecified; might be @code{nil} or @code{((2))}.} 1247@end group 1248@end example 1249@end defun 1250 1251@defun delq object list 1252@cindex deleting list elements 1253This function destructively removes all elements @code{eq} to 1254@var{object} from @var{list}, and returns the resulting list. The 1255letter @samp{q} in @code{delq} says that it uses @code{eq} to compare 1256@var{object} against the elements of the list, like @code{memq} and 1257@code{remq}. 1258 1259Typically, when you invoke @code{delq}, you should use the return 1260value by assigning it to the variable which held the original list. 1261The reason for this is explained below. 1262@end defun 1263 1264The @code{delq} function deletes elements from the front of the list 1265by simply advancing down the list, and returning a sublist that starts 1266after those elements. For example: 1267 1268@example 1269@group 1270(delq 'a '(a b c)) @equiv{} (cdr '(a b c)) 1271@end group 1272@end example 1273 1274@noindent 1275When an element to be deleted appears in the middle of the list, 1276removing it involves changing the @sc{cdr}s (@pxref{Setcdr}). 1277 1278@example 1279@group 1280(setq sample-list (list 'a 'b 'c '(4))) 1281 @result{} (a b c (4)) 1282@end group 1283@group 1284(delq 'a sample-list) 1285 @result{} (b c (4)) 1286@end group 1287@group 1288sample-list 1289 @result{} (a b c (4)) 1290@end group 1291@group 1292(delq 'c sample-list) 1293 @result{} (a b (4)) 1294@end group 1295@group 1296sample-list 1297 @result{} (a b (4)) 1298@end group 1299@end example 1300 1301Note that @code{(delq 'c sample-list)} modifies @code{sample-list} to 1302splice out the third element, but @code{(delq 'a sample-list)} does not 1303splice anything---it just returns a shorter list. Don't assume that a 1304variable which formerly held the argument @var{list} now has fewer 1305elements, or that it still holds the original list! Instead, save the 1306result of @code{delq} and use that. Most often we store the result back 1307into the variable that held the original list: 1308 1309@example 1310(setq flowers (delq 'rose flowers)) 1311@end example 1312 1313In the following example, the @code{(list 4)} that @code{delq} attempts to match 1314and the @code{(4)} in the @code{sample-list} are @code{equal} but not @code{eq}: 1315 1316@example 1317@group 1318(delq (list 4) sample-list) 1319 @result{} (a c (4)) 1320@end group 1321@end example 1322 1323If you want to delete elements that are @code{equal} to a given value, 1324use @code{delete} (see below). 1325 1326@defun remq object list 1327This function returns a copy of @var{list}, with all elements removed 1328which are @code{eq} to @var{object}. The letter @samp{q} in @code{remq} 1329says that it uses @code{eq} to compare @var{object} against the elements 1330of @code{list}. 1331 1332@example 1333@group 1334(setq sample-list (list 'a 'b 'c 'a 'b 'c)) 1335 @result{} (a b c a b c) 1336@end group 1337@group 1338(remq 'a sample-list) 1339 @result{} (b c b c) 1340@end group 1341@group 1342sample-list 1343 @result{} (a b c a b c) 1344@end group 1345@end example 1346@end defun 1347 1348@defun memql object list 1349The function @code{memql} tests to see whether @var{object} is a member 1350of @var{list}, comparing members with @var{object} using @code{eql}, 1351so floating-point elements are compared by value. 1352If @var{object} is a member, @code{memql} returns a list starting with 1353its first occurrence in @var{list}. Otherwise, it returns @code{nil}. 1354 1355Compare this with @code{memq}: 1356 1357@example 1358@group 1359(memql 1.2 '(1.1 1.2 1.3)) ; @r{@code{1.2} and @code{1.2} are @code{eql}.} 1360 @result{} (1.2 1.3) 1361@end group 1362@group 1363(memq 1.2 '(1.1 1.2 1.3)) ; @r{The two @code{1.2}s need not be @code{eq}.} 1364 @result{} @r{Unspecified; might be @code{nil} or @code{(1.2 1.3)}.} 1365@end group 1366@end example 1367@end defun 1368 1369The following three functions are like @code{memq}, @code{delq} and 1370@code{remq}, but use @code{equal} rather than @code{eq} to compare 1371elements. @xref{Equality Predicates}. 1372 1373@defun member object list 1374The function @code{member} tests to see whether @var{object} is a member 1375of @var{list}, comparing members with @var{object} using @code{equal}. 1376If @var{object} is a member, @code{member} returns a list starting with 1377its first occurrence in @var{list}. Otherwise, it returns @code{nil}. 1378 1379Compare this with @code{memq}: 1380 1381@example 1382@group 1383(member '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are @code{equal}.} 1384 @result{} ((2)) 1385@end group 1386@group 1387(memq '(2) '((1) (2))) ; @r{The two @code{(2)}s need not be @code{eq}.} 1388 @result{} @r{Unspecified; might be @code{nil} or @code{(2)}.} 1389@end group 1390@group 1391;; @r{Two strings with the same contents are @code{equal}.} 1392(member "foo" '("foo" "bar")) 1393 @result{} ("foo" "bar") 1394@end group 1395@end example 1396@end defun 1397 1398@defun delete object sequence 1399This function removes all elements @code{equal} to @var{object} from 1400@var{sequence}, and returns the resulting sequence. 1401 1402If @var{sequence} is a list, @code{delete} is to @code{delq} as 1403@code{member} is to @code{memq}: it uses @code{equal} to compare 1404elements with @var{object}, like @code{member}; when it finds an 1405element that matches, it cuts the element out just as @code{delq} 1406would. As with @code{delq}, you should typically use the return value 1407by assigning it to the variable which held the original list. 1408 1409If @code{sequence} is a vector or string, @code{delete} returns a copy 1410of @code{sequence} with all elements @code{equal} to @code{object} 1411removed. 1412 1413For example: 1414 1415@example 1416@group 1417(setq l (list '(2) '(1) '(2))) 1418(delete '(2) l) 1419 @result{} ((1)) 1420l 1421 @result{} ((2) (1)) 1422;; @r{If you want to change @code{l} reliably,} 1423;; @r{write @code{(setq l (delete '(2) l))}.} 1424@end group 1425@group 1426(setq l (list '(2) '(1) '(2))) 1427(delete '(1) l) 1428 @result{} ((2) (2)) 1429l 1430 @result{} ((2) (2)) 1431;; @r{In this case, it makes no difference whether you set @code{l},} 1432;; @r{but you should do so for the sake of the other case.} 1433@end group 1434@group 1435(delete '(2) [(2) (1) (2)]) 1436 @result{} [(1)] 1437@end group 1438@end example 1439@end defun 1440 1441@defun remove object sequence 1442This function is the non-destructive counterpart of @code{delete}. It 1443returns a copy of @code{sequence}, a list, vector, or string, with 1444elements @code{equal} to @code{object} removed. For example: 1445 1446@example 1447@group 1448(remove '(2) '((2) (1) (2))) 1449 @result{} ((1)) 1450@end group 1451@group 1452(remove '(2) [(2) (1) (2)]) 1453 @result{} [(1)] 1454@end group 1455@end example 1456@end defun 1457 1458@quotation 1459@b{Common Lisp note:} The functions @code{member}, @code{delete} and 1460@code{remove} in GNU Emacs Lisp are derived from Maclisp, not Common 1461Lisp. The Common Lisp versions do not use @code{equal} to compare 1462elements. 1463@end quotation 1464 1465@defun member-ignore-case object list 1466This function is like @code{member}, except that @var{object} should 1467be a string and that it ignores differences in letter-case and text 1468representation: upper-case and lower-case letters are treated as 1469equal, and unibyte strings are converted to multibyte prior to 1470comparison. 1471@end defun 1472 1473@defun delete-dups list 1474This function destructively removes all @code{equal} duplicates from 1475@var{list}, stores the result in @var{list} and returns it. Of 1476several @code{equal} occurrences of an element in @var{list}, 1477@code{delete-dups} keeps the first one. 1478@end defun 1479 1480 See also the function @code{add-to-list}, in @ref{List Variables}, 1481for a way to add an element to a list stored in a variable and used as a 1482set. 1483 1484@node Association Lists 1485@section Association Lists 1486@cindex association list 1487@cindex alist 1488 1489 An @dfn{association list}, or @dfn{alist} for short, records a mapping 1490from keys to values. It is a list of cons cells called 1491@dfn{associations}: the @sc{car} of each cons cell is the @dfn{key}, and the 1492@sc{cdr} is the @dfn{associated value}.@footnote{This usage of ``key'' 1493is not related to the term ``key sequence''; it means a value used to 1494look up an item in a table. In this case, the table is the alist, and 1495the alist associations are the items.} 1496 1497 Here is an example of an alist. The key @code{pine} is associated with 1498the value @code{cones}; the key @code{oak} is associated with 1499@code{acorns}; and the key @code{maple} is associated with @code{seeds}. 1500 1501@example 1502@group 1503((pine . cones) 1504 (oak . acorns) 1505 (maple . seeds)) 1506@end group 1507@end example 1508 1509 Both the values and the keys in an alist may be any Lisp objects. 1510For example, in the following alist, the symbol @code{a} is 1511associated with the number @code{1}, and the string @code{"b"} is 1512associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of 1513the alist element: 1514 1515@example 1516((a . 1) ("b" 2 3)) 1517@end example 1518 1519 Sometimes it is better to design an alist to store the associated 1520value in the @sc{car} of the @sc{cdr} of the element. Here is an 1521example of such an alist: 1522 1523@example 1524((rose red) (lily white) (buttercup yellow)) 1525@end example 1526 1527@noindent 1528Here we regard @code{red} as the value associated with @code{rose}. One 1529advantage of this kind of alist is that you can store other related 1530information---even a list of other items---in the @sc{cdr} of the 1531@sc{cdr}. One disadvantage is that you cannot use @code{rassq} (see 1532below) to find the element containing a given value. When neither of 1533these considerations is important, the choice is a matter of taste, as 1534long as you are consistent about it for any given alist. 1535 1536 The same alist shown above could be regarded as having the 1537associated value in the @sc{cdr} of the element; the value associated 1538with @code{rose} would be the list @code{(red)}. 1539 1540 Association lists are often used to record information that you might 1541otherwise keep on a stack, since new associations may be added easily to 1542the front of the list. When searching an association list for an 1543association with a given key, the first one found is returned, if there 1544is more than one. 1545 1546 In Emacs Lisp, it is @emph{not} an error if an element of an 1547association list is not a cons cell. The alist search functions simply 1548ignore such elements. Many other versions of Lisp signal errors in such 1549cases. 1550 1551 Note that property lists are similar to association lists in several 1552respects. A property list behaves like an association list in which 1553each key can occur only once. @xref{Property Lists}, for a comparison 1554of property lists and association lists. 1555 1556@defun assoc key alist &optional testfn 1557This function returns the first association for @var{key} in 1558@var{alist}, comparing @var{key} against the alist elements using 1559@var{testfn} if it is non-@code{nil} and @code{equal} otherwise 1560(@pxref{Equality Predicates}). It returns @code{nil} if no 1561association in @var{alist} has a @sc{car} equal to @var{key}. For 1562example: 1563 1564@smallexample 1565(setq trees '((pine . cones) (oak . acorns) (maple . seeds))) 1566 @result{} ((pine . cones) (oak . acorns) (maple . seeds)) 1567(assoc 'oak trees) 1568 @result{} (oak . acorns) 1569(cdr (assoc 'oak trees)) 1570 @result{} acorns 1571(assoc 'birch trees) 1572 @result{} nil 1573@end smallexample 1574 1575Here is another example, in which the keys and values are not symbols: 1576 1577@smallexample 1578(setq needles-per-cluster 1579 '((2 "Austrian Pine" "Red Pine") 1580 (3 "Pitch Pine") 1581 (5 "White Pine"))) 1582 1583(cdr (assoc 3 needles-per-cluster)) 1584 @result{} ("Pitch Pine") 1585(cdr (assoc 2 needles-per-cluster)) 1586 @result{} ("Austrian Pine" "Red Pine") 1587@end smallexample 1588@end defun 1589 1590 The function @code{assoc-string} is much like @code{assoc} except 1591that it ignores certain differences between strings. @xref{Text 1592Comparison}. 1593 1594@defun rassoc value alist 1595This function returns the first association with value @var{value} in 1596@var{alist}. It returns @code{nil} if no association in @var{alist} has 1597a @sc{cdr} @code{equal} to @var{value}. 1598 1599@code{rassoc} is like @code{assoc} except that it compares the @sc{cdr} of 1600each @var{alist} association instead of the @sc{car}. You can think of 1601this as reverse @code{assoc}, finding the key for a given value. 1602@end defun 1603 1604@defun assq key alist 1605This function is like @code{assoc} in that it returns the first 1606association for @var{key} in @var{alist}, but it makes the comparison 1607using @code{eq}. @code{assq} returns @code{nil} if no association in 1608@var{alist} has a @sc{car} @code{eq} to @var{key}. This function is 1609used more often than @code{assoc}, since @code{eq} is faster than 1610@code{equal} and most alists use symbols as keys. @xref{Equality 1611Predicates}. 1612 1613@smallexample 1614(setq trees '((pine . cones) (oak . acorns) (maple . seeds))) 1615 @result{} ((pine . cones) (oak . acorns) (maple . seeds)) 1616(assq 'pine trees) 1617 @result{} (pine . cones) 1618@end smallexample 1619 1620On the other hand, @code{assq} is not usually useful in alists where the 1621keys may not be symbols: 1622 1623@smallexample 1624(setq leaves 1625 '(("simple leaves" . oak) 1626 ("compound leaves" . horsechestnut))) 1627 1628(assq "simple leaves" leaves) 1629 @result{} @r{Unspecified; might be @code{nil} or @code{("simple leaves" . oak)}.} 1630(assoc "simple leaves" leaves) 1631 @result{} ("simple leaves" . oak) 1632@end smallexample 1633@end defun 1634 1635@defun alist-get key alist &optional default remove testfn 1636This function is similar to @code{assq}. It finds the first 1637association @w{@code{(@var{key} . @var{value})}} by comparing 1638@var{key} with @var{alist} elements, and, if found, returns the 1639@var{value} of that association. If no association is found, the 1640function returns @var{default}. Comparison of @var{key} against 1641@var{alist} elements uses the function specified by @var{testfn}, 1642defaulting to @code{eq}. 1643 1644This is a generalized variable (@pxref{Generalized Variables}) 1645that can be used to change a value with @code{setf}. When 1646using it to set a value, optional argument @var{remove} non-@code{nil} 1647means to remove @var{key}'s association from @var{alist} if the new 1648value is @code{eql} to @var{default}. 1649@end defun 1650 1651@defun rassq value alist 1652This function returns the first association with value @var{value} in 1653@var{alist}. It returns @code{nil} if no association in @var{alist} has 1654a @sc{cdr} @code{eq} to @var{value}. 1655 1656@code{rassq} is like @code{assq} except that it compares the @sc{cdr} of 1657each @var{alist} association instead of the @sc{car}. You can think of 1658this as reverse @code{assq}, finding the key for a given value. 1659 1660For example: 1661 1662@smallexample 1663(setq trees '((pine . cones) (oak . acorns) (maple . seeds))) 1664 1665(rassq 'acorns trees) 1666 @result{} (oak . acorns) 1667(rassq 'spores trees) 1668 @result{} nil 1669@end smallexample 1670 1671@code{rassq} cannot search for a value stored in the @sc{car} 1672of the @sc{cdr} of an element: 1673 1674@smallexample 1675(setq colors '((rose red) (lily white) (buttercup yellow))) 1676 1677(rassq 'white colors) 1678 @result{} nil 1679@end smallexample 1680 1681In this case, the @sc{cdr} of the association @code{(lily white)} is not 1682the symbol @code{white}, but rather the list @code{(white)}. This 1683becomes clearer if the association is written in dotted pair notation: 1684 1685@smallexample 1686(lily white) @equiv{} (lily . (white)) 1687@end smallexample 1688@end defun 1689 1690@defun assoc-default key alist &optional test default 1691This function searches @var{alist} for a match for @var{key}. For each 1692element of @var{alist}, it compares the element (if it is an atom) or 1693the element's @sc{car} (if it is a cons) against @var{key}, by calling 1694@var{test} with two arguments: the element or its @sc{car}, and 1695@var{key}. The arguments are passed in that order so that you can get 1696useful results using @code{string-match} with an alist that contains 1697regular expressions (@pxref{Regexp Search}). If @var{test} is omitted 1698or @code{nil}, @code{equal} is used for comparison. 1699 1700If an alist element matches @var{key} by this criterion, 1701then @code{assoc-default} returns a value based on this element. 1702If the element is a cons, then the value is the element's @sc{cdr}. 1703Otherwise, the return value is @var{default}. 1704 1705If no alist element matches @var{key}, @code{assoc-default} returns 1706@code{nil}. 1707@end defun 1708 1709@defun copy-alist alist 1710@cindex copying alists 1711This function returns a two-level deep copy of @var{alist}: it creates a 1712new copy of each association, so that you can alter the associations of 1713the new alist without changing the old one. 1714 1715@smallexample 1716@group 1717(setq needles-per-cluster 1718 '((2 . ("Austrian Pine" "Red Pine")) 1719 (3 . ("Pitch Pine")) 1720@end group 1721 (5 . ("White Pine")))) 1722@result{} 1723((2 "Austrian Pine" "Red Pine") 1724 (3 "Pitch Pine") 1725 (5 "White Pine")) 1726 1727(setq copy (copy-alist needles-per-cluster)) 1728@result{} 1729((2 "Austrian Pine" "Red Pine") 1730 (3 "Pitch Pine") 1731 (5 "White Pine")) 1732 1733(eq needles-per-cluster copy) 1734 @result{} nil 1735(equal needles-per-cluster copy) 1736 @result{} t 1737(eq (car needles-per-cluster) (car copy)) 1738 @result{} nil 1739(cdr (car (cdr needles-per-cluster))) 1740 @result{} ("Pitch Pine") 1741@group 1742(eq (cdr (car (cdr needles-per-cluster))) 1743 (cdr (car (cdr copy)))) 1744 @result{} t 1745@end group 1746@end smallexample 1747 1748 This example shows how @code{copy-alist} makes it possible to change 1749the associations of one copy without affecting the other: 1750 1751@smallexample 1752@group 1753(setcdr (assq 3 copy) '("Martian Vacuum Pine")) 1754(cdr (assq 3 needles-per-cluster)) 1755 @result{} ("Pitch Pine") 1756@end group 1757@end smallexample 1758@end defun 1759 1760@defun assq-delete-all key alist 1761This function deletes from @var{alist} all the elements whose @sc{car} 1762is @code{eq} to @var{key}, much as if you used @code{delq} to delete 1763each such element one by one. It returns the shortened alist, and 1764often modifies the original list structure of @var{alist}. For 1765correct results, use the return value of @code{assq-delete-all} rather 1766than looking at the saved value of @var{alist}. 1767 1768@example 1769(setq alist (list '(foo 1) '(bar 2) '(foo 3) '(lose 4))) 1770 @result{} ((foo 1) (bar 2) (foo 3) (lose 4)) 1771(assq-delete-all 'foo alist) 1772 @result{} ((bar 2) (lose 4)) 1773alist 1774 @result{} ((foo 1) (bar 2) (lose 4)) 1775@end example 1776@end defun 1777 1778@defun assoc-delete-all key alist &optional test 1779This function is like @code{assq-delete-all} except that it accepts 1780an optional argument @var{test}, a predicate function to compare the 1781keys in @var{alist}. If omitted or @code{nil}, @var{test} defaults to 1782@code{equal}. As @code{assq-delete-all}, this function often modifies 1783the original list structure of @var{alist}. 1784@end defun 1785 1786@defun rassq-delete-all value alist 1787This function deletes from @var{alist} all the elements whose @sc{cdr} 1788is @code{eq} to @var{value}. It returns the shortened alist, and 1789often modifies the original list structure of @var{alist}. 1790@code{rassq-delete-all} is like @code{assq-delete-all} except that it 1791compares the @sc{cdr} of each @var{alist} association instead of the 1792@sc{car}. 1793@end defun 1794 1795@defmac let-alist alist body 1796Creates a binding for each symbol used as keys the association list 1797@var{alist}, prefixed with dot. This can be useful when accessing 1798several items in the same association list, and it's best understood 1799through a simple example: 1800 1801@lisp 1802(setq colors '((rose . red) (lily . white) (buttercup . yellow))) 1803(let-alist colors 1804 (if (eq .rose 'red) 1805 .lily)) 1806=> white 1807@end lisp 1808 1809The @var{body} is inspected at compilation time, and only the symbols 1810that appear in @var{body} with a @samp{.} as the first character in 1811the symbol name will be bound. Finding the keys is done with 1812@code{assq}, and the @code{cdr} of the return value of this 1813@code{assq} is assigned as the value for the binding. 1814 1815Nested association lists is supported: 1816 1817@lisp 1818(setq colors '((rose . red) (lily (belladonna . yellow) (brindisi . pink)))) 1819(let-alist colors 1820 (if (eq .rose 'red) 1821 .lily.belladonna)) 1822=> yellow 1823@end lisp 1824 1825Nesting @code{let-alist} inside each other is allowed, but the code in 1826the inner @code{let-alist} can't access the variables bound by the 1827outer @code{let-alist}. 1828@end defmac 1829 1830@node Property Lists 1831@section Property Lists 1832@cindex property list 1833@cindex plist 1834 1835 A @dfn{property list} (@dfn{plist} for short) is a list of paired 1836elements. Each of the pairs associates a property name (usually a 1837symbol) with a property or value. Here is an example of a property 1838list: 1839 1840@example 1841(pine cones numbers (1 2 3) color "blue") 1842@end example 1843 1844@noindent 1845This property list associates @code{pine} with @code{cones}, 1846@code{numbers} with @code{(1 2 3)}, and @code{color} with 1847@code{"blue"}. The property names and values can be any Lisp objects, 1848but the names are usually symbols (as they are in this example). 1849 1850 Property lists are used in several contexts. For instance, the 1851function @code{put-text-property} takes an argument which is a 1852property list, specifying text properties and associated values which 1853are to be applied to text in a string or buffer. @xref{Text 1854Properties}. 1855 1856 Another prominent use of property lists is for storing symbol 1857properties. Every symbol possesses a list of properties, used to 1858record miscellaneous information about the symbol; these properties 1859are stored in the form of a property list. @xref{Symbol Properties}. 1860 1861@menu 1862* Plists and Alists:: Comparison of the advantages of property 1863 lists and association lists. 1864* Plist Access:: Accessing property lists stored elsewhere. 1865@end menu 1866 1867@node Plists and Alists 1868@subsection Property Lists and Association Lists 1869@cindex plist vs. alist 1870@cindex alist vs. plist 1871 1872@cindex property lists vs association lists 1873 Association lists (@pxref{Association Lists}) are very similar to 1874property lists. In contrast to association lists, the order of the 1875pairs in the property list is not significant, since the property 1876names must be distinct. 1877 1878 Property lists are better than association lists for attaching 1879information to various Lisp function names or variables. If your 1880program keeps all such information in one association list, it will 1881typically need to search that entire list each time it checks for an 1882association for a particular Lisp function name or variable, which 1883could be slow. By contrast, if you keep the same information in the 1884property lists of the function names or variables themselves, each 1885search will scan only the length of one property list, which is 1886usually short. This is why the documentation for a variable is 1887recorded in a property named @code{variable-documentation}. The byte 1888compiler likewise uses properties to record those functions needing 1889special treatment. 1890 1891 However, association lists have their own advantages. Depending on 1892your application, it may be faster to add an association to the front of 1893an association list than to update a property. All properties for a 1894symbol are stored in the same property list, so there is a possibility 1895of a conflict between different uses of a property name. (For this 1896reason, it is a good idea to choose property names that are probably 1897unique, such as by beginning the property name with the program's usual 1898name-prefix for variables and functions.) An association list may be 1899used like a stack where associations are pushed on the front of the list 1900and later discarded; this is not possible with a property list. 1901 1902@node Plist Access 1903@subsection Property Lists Outside Symbols 1904@cindex plist access 1905@cindex accessing plist properties 1906 1907 The following functions can be used to manipulate property lists. 1908They all compare property names using @code{eq}. 1909 1910@defun plist-get plist property 1911This returns the value of the @var{property} property stored in the 1912property list @var{plist}. It accepts a malformed @var{plist} 1913argument. If @var{property} is not found in the @var{plist}, it 1914returns @code{nil}. For example, 1915 1916@example 1917(plist-get '(foo 4) 'foo) 1918 @result{} 4 1919(plist-get '(foo 4 bad) 'foo) 1920 @result{} 4 1921(plist-get '(foo 4 bad) 'bad) 1922 @result{} nil 1923(plist-get '(foo 4 bad) 'bar) 1924 @result{} nil 1925@end example 1926@end defun 1927 1928@defun plist-put plist property value 1929This stores @var{value} as the value of the @var{property} property in 1930the property list @var{plist}. It may modify @var{plist} destructively, 1931or it may construct a new list structure without altering the old. The 1932function returns the modified property list, so you can store that back 1933in the place where you got @var{plist}. For example, 1934 1935@example 1936(setq my-plist (list 'bar t 'foo 4)) 1937 @result{} (bar t foo 4) 1938(setq my-plist (plist-put my-plist 'foo 69)) 1939 @result{} (bar t foo 69) 1940(setq my-plist (plist-put my-plist 'quux '(a))) 1941 @result{} (bar t foo 69 quux (a)) 1942@end example 1943@end defun 1944 1945@defun lax-plist-get plist property 1946Like @code{plist-get} except that it compares properties 1947using @code{equal} instead of @code{eq}. 1948@end defun 1949 1950@defun lax-plist-put plist property value 1951Like @code{plist-put} except that it compares properties 1952using @code{equal} instead of @code{eq}. 1953@end defun 1954 1955@defun plist-member plist property 1956This returns non-@code{nil} if @var{plist} contains the given 1957@var{property}. Unlike @code{plist-get}, this allows you to distinguish 1958between a missing property and a property with the value @code{nil}. 1959The value is actually the tail of @var{plist} whose @code{car} is 1960@var{property}. 1961@end defun 1962