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 ensure-list object 683This function returns @var{object} as a list. If @var{object} is 684already a list, the function returns it; otherwise, the function 685returns a one-element list containing @var{object}. 686 687This is usually useful if you have a variable that may or may not be a 688list, and you can then say, for instance: 689 690@lisp 691(dolist (elem (ensure-list foo)) 692 (princ elem)) 693@end lisp 694@end defun 695 696@defun number-sequence from &optional to separation 697This function returns a list of numbers starting with @var{from} and 698incrementing by @var{separation}, and ending at or just before 699@var{to}. @var{separation} can be positive or negative and defaults 700to 1. If @var{to} is @code{nil} or numerically equal to @var{from}, 701the value is the one-element list @code{(@var{from})}. If @var{to} is 702less than @var{from} with a positive @var{separation}, or greater than 703@var{from} with a negative @var{separation}, the value is @code{nil} 704because those arguments specify an empty sequence. 705 706If @var{separation} is 0 and @var{to} is neither @code{nil} nor 707numerically equal to @var{from}, @code{number-sequence} signals an 708error, since those arguments specify an infinite sequence. 709 710All arguments are numbers. 711Floating-point arguments can be tricky, because floating-point 712arithmetic is inexact. For instance, depending on the machine, it may 713quite well happen that @code{(number-sequence 0.4 0.6 0.2)} returns 714the one element list @code{(0.4)}, whereas 715@code{(number-sequence 0.4 0.8 0.2)} returns a list with three 716elements. The @var{n}th element of the list is computed by the exact 717formula @code{(+ @var{from} (* @var{n} @var{separation}))}. Thus, if 718one wants to make sure that @var{to} is included in the list, one can 719pass an expression of this exact type for @var{to}. Alternatively, 720one can replace @var{to} with a slightly larger value (or a slightly 721more negative value if @var{separation} is negative). 722 723Some examples: 724 725@example 726(number-sequence 4 9) 727 @result{} (4 5 6 7 8 9) 728(number-sequence 9 4 -1) 729 @result{} (9 8 7 6 5 4) 730(number-sequence 9 4 -2) 731 @result{} (9 7 5) 732(number-sequence 8) 733 @result{} (8) 734(number-sequence 8 5) 735 @result{} nil 736(number-sequence 5 8 -1) 737 @result{} nil 738(number-sequence 1.5 6 2) 739 @result{} (1.5 3.5 5.5) 740@end example 741@end defun 742 743@node List Variables 744@section Modifying List Variables 745@cindex modify a list 746@cindex list modification 747 748 These functions, and one macro, provide convenient ways 749to modify a list which is stored in a variable. 750 751@defmac push element listname 752This macro creates a new list whose @sc{car} is @var{element} and 753whose @sc{cdr} is the list specified by @var{listname}, and saves that 754list in @var{listname}. In the simplest case, @var{listname} is an 755unquoted symbol naming a list, and this macro is equivalent 756to @w{@code{(setq @var{listname} (cons @var{element} @var{listname}))}}. 757 758@example 759(setq l '(a b)) 760 @result{} (a b) 761(push 'c l) 762 @result{} (c a b) 763l 764 @result{} (c a b) 765@end example 766 767More generally, @code{listname} can be a generalized variable. In 768that case, this macro does the equivalent of @w{@code{(setf 769@var{listname} (cons @var{element} @var{listname}))}}. 770@xref{Generalized Variables}. 771 772For the @code{pop} macro, which removes the first element from a list, 773@xref{List Elements}. 774@end defmac 775 776 Two functions modify lists that are the values of variables. 777 778@defun add-to-list symbol element &optional append compare-fn 779This function sets the variable @var{symbol} by consing @var{element} 780onto the old value, if @var{element} is not already a member of that 781value. It returns the resulting list, whether updated or not. The 782value of @var{symbol} had better be a list already before the call. 783@code{add-to-list} uses @var{compare-fn} to compare @var{element} 784against existing list members; if @var{compare-fn} is @code{nil}, it 785uses @code{equal}. 786 787Normally, if @var{element} is added, it is added to the front of 788@var{symbol}, but if the optional argument @var{append} is 789non-@code{nil}, it is added at the end. 790 791The argument @var{symbol} is not implicitly quoted; @code{add-to-list} 792is an ordinary function, like @code{set} and unlike @code{setq}. Quote 793the argument yourself if that is what you want. 794 795Do not use this function when @var{symbol} refers to a lexical 796variable. 797@end defun 798 799Here's a scenario showing how to use @code{add-to-list}: 800 801@example 802(setq foo '(a b)) 803 @result{} (a b) 804 805(add-to-list 'foo 'c) ;; @r{Add @code{c}.} 806 @result{} (c a b) 807 808(add-to-list 'foo 'b) ;; @r{No effect.} 809 @result{} (c a b) 810 811foo ;; @r{@code{foo} was changed.} 812 @result{} (c a b) 813@end example 814 815 An equivalent expression for @code{(add-to-list '@var{var} 816@var{value})} is this: 817 818@example 819(if (member @var{value} @var{var}) 820 @var{var} 821 (setq @var{var} (cons @var{value} @var{var}))) 822@end example 823 824@defun add-to-ordered-list symbol element &optional order 825This function sets the variable @var{symbol} by inserting 826@var{element} into the old value, which must be a list, at the 827position specified by @var{order}. If @var{element} is already a 828member of the list, its position in the list is adjusted according 829to @var{order}. Membership is tested using @code{eq}. 830This function returns the resulting list, whether updated or not. 831 832The @var{order} is typically a number (integer or float), and the 833elements of the list are sorted in non-decreasing numerical order. 834 835@var{order} may also be omitted or @code{nil}. Then the numeric order 836of @var{element} stays unchanged if it already has one; otherwise, 837@var{element} has no numeric order. Elements without a numeric list 838order are placed at the end of the list, in no particular order. 839 840Any other value for @var{order} removes the numeric order of @var{element} 841if it already has one; otherwise, it is equivalent to @code{nil}. 842 843The argument @var{symbol} is not implicitly quoted; 844@code{add-to-ordered-list} is an ordinary function, like @code{set} 845and unlike @code{setq}. Quote the argument yourself if necessary. 846 847The ordering information is stored in a hash table on @var{symbol}'s 848@code{list-order} property. 849@var{symbol} cannot refer to a lexical variable. 850@end defun 851 852Here's a scenario showing how to use @code{add-to-ordered-list}: 853 854@example 855(setq foo '()) 856 @result{} nil 857 858(add-to-ordered-list 'foo 'a 1) ;; @r{Add @code{a}.} 859 @result{} (a) 860 861(add-to-ordered-list 'foo 'c 3) ;; @r{Add @code{c}.} 862 @result{} (a c) 863 864(add-to-ordered-list 'foo 'b 2) ;; @r{Add @code{b}.} 865 @result{} (a b c) 866 867(add-to-ordered-list 'foo 'b 4) ;; @r{Move @code{b}.} 868 @result{} (a c b) 869 870(add-to-ordered-list 'foo 'd) ;; @r{Append @code{d}.} 871 @result{} (a c b d) 872 873(add-to-ordered-list 'foo 'e) ;; @r{Add @code{e}}. 874 @result{} (a c b e d) 875 876foo ;; @r{@code{foo} was changed.} 877 @result{} (a c b e d) 878@end example 879 880@node Modifying Lists 881@section Modifying Existing List Structure 882@cindex destructive list operations 883@cindex mutable lists 884 885 You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the 886primitives @code{setcar} and @code{setcdr}. These are destructive 887operations because they change existing list structure. 888Destructive operations should be applied only to mutable lists, 889that is, lists constructed via @code{cons}, @code{list} or similar 890operations. Lists created by quoting are part of the program and 891should not be changed by destructive operations. @xref{Mutability}. 892 893@cindex CL note---@code{rplaca} vs @code{setcar} 894@quotation 895@findex rplaca 896@findex rplacd 897@b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and 898@code{rplacd} to alter list structure; they change structure the same 899way as @code{setcar} and @code{setcdr}, but the Common Lisp functions 900return the cons cell while @code{setcar} and @code{setcdr} return the 901new @sc{car} or @sc{cdr}. 902@end quotation 903 904@menu 905* Setcar:: Replacing an element in a list. 906* Setcdr:: Replacing part of the list backbone. 907 This can be used to remove or add elements. 908* Rearrangement:: Reordering the elements in a list; combining lists. 909@end menu 910 911@node Setcar 912@subsection Altering List Elements with @code{setcar} 913@cindex replace list element 914@cindex list, replace element 915 916 Changing the @sc{car} of a cons cell is done with @code{setcar}. When 917used on a list, @code{setcar} replaces one element of a list with a 918different element. 919 920@defun setcar cons object 921This function stores @var{object} as the new @sc{car} of @var{cons}, 922replacing its previous @sc{car}. In other words, it changes the 923@sc{car} slot of @var{cons} to refer to @var{object}. It returns the 924value @var{object}. For example: 925 926@example 927@group 928(setq x (list 1 2)) 929 @result{} (1 2) 930@end group 931@group 932(setcar x 4) 933 @result{} 4 934@end group 935@group 936x 937 @result{} (4 2) 938@end group 939@end example 940@end defun 941 942 When a cons cell is part of the shared structure of several lists, 943storing a new @sc{car} into the cons changes one element of each of 944these lists. Here is an example: 945 946@example 947@group 948;; @r{Create two lists that are partly shared.} 949(setq x1 (list 'a 'b 'c)) 950 @result{} (a b c) 951(setq x2 (cons 'z (cdr x1))) 952 @result{} (z b c) 953@end group 954 955@group 956;; @r{Replace the @sc{car} of a shared link.} 957(setcar (cdr x1) 'foo) 958 @result{} foo 959x1 ; @r{Both lists are changed.} 960 @result{} (a foo c) 961x2 962 @result{} (z foo c) 963@end group 964 965@group 966;; @r{Replace the @sc{car} of a link that is not shared.} 967(setcar x1 'baz) 968 @result{} baz 969x1 ; @r{Only one list is changed.} 970 @result{} (baz foo c) 971x2 972 @result{} (z foo c) 973@end group 974@end example 975 976 Here is a graphical depiction of the shared structure of the two lists 977in the variables @code{x1} and @code{x2}, showing why replacing @code{b} 978changes them both: 979 980@example 981@group 982 --- --- --- --- --- --- 983x1---> | | |----> | | |--> | | |--> nil 984 --- --- --- --- --- --- 985 | --> | | 986 | | | | 987 --> a | --> b --> c 988 | 989 --- --- | 990x2--> | | |-- 991 --- --- 992 | 993 | 994 --> z 995@end group 996@end example 997 998 Here is an alternative form of box diagram, showing the same relationship: 999 1000@example 1001@group 1002x1: 1003 -------------- -------------- -------------- 1004| car | cdr | | car | cdr | | car | cdr | 1005| a | o------->| b | o------->| c | nil | 1006| | | -->| | | | | | 1007 -------------- | -------------- -------------- 1008 | 1009x2: | 1010 -------------- | 1011| car | cdr | | 1012| z | o---- 1013| | | 1014 -------------- 1015@end group 1016@end example 1017 1018@node Setcdr 1019@subsection Altering the CDR of a List 1020@cindex replace part of list 1021 1022 The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}: 1023 1024@defun setcdr cons object 1025This function stores @var{object} as the new @sc{cdr} of @var{cons}, 1026replacing its previous @sc{cdr}. In other words, it changes the 1027@sc{cdr} slot of @var{cons} to refer to @var{object}. It returns the 1028value @var{object}. 1029@end defun 1030 1031 Here is an example of replacing the @sc{cdr} of a list with a 1032different list. All but the first element of the list are removed in 1033favor of a different sequence of elements. The first element is 1034unchanged, because it resides in the @sc{car} of the list, and is not 1035reached via the @sc{cdr}. 1036 1037@example 1038@group 1039(setq x (list 1 2 3)) 1040 @result{} (1 2 3) 1041@end group 1042@group 1043(setcdr x '(4)) 1044 @result{} (4) 1045@end group 1046@group 1047x 1048 @result{} (1 4) 1049@end group 1050@end example 1051 1052 You can delete elements from the middle of a list by altering the 1053@sc{cdr}s of the cons cells in the list. For example, here we delete 1054the second element, @code{b}, from the list @code{(a b c)}, by changing 1055the @sc{cdr} of the first cons cell: 1056 1057@example 1058@group 1059(setq x1 (list 'a 'b 'c)) 1060 @result{} (a b c) 1061(setcdr x1 (cdr (cdr x1))) 1062 @result{} (c) 1063x1 1064 @result{} (a c) 1065@end group 1066@end example 1067 1068 Here is the result in box notation: 1069 1070@smallexample 1071@group 1072 -------------------- 1073 | | 1074 -------------- | -------------- | -------------- 1075| car | cdr | | | car | cdr | -->| car | cdr | 1076| a | o----- | b | o-------->| c | nil | 1077| | | | | | | | | 1078 -------------- -------------- -------------- 1079@end group 1080@end smallexample 1081 1082@noindent 1083The second cons cell, which previously held the element @code{b}, still 1084exists and its @sc{car} is still @code{b}, but it no longer forms part 1085of this list. 1086 1087 It is equally easy to insert a new element by changing @sc{cdr}s: 1088 1089@example 1090@group 1091(setq x1 (list 'a 'b 'c)) 1092 @result{} (a b c) 1093(setcdr x1 (cons 'd (cdr x1))) 1094 @result{} (d b c) 1095x1 1096 @result{} (a d b c) 1097@end group 1098@end example 1099 1100 Here is this result in box notation: 1101 1102@smallexample 1103@group 1104 -------------- ------------- ------------- 1105| car | cdr | | car | cdr | | car | cdr | 1106| a | o | -->| b | o------->| c | nil | 1107| | | | | | | | | | | 1108 --------- | -- | ------------- ------------- 1109 | | 1110 ----- -------- 1111 | | 1112 | --------------- | 1113 | | car | cdr | | 1114 -->| d | o------ 1115 | | | 1116 --------------- 1117@end group 1118@end smallexample 1119 1120@node Rearrangement 1121@subsection Functions that Rearrange Lists 1122@cindex rearrangement of lists 1123@cindex reordering, of elements in lists 1124@cindex modification of lists 1125 1126 Here are some functions that rearrange lists destructively by 1127modifying the @sc{cdr}s of their component cons cells. These functions 1128are destructive because they chew up the original lists passed 1129to them as arguments, relinking their cons cells to form a new list that 1130is the returned value. 1131 1132@ifnottex 1133 See @code{delq}, in @ref{Sets And Lists}, for another function 1134that modifies cons cells. 1135@end ifnottex 1136@iftex 1137 The function @code{delq} in the following section is another example 1138of destructive list manipulation. 1139@end iftex 1140 1141@defun nconc &rest lists 1142@cindex concatenating lists 1143@cindex joining lists 1144This function returns a list containing all the elements of @var{lists}. 1145Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are 1146@emph{not} copied. Instead, the last @sc{cdr} of each of the 1147@var{lists} is changed to refer to the following list. The last of the 1148@var{lists} is not altered. For example: 1149 1150@example 1151@group 1152(setq x (list 1 2 3)) 1153 @result{} (1 2 3) 1154@end group 1155@group 1156(nconc x '(4 5)) 1157 @result{} (1 2 3 4 5) 1158@end group 1159@group 1160x 1161 @result{} (1 2 3 4 5) 1162@end group 1163@end example 1164 1165 Since the last argument of @code{nconc} is not itself modified, it is 1166reasonable to use a constant list, such as @code{'(4 5)}, as in the 1167above example. For the same reason, the last argument need not be a 1168list: 1169 1170@example 1171@group 1172(setq x (list 1 2 3)) 1173 @result{} (1 2 3) 1174@end group 1175@group 1176(nconc x 'z) 1177 @result{} (1 2 3 . z) 1178@end group 1179@group 1180x 1181 @result{} (1 2 3 . z) 1182@end group 1183@end example 1184 1185However, the other arguments (all but the last) should be mutable 1186lists. 1187 1188A common pitfall is to use a constant list as a non-last argument to 1189@code{nconc}. If you do this, the resulting behavior is undefined 1190(@pxref{Self-Evaluating Forms}). It is possible that your program 1191will change each time you run it! Here is what might happen (though 1192this is not guaranteed to happen): 1193 1194@smallexample 1195@group 1196(defun add-foo (x) ; @r{We want this function to add} 1197 (nconc '(foo) x)) ; @r{@code{foo} to the front of its arg.} 1198@end group 1199 1200@group 1201(symbol-function 'add-foo) 1202 @result{} (lambda (x) (nconc '(foo) x)) 1203@end group 1204 1205@group 1206(setq xx (add-foo '(1 2))) ; @r{It seems to work.} 1207 @result{} (foo 1 2) 1208@end group 1209@group 1210(setq xy (add-foo '(3 4))) ; @r{What happened?} 1211 @result{} (foo 1 2 3 4) 1212@end group 1213@group 1214(eq xx xy) 1215 @result{} t 1216@end group 1217 1218@group 1219(symbol-function 'add-foo) 1220 @result{} (lambda (x) (nconc '(foo 1 2 3 4) x)) 1221@end group 1222@end smallexample 1223@end defun 1224 1225@node Sets And Lists 1226@section Using Lists as Sets 1227@cindex lists as sets 1228@cindex sets 1229 1230 A list can represent an unordered mathematical set---simply consider 1231a value an element of a set if it appears in the list, and ignore the 1232order of the list. To form the union of two sets, use @code{append} 1233(as long as you don't mind having duplicate elements). You can remove 1234@code{equal} duplicates using @code{delete-dups} or @code{seq-uniq}. 1235Other useful functions for sets include @code{memq} and @code{delq}, 1236and their @code{equal} versions, @code{member} and @code{delete}. 1237 1238@cindex CL note---lack @code{union}, @code{intersection} 1239@quotation 1240@b{Common Lisp note:} Common Lisp has functions @code{union} (which 1241avoids duplicate elements) and @code{intersection} for set operations. 1242In Emacs Lisp, variants of these facilities are provided by the 1243@file{cl-lib} library. @xref{Lists as Sets,,,cl,Common Lisp Extensions}. 1244@end quotation 1245 1246@defun memq object list 1247@cindex membership in a list 1248This function tests to see whether @var{object} is a member of 1249@var{list}. If it is, @code{memq} returns a list starting with the 1250first occurrence of @var{object}. Otherwise, it returns @code{nil}. 1251The letter @samp{q} in @code{memq} says that it uses @code{eq} to 1252compare @var{object} against the elements of the list. For example: 1253 1254@example 1255@group 1256(memq 'b '(a b c b a)) 1257 @result{} (b c b a) 1258@end group 1259@group 1260(memq '(2) '((1) (2))) ; @r{The two @code{(2)}s need not be @code{eq}.} 1261 @result{} @r{Unspecified; might be @code{nil} or @code{((2))}.} 1262@end group 1263@end example 1264@end defun 1265 1266@defun delq object list 1267@cindex deleting list elements 1268This function destructively removes all elements @code{eq} to 1269@var{object} from @var{list}, and returns the resulting list. The 1270letter @samp{q} in @code{delq} says that it uses @code{eq} to compare 1271@var{object} against the elements of the list, like @code{memq} and 1272@code{remq}. 1273 1274Typically, when you invoke @code{delq}, you should use the return 1275value by assigning it to the variable which held the original list. 1276The reason for this is explained below. 1277@end defun 1278 1279The @code{delq} function deletes elements from the front of the list 1280by simply advancing down the list, and returning a sublist that starts 1281after those elements. For example: 1282 1283@example 1284@group 1285(delq 'a '(a b c)) @equiv{} (cdr '(a b c)) 1286@end group 1287@end example 1288 1289@noindent 1290When an element to be deleted appears in the middle of the list, 1291removing it involves changing the @sc{cdr}s (@pxref{Setcdr}). 1292 1293@example 1294@group 1295(setq sample-list (list 'a 'b 'c '(4))) 1296 @result{} (a b c (4)) 1297@end group 1298@group 1299(delq 'a sample-list) 1300 @result{} (b c (4)) 1301@end group 1302@group 1303sample-list 1304 @result{} (a b c (4)) 1305@end group 1306@group 1307(delq 'c sample-list) 1308 @result{} (a b (4)) 1309@end group 1310@group 1311sample-list 1312 @result{} (a b (4)) 1313@end group 1314@end example 1315 1316Note that @code{(delq 'c sample-list)} modifies @code{sample-list} to 1317splice out the third element, but @code{(delq 'a sample-list)} does not 1318splice anything---it just returns a shorter list. Don't assume that a 1319variable which formerly held the argument @var{list} now has fewer 1320elements, or that it still holds the original list! Instead, save the 1321result of @code{delq} and use that. Most often we store the result back 1322into the variable that held the original list: 1323 1324@example 1325(setq flowers (delq 'rose flowers)) 1326@end example 1327 1328In the following example, the @code{(list 4)} that @code{delq} attempts to match 1329and the @code{(4)} in the @code{sample-list} are @code{equal} but not @code{eq}: 1330 1331@example 1332@group 1333(delq (list 4) sample-list) 1334 @result{} (a c (4)) 1335@end group 1336@end example 1337 1338If you want to delete elements that are @code{equal} to a given value, 1339use @code{delete} (see below). 1340 1341@defun remq object list 1342This function returns a copy of @var{list}, with all elements removed 1343which are @code{eq} to @var{object}. The letter @samp{q} in @code{remq} 1344says that it uses @code{eq} to compare @var{object} against the elements 1345of @code{list}. 1346 1347@example 1348@group 1349(setq sample-list (list 'a 'b 'c 'a 'b 'c)) 1350 @result{} (a b c a b c) 1351@end group 1352@group 1353(remq 'a sample-list) 1354 @result{} (b c b c) 1355@end group 1356@group 1357sample-list 1358 @result{} (a b c a b c) 1359@end group 1360@end example 1361@end defun 1362 1363@defun memql object list 1364The function @code{memql} tests to see whether @var{object} is a member 1365of @var{list}, comparing members with @var{object} using @code{eql}, 1366so floating-point elements are compared by value. 1367If @var{object} is a member, @code{memql} returns a list starting with 1368its first occurrence in @var{list}. Otherwise, it returns @code{nil}. 1369 1370Compare this with @code{memq}: 1371 1372@example 1373@group 1374(memql 1.2 '(1.1 1.2 1.3)) ; @r{@code{1.2} and @code{1.2} are @code{eql}.} 1375 @result{} (1.2 1.3) 1376@end group 1377@group 1378(memq 1.2 '(1.1 1.2 1.3)) ; @r{The two @code{1.2}s need not be @code{eq}.} 1379 @result{} @r{Unspecified; might be @code{nil} or @code{(1.2 1.3)}.} 1380@end group 1381@end example 1382@end defun 1383 1384The following three functions are like @code{memq}, @code{delq} and 1385@code{remq}, but use @code{equal} rather than @code{eq} to compare 1386elements. @xref{Equality Predicates}. 1387 1388@defun member object list 1389The function @code{member} tests to see whether @var{object} is a member 1390of @var{list}, comparing members with @var{object} using @code{equal}. 1391If @var{object} is a member, @code{member} returns a list starting with 1392its first occurrence in @var{list}. Otherwise, it returns @code{nil}. 1393 1394Compare this with @code{memq}: 1395 1396@example 1397@group 1398(member '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are @code{equal}.} 1399 @result{} ((2)) 1400@end group 1401@group 1402(memq '(2) '((1) (2))) ; @r{The two @code{(2)}s need not be @code{eq}.} 1403 @result{} @r{Unspecified; might be @code{nil} or @code{(2)}.} 1404@end group 1405@group 1406;; @r{Two strings with the same contents are @code{equal}.} 1407(member "foo" '("foo" "bar")) 1408 @result{} ("foo" "bar") 1409@end group 1410@end example 1411@end defun 1412 1413@defun delete object sequence 1414This function removes all elements @code{equal} to @var{object} from 1415@var{sequence}, and returns the resulting sequence. 1416 1417If @var{sequence} is a list, @code{delete} is to @code{delq} as 1418@code{member} is to @code{memq}: it uses @code{equal} to compare 1419elements with @var{object}, like @code{member}; when it finds an 1420element that matches, it cuts the element out just as @code{delq} 1421would. As with @code{delq}, you should typically use the return value 1422by assigning it to the variable which held the original list. 1423 1424If @code{sequence} is a vector or string, @code{delete} returns a copy 1425of @code{sequence} with all elements @code{equal} to @code{object} 1426removed. 1427 1428For example: 1429 1430@example 1431@group 1432(setq l (list '(2) '(1) '(2))) 1433(delete '(2) l) 1434 @result{} ((1)) 1435l 1436 @result{} ((2) (1)) 1437;; @r{If you want to change @code{l} reliably,} 1438;; @r{write @code{(setq l (delete '(2) l))}.} 1439@end group 1440@group 1441(setq l (list '(2) '(1) '(2))) 1442(delete '(1) l) 1443 @result{} ((2) (2)) 1444l 1445 @result{} ((2) (2)) 1446;; @r{In this case, it makes no difference whether you set @code{l},} 1447;; @r{but you should do so for the sake of the other case.} 1448@end group 1449@group 1450(delete '(2) [(2) (1) (2)]) 1451 @result{} [(1)] 1452@end group 1453@end example 1454@end defun 1455 1456@defun remove object sequence 1457This function is the non-destructive counterpart of @code{delete}. It 1458returns a copy of @code{sequence}, a list, vector, or string, with 1459elements @code{equal} to @code{object} removed. For example: 1460 1461@example 1462@group 1463(remove '(2) '((2) (1) (2))) 1464 @result{} ((1)) 1465@end group 1466@group 1467(remove '(2) [(2) (1) (2)]) 1468 @result{} [(1)] 1469@end group 1470@end example 1471@end defun 1472 1473@quotation 1474@b{Common Lisp note:} The functions @code{member}, @code{delete} and 1475@code{remove} in GNU Emacs Lisp are derived from Maclisp, not Common 1476Lisp. The Common Lisp versions do not use @code{equal} to compare 1477elements. 1478@end quotation 1479 1480@defun member-ignore-case object list 1481This function is like @code{member}, except that @var{object} should 1482be a string and that it ignores differences in letter-case and text 1483representation: upper-case and lower-case letters are treated as 1484equal, and unibyte strings are converted to multibyte prior to 1485comparison. 1486@end defun 1487 1488@defun delete-dups list 1489This function destructively removes all @code{equal} duplicates from 1490@var{list}, stores the result in @var{list} and returns it. Of 1491several @code{equal} occurrences of an element in @var{list}, 1492@code{delete-dups} keeps the first one. See @code{seq-uniq} for 1493non-destructive operation (@pxref{Sequence Functions}). 1494@end defun 1495 1496 See also the function @code{add-to-list}, in @ref{List Variables}, 1497for a way to add an element to a list stored in a variable and used as a 1498set. 1499 1500@node Association Lists 1501@section Association Lists 1502@cindex association list 1503@cindex alist 1504 1505 An @dfn{association list}, or @dfn{alist} for short, records a mapping 1506from keys to values. It is a list of cons cells called 1507@dfn{associations}: the @sc{car} of each cons cell is the @dfn{key}, and the 1508@sc{cdr} is the @dfn{associated value}.@footnote{This usage of ``key'' 1509is not related to the term ``key sequence''; it means a value used to 1510look up an item in a table. In this case, the table is the alist, and 1511the alist associations are the items.} 1512 1513 Here is an example of an alist. The key @code{pine} is associated with 1514the value @code{cones}; the key @code{oak} is associated with 1515@code{acorns}; and the key @code{maple} is associated with @code{seeds}. 1516 1517@example 1518@group 1519((pine . cones) 1520 (oak . acorns) 1521 (maple . seeds)) 1522@end group 1523@end example 1524 1525 Both the values and the keys in an alist may be any Lisp objects. 1526For example, in the following alist, the symbol @code{a} is 1527associated with the number @code{1}, and the string @code{"b"} is 1528associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of 1529the alist element: 1530 1531@example 1532((a . 1) ("b" 2 3)) 1533@end example 1534 1535 Sometimes it is better to design an alist to store the associated 1536value in the @sc{car} of the @sc{cdr} of the element. Here is an 1537example of such an alist: 1538 1539@example 1540((rose red) (lily white) (buttercup yellow)) 1541@end example 1542 1543@noindent 1544Here we regard @code{red} as the value associated with @code{rose}. One 1545advantage of this kind of alist is that you can store other related 1546information---even a list of other items---in the @sc{cdr} of the 1547@sc{cdr}. One disadvantage is that you cannot use @code{rassq} (see 1548below) to find the element containing a given value. When neither of 1549these considerations is important, the choice is a matter of taste, as 1550long as you are consistent about it for any given alist. 1551 1552 The same alist shown above could be regarded as having the 1553associated value in the @sc{cdr} of the element; the value associated 1554with @code{rose} would be the list @code{(red)}. 1555 1556 Association lists are often used to record information that you might 1557otherwise keep on a stack, since new associations may be added easily to 1558the front of the list. When searching an association list for an 1559association with a given key, the first one found is returned, if there 1560is more than one. 1561 1562 In Emacs Lisp, it is @emph{not} an error if an element of an 1563association list is not a cons cell. The alist search functions simply 1564ignore such elements. Many other versions of Lisp signal errors in such 1565cases. 1566 1567 Note that property lists are similar to association lists in several 1568respects. A property list behaves like an association list in which 1569each key can occur only once. @xref{Property Lists}, for a comparison 1570of property lists and association lists. 1571 1572@defun assoc key alist &optional testfn 1573This function returns the first association for @var{key} in 1574@var{alist}, comparing @var{key} against the alist elements using 1575@var{testfn} if it is a function, and @code{equal} otherwise 1576(@pxref{Equality Predicates}). If @var{testfn} is a function, it is 1577called with two arguments: the @sc{car} of an element from @var{alist} 1578and @var{key}. The function returns @code{nil} if no 1579association in @var{alist} has a @sc{car} equal to @var{key}, as 1580tested by @var{testfn}. For example: 1581 1582@smallexample 1583(setq trees '((pine . cones) (oak . acorns) (maple . seeds))) 1584 @result{} ((pine . cones) (oak . acorns) (maple . seeds)) 1585(assoc 'oak trees) 1586 @result{} (oak . acorns) 1587(cdr (assoc 'oak trees)) 1588 @result{} acorns 1589(assoc 'birch trees) 1590 @result{} nil 1591@end smallexample 1592 1593Here is another example, in which the keys and values are not symbols: 1594 1595@smallexample 1596(setq needles-per-cluster 1597 '((2 "Austrian Pine" "Red Pine") 1598 (3 "Pitch Pine") 1599 (5 "White Pine"))) 1600 1601(cdr (assoc 3 needles-per-cluster)) 1602 @result{} ("Pitch Pine") 1603(cdr (assoc 2 needles-per-cluster)) 1604 @result{} ("Austrian Pine" "Red Pine") 1605@end smallexample 1606@end defun 1607 1608 The function @code{assoc-string} is much like @code{assoc} except 1609that it ignores certain differences between strings. @xref{Text 1610Comparison}. 1611 1612@defun rassoc value alist 1613This function returns the first association with value @var{value} in 1614@var{alist}. It returns @code{nil} if no association in @var{alist} has 1615a @sc{cdr} @code{equal} to @var{value}. 1616 1617@code{rassoc} is like @code{assoc} except that it compares the @sc{cdr} of 1618each @var{alist} association instead of the @sc{car}. You can think of 1619this as reverse @code{assoc}, finding the key for a given value. 1620@end defun 1621 1622@defun assq key alist 1623This function is like @code{assoc} in that it returns the first 1624association for @var{key} in @var{alist}, but it makes the comparison 1625using @code{eq}. @code{assq} returns @code{nil} if no association in 1626@var{alist} has a @sc{car} @code{eq} to @var{key}. This function is 1627used more often than @code{assoc}, since @code{eq} is faster than 1628@code{equal} and most alists use symbols as keys. @xref{Equality 1629Predicates}. 1630 1631@smallexample 1632(setq trees '((pine . cones) (oak . acorns) (maple . seeds))) 1633 @result{} ((pine . cones) (oak . acorns) (maple . seeds)) 1634(assq 'pine trees) 1635 @result{} (pine . cones) 1636@end smallexample 1637 1638On the other hand, @code{assq} is not usually useful in alists where the 1639keys may not be symbols: 1640 1641@smallexample 1642(setq leaves 1643 '(("simple leaves" . oak) 1644 ("compound leaves" . horsechestnut))) 1645 1646(assq "simple leaves" leaves) 1647 @result{} @r{Unspecified; might be @code{nil} or @code{("simple leaves" . oak)}.} 1648(assoc "simple leaves" leaves) 1649 @result{} ("simple leaves" . oak) 1650@end smallexample 1651@end defun 1652 1653@defun alist-get key alist &optional default remove testfn 1654This function is similar to @code{assq}. It finds the first 1655association @w{@code{(@var{key} . @var{value})}} by comparing 1656@var{key} with @var{alist} elements, and, if found, returns the 1657@var{value} of that association. If no association is found, the 1658function returns @var{default}. Comparison of @var{key} against 1659@var{alist} elements uses the function specified by @var{testfn}, 1660defaulting to @code{eq}. 1661 1662This is a generalized variable (@pxref{Generalized Variables}) 1663that can be used to change a value with @code{setf}. When 1664using it to set a value, optional argument @var{remove} non-@code{nil} 1665means to remove @var{key}'s association from @var{alist} if the new 1666value is @code{eql} to @var{default}. 1667@end defun 1668 1669@defun rassq value alist 1670This function returns the first association with value @var{value} in 1671@var{alist}. It returns @code{nil} if no association in @var{alist} has 1672a @sc{cdr} @code{eq} to @var{value}. 1673 1674@code{rassq} is like @code{assq} except that it compares the @sc{cdr} of 1675each @var{alist} association instead of the @sc{car}. You can think of 1676this as reverse @code{assq}, finding the key for a given value. 1677 1678For example: 1679 1680@smallexample 1681(setq trees '((pine . cones) (oak . acorns) (maple . seeds))) 1682 1683(rassq 'acorns trees) 1684 @result{} (oak . acorns) 1685(rassq 'spores trees) 1686 @result{} nil 1687@end smallexample 1688 1689@code{rassq} cannot search for a value stored in the @sc{car} 1690of the @sc{cdr} of an element: 1691 1692@smallexample 1693(setq colors '((rose red) (lily white) (buttercup yellow))) 1694 1695(rassq 'white colors) 1696 @result{} nil 1697@end smallexample 1698 1699In this case, the @sc{cdr} of the association @code{(lily white)} is not 1700the symbol @code{white}, but rather the list @code{(white)}. This 1701becomes clearer if the association is written in dotted pair notation: 1702 1703@smallexample 1704(lily white) @equiv{} (lily . (white)) 1705@end smallexample 1706@end defun 1707 1708@defun assoc-default key alist &optional test default 1709This function searches @var{alist} for a match for @var{key}. For each 1710element of @var{alist}, it compares the element (if it is an atom) or 1711the element's @sc{car} (if it is a cons) against @var{key}, by calling 1712@var{test} with two arguments: the element or its @sc{car}, and 1713@var{key}. The arguments are passed in that order so that you can get 1714useful results using @code{string-match} with an alist that contains 1715regular expressions (@pxref{Regexp Search}). If @var{test} is omitted 1716or @code{nil}, @code{equal} is used for comparison. 1717 1718If an alist element matches @var{key} by this criterion, 1719then @code{assoc-default} returns a value based on this element. 1720If the element is a cons, then the value is the element's @sc{cdr}. 1721Otherwise, the return value is @var{default}. 1722 1723If no alist element matches @var{key}, @code{assoc-default} returns 1724@code{nil}. 1725@end defun 1726 1727@defun copy-alist alist 1728@cindex copying alists 1729This function returns a two-level deep copy of @var{alist}: it creates a 1730new copy of each association, so that you can alter the associations of 1731the new alist without changing the old one. 1732 1733@smallexample 1734@group 1735(setq needles-per-cluster 1736 '((2 . ("Austrian Pine" "Red Pine")) 1737 (3 . ("Pitch Pine")) 1738@end group 1739 (5 . ("White Pine")))) 1740@result{} 1741((2 "Austrian Pine" "Red Pine") 1742 (3 "Pitch Pine") 1743 (5 "White Pine")) 1744 1745(setq copy (copy-alist needles-per-cluster)) 1746@result{} 1747((2 "Austrian Pine" "Red Pine") 1748 (3 "Pitch Pine") 1749 (5 "White Pine")) 1750 1751(eq needles-per-cluster copy) 1752 @result{} nil 1753(equal needles-per-cluster copy) 1754 @result{} t 1755(eq (car needles-per-cluster) (car copy)) 1756 @result{} nil 1757(cdr (car (cdr needles-per-cluster))) 1758 @result{} ("Pitch Pine") 1759@group 1760(eq (cdr (car (cdr needles-per-cluster))) 1761 (cdr (car (cdr copy)))) 1762 @result{} t 1763@end group 1764@end smallexample 1765 1766 This example shows how @code{copy-alist} makes it possible to change 1767the associations of one copy without affecting the other: 1768 1769@smallexample 1770@group 1771(setcdr (assq 3 copy) '("Martian Vacuum Pine")) 1772(cdr (assq 3 needles-per-cluster)) 1773 @result{} ("Pitch Pine") 1774@end group 1775@end smallexample 1776@end defun 1777 1778@defun assq-delete-all key alist 1779This function deletes from @var{alist} all the elements whose @sc{car} 1780is @code{eq} to @var{key}, much as if you used @code{delq} to delete 1781each such element one by one. It returns the shortened alist, and 1782often modifies the original list structure of @var{alist}. For 1783correct results, use the return value of @code{assq-delete-all} rather 1784than looking at the saved value of @var{alist}. 1785 1786@example 1787(setq alist (list '(foo 1) '(bar 2) '(foo 3) '(lose 4))) 1788 @result{} ((foo 1) (bar 2) (foo 3) (lose 4)) 1789(assq-delete-all 'foo alist) 1790 @result{} ((bar 2) (lose 4)) 1791alist 1792 @result{} ((foo 1) (bar 2) (lose 4)) 1793@end example 1794@end defun 1795 1796@defun assoc-delete-all key alist &optional test 1797This function is like @code{assq-delete-all} except that it accepts 1798an optional argument @var{test}, a predicate function to compare the 1799keys in @var{alist}. If omitted or @code{nil}, @var{test} defaults to 1800@code{equal}. As @code{assq-delete-all}, this function often modifies 1801the original list structure of @var{alist}. 1802@end defun 1803 1804@defun rassq-delete-all value alist 1805This function deletes from @var{alist} all the elements whose @sc{cdr} 1806is @code{eq} to @var{value}. It returns the shortened alist, and 1807often modifies the original list structure of @var{alist}. 1808@code{rassq-delete-all} is like @code{assq-delete-all} except that it 1809compares the @sc{cdr} of each @var{alist} association instead of the 1810@sc{car}. 1811@end defun 1812 1813@defmac let-alist alist body 1814Creates a binding for each symbol used as keys the association list 1815@var{alist}, prefixed with dot. This can be useful when accessing 1816several items in the same association list, and it's best understood 1817through a simple example: 1818 1819@lisp 1820(setq colors '((rose . red) (lily . white) (buttercup . yellow))) 1821(let-alist colors 1822 (if (eq .rose 'red) 1823 .lily)) 1824 @result{} white 1825@end lisp 1826 1827The @var{body} is inspected at compilation time, and only the symbols 1828that appear in @var{body} with a @samp{.} as the first character in 1829the symbol name will be bound. Finding the keys is done with 1830@code{assq}, and the @code{cdr} of the return value of this 1831@code{assq} is assigned as the value for the binding. 1832 1833Nested association lists is supported: 1834 1835@lisp 1836(setq colors '((rose . red) (lily (belladonna . yellow) (brindisi . pink)))) 1837(let-alist colors 1838 (if (eq .rose 'red) 1839 .lily.belladonna)) 1840 @result{} yellow 1841@end lisp 1842 1843Nesting @code{let-alist} inside each other is allowed, but the code in 1844the inner @code{let-alist} can't access the variables bound by the 1845outer @code{let-alist}. 1846@end defmac 1847 1848@node Property Lists 1849@section Property Lists 1850@cindex property list 1851@cindex plist 1852 1853 A @dfn{property list} (@dfn{plist} for short) is a list of paired 1854elements. Each of the pairs associates a property name (usually a 1855symbol) with a property or value. Here is an example of a property 1856list: 1857 1858@example 1859(pine cones numbers (1 2 3) color "blue") 1860@end example 1861 1862@noindent 1863This property list associates @code{pine} with @code{cones}, 1864@code{numbers} with @code{(1 2 3)}, and @code{color} with 1865@code{"blue"}. The property names and values can be any Lisp objects, 1866but the names are usually symbols (as they are in this example). 1867 1868 Property lists are used in several contexts. For instance, the 1869function @code{put-text-property} takes an argument which is a 1870property list, specifying text properties and associated values which 1871are to be applied to text in a string or buffer. @xref{Text 1872Properties}. 1873 1874 Another prominent use of property lists is for storing symbol 1875properties. Every symbol possesses a list of properties, used to 1876record miscellaneous information about the symbol; these properties 1877are stored in the form of a property list. @xref{Symbol Properties}. 1878 1879@menu 1880* Plists and Alists:: Comparison of the advantages of property 1881 lists and association lists. 1882* Plist Access:: Accessing property lists stored elsewhere. 1883@end menu 1884 1885@node Plists and Alists 1886@subsection Property Lists and Association Lists 1887@cindex plist vs. alist 1888@cindex alist vs. plist 1889 1890@cindex property lists vs association lists 1891 Association lists (@pxref{Association Lists}) are very similar to 1892property lists. In contrast to association lists, the order of the 1893pairs in the property list is not significant, since the property 1894names must be distinct. 1895 1896 Property lists are better than association lists for attaching 1897information to various Lisp function names or variables. If your 1898program keeps all such information in one association list, it will 1899typically need to search that entire list each time it checks for an 1900association for a particular Lisp function name or variable, which 1901could be slow. By contrast, if you keep the same information in the 1902property lists of the function names or variables themselves, each 1903search will scan only the length of one property list, which is 1904usually short. This is why the documentation for a variable is 1905recorded in a property named @code{variable-documentation}. The byte 1906compiler likewise uses properties to record those functions needing 1907special treatment. 1908 1909 However, association lists have their own advantages. Depending on 1910your application, it may be faster to add an association to the front of 1911an association list than to update a property. All properties for a 1912symbol are stored in the same property list, so there is a possibility 1913of a conflict between different uses of a property name. (For this 1914reason, it is a good idea to choose property names that are probably 1915unique, such as by beginning the property name with the program's usual 1916name-prefix for variables and functions.) An association list may be 1917used like a stack where associations are pushed on the front of the list 1918and later discarded; this is not possible with a property list. 1919 1920@node Plist Access 1921@subsection Property Lists Outside Symbols 1922@cindex plist access 1923@cindex accessing plist properties 1924 1925 The following functions can be used to manipulate property lists. 1926They all compare property names using @code{eq}. 1927 1928@defun plist-get plist property 1929This returns the value of the @var{property} property stored in the 1930property list @var{plist}. It accepts a malformed @var{plist} 1931argument. If @var{property} is not found in the @var{plist}, it 1932returns @code{nil}. For example, 1933 1934@example 1935(plist-get '(foo 4) 'foo) 1936 @result{} 4 1937(plist-get '(foo 4 bad) 'foo) 1938 @result{} 4 1939(plist-get '(foo 4 bad) 'bad) 1940 @result{} nil 1941(plist-get '(foo 4 bad) 'bar) 1942 @result{} nil 1943@end example 1944@end defun 1945 1946@defun plist-put plist property value 1947This stores @var{value} as the value of the @var{property} property in 1948the property list @var{plist}. It may modify @var{plist} destructively, 1949or it may construct a new list structure without altering the old. The 1950function returns the modified property list, so you can store that back 1951in the place where you got @var{plist}. For example, 1952 1953@example 1954(setq my-plist (list 'bar t 'foo 4)) 1955 @result{} (bar t foo 4) 1956(setq my-plist (plist-put my-plist 'foo 69)) 1957 @result{} (bar t foo 69) 1958(setq my-plist (plist-put my-plist 'quux '(a))) 1959 @result{} (bar t foo 69 quux (a)) 1960@end example 1961@end defun 1962 1963@defun lax-plist-get plist property 1964Like @code{plist-get} except that it compares properties 1965using @code{equal} instead of @code{eq}. 1966@end defun 1967 1968@defun lax-plist-put plist property value 1969Like @code{plist-put} except that it compares properties 1970using @code{equal} instead of @code{eq}. 1971@end defun 1972 1973@defun plist-member plist property 1974This returns non-@code{nil} if @var{plist} contains the given 1975@var{property}. Unlike @code{plist-get}, this allows you to distinguish 1976between a missing property and a property with the value @code{nil}. 1977The value is actually the tail of @var{plist} whose @code{car} is 1978@var{property}. 1979@end defun 1980