|
DataMuseum.dkPresents historical artifacts from the history of: DKUUG/EUUG Conference tapes |
This is an automatic "excavation" of a thematic subset of
See our Wiki for more about DKUUG/EUUG Conference tapes Excavated with: AutoArchaeologist - Free & Open Source Software. |
top - metrics - downloadIndex: T l
Length: 31831 (0x7c57)
Types: TextFile
Names: »lists.texinfo«
└─⟦a05ed705a⟧ Bits:30007078 DKUUG GNU 2/12/89
└─⟦c06c473ab⟧ »./UNRELEASED/lispref.tar.Z«
└─⟦1b57a2ffe⟧
└─⟦this⟧ »lists.texinfo«
@setfilename ../info/lists
@node Lists, Sequences Arrays Vectors, Strings and Characters, Top
@chapter Lists
A @dfn{list} represents a sequence of zero or more elements.
Lists in Lisp are not a primitive data type; they are built up from
@dfn{cons cells}. A cons cell is a data object which represents an ordered
pair. It records two Lisp objects, one labeled as the @sc{car}, and the
other labeled as the @sc{cdr}. (These names are traditional.)
A list is either the distinguished symbol @code{nil} (which
denotes the empty list), or one or more cons cells chained together
through the @sc{cdr}. The @sc{car}s of these cons cells are the
@dfn{elements} of the list.
@menu
* Lists as Boxes::
* List-related Predicates::
* Building Cons Cells and Lists::
* List Elements::
* Modifying Lists::
* Lists as Sets::
* Association Lists::
@end menu
@node Lists as Boxes, List-related Predicates, Lists, Lists
@comment node-name, next, previous, up
@section Lists as Linked Pairs of Boxes
@cindex box representation for lists
@cindex lists represented as boxes
@cindex cons cell as box
A cons cell can be illustrated as a a pair of boxes. The first box
represents the @sc{car} and the second box represents the @sc{cdr}.
Here is an illustration of the two element list, @code{(tulip lilly)}:
@group
@example
--------------- ---------------
|car |cdr | |car |cdr |
| | | | | |
| | o---------->| | |
| tulip | | | lilly | nil |
| | | | | |
--------------- ---------------
@end example
@end group
Each box refers to or `contains' a Lisp object. Each pair of boxes
represents a cons cell. The first box, which is the @sc{car} of the
first cons cell, refers to or contains @samp{tulip}. The arrow from the
@sc{cdr} of the first cons cell to the second cons cell indicates that
the @sc{cdr} of the first cons cell refers to second cons cell.
The exact same list can be illustrated in a different sort of box
notation like this:
@group
@example
___ ___ ___ ___
|___|___|--> |___|___|--> nil
| |
| |
--> tulip --> lilly
@end example
@end group
Here is a more complex illustration, this time of the three element
list, @code{((pine needles) oak maple)}, the first element of which is
a two element list:
@group
@example
___ ___ ___ ___ ___ ___
|___|___|--> |___|___|--> |___|___|--> nil
| | |
| | |
| --> oak --> maple
|
| ___ ___ ___ ___
--> |___|___|--> |___|___|--> nil
| |
| |
--> pine --> needles
@end example
@end group
The exact same list shown above, @code{((pine needles) oak maple)}, is
represented in the second box notation like this:
@group
@example
--------------- --------------- ---------------
|car |cdr | |car |cdr | |car |cdr |
| | | | | | | | |
| o | o---------->| | o---------->| | |
| | | | | oak | | | maple | nil |
| | | | | | | | | |
-- | ---------- --------------- ---------------
|
|
| --------------- -----------------
| |car |cdr | |car |cdr |
| | | | | | |
------>| | o---------->| | |
| pine | | | needles | nil |
| | | | | |
--------------- -----------------
@end example
@end group
@xref{List Type}, for the read and print syntax of lists, and for more
`box and arrow' illustrations of lists.
@node List-related Predicates, Building Cons Cells and Lists, Lists as Boxes, Lists
@section Predicates on Lists
The following predicates test whether a Lisp object is an atom, cons
cell, list, or whether it is the distinguished object @code{nil}. And the
function @code{nlistp} tests whether a function is @emph{not} a list.
@defun consp object
@cindex cons cell
This function returns @code{t} if the object is a cons cell, @code{nil}
otherwise. @code{nil} is not a cons cell, although it @emph{is} a list.
@end defun
@defun atom object
@cindex atoms
This function returns @code{t} if @var{object} is an atom,
@code{nil} otherwise. All objects except cons cells are atoms.
@example
(atom @var{object}) @equiv{} (not (consp @var{object}))
@end example
@end defun
@defun listp object
This function returns @code{t} if @var{object} is a cons cell or
@code{nil}. Otherwise, it returns @code{nil}.
@example
(listp '(1))
@result{} t
(listp '())
@result{} t
@end example
@end defun
@defun nlistp object
This function is the opposite of @code{listp}: it returns @code{t} if
@var{object} is not a list. Otherwise, it returns @code{nil}.
@example
(listp @var{object}) @equiv{} (not (nlistp @var{object}))
@end example
@end defun
@defun null object
This function returns @code{t} if @var{object} is @code{nil}. It
returns @code{nil} otherwise. This function is identical to @code{not},
but by convention, @code{null} is used when @var{object} is considered a
list, and @code{not} is used when it is considered to a truth value (see
@code{not} in @ref{Conditionals}).
@example
(null '(1))
@result{} nil
(null '())
@result{} t
@end example
@end defun
@node Building Cons Cells and Lists, List Elements, List-related Predicates, Lists
@comment node-name, next, previous, up
@section Building Cons Cells and Lists
@cindex cons cells
@cindex building lists
Many functions build lists, as they reside at the very heart of Lisp.
@code{cons} is the fundamental list building function; however, it is
interesting to note that @code{list} is used more times in the source
code for Emacs than @code{cons}.
@defun cons object1 object2
This function is the fundamental function used to build new list
structure. It creates a new cons cell, making @var{object1} the
@code{car}, and @var{object2} the @code{cdr}. It then returns a pointer
to the new cons cell. There is no requirement for @var{object2} to be
of any particular type, although it is normally a list.
@example
(cons 1 '(2))
@result{} (1 2)
(cons 1 '())
@result{} (1)
(cons 1 2)
@result{} (1 . 2)
@end example
@end defun
@defun list &rest objects
This function creates a list with @var{objects} as its elements. The
resulting list is always @code{nil}-terminated. If no @var{objects}
are given, the empty list is returned.
@example
(list 1 2 3 4 5)
@result{} (1 2 3 4 5)
(list)
@result{} nil
@end example
@end defun
@defun make-list length object
This function creates a list of length @var{length}, with each element
being @var{object}.
Compare @code{make-list} to @code{make-string}. (@xref{Creating
Strings}.)
@example
(make-list 3 'pigs)
@result{} (pigs pigs pigs)
(make-list 0 'pigs)
@result{} nil
@end example
@end defun
@defun append &rest sequences
@cindex copying sequences
@cindex copying lists
This function returns a list containing all the elements of
@var{sequences}. The @var{sequences} may be lists, vectors, strings, or
integers. All arguments except the last one are copied, so none of them
are altered.
The final argument to @code{append} may be any object but it is
typically a list. The final argument is not copied or converted.
@group
@example
(setq trees '(pine oak))
@result{} (pine oak)
(setq more-trees (append '(maple birch) trees))
@result{} (maple birch pine oak)
trees
@result{} (pine oak)
more-trees
@result{} (maple birch pine oak)
@end example
@end group
You can see what happens by looking at a box diagram. The variable
@code{trees} is set to the list @code{(pine oak)} and then the variable
@code{more-trees} is set to the list @code{(maple birch pine oak)};
however, the variable @code{trees} continues to refer to the original
list:
@group
@example
more-trees trees
| |
| ___ ___ ___ ___ | ___ ___ ___ ___
--> | | | | | | --> | | | | | |
|___|___|--> |___|___|----> |___|___|--> |___|___|--> nil
| | | |
| | | |
--> maple -->birch --> pine --> oak
@end example
@end group
An empty sequence contributes nothing to the value returned by
@code{append}. As a consequence of this, a final @code{nil} argument
forces a copy of the previous argument.
@group
@example
trees
@result{} (pine oak)
(setq wood (append trees ()))
@result{} (pine oak)
wood
@result{} (pine oak)
(eq wood trees)
@result{} nil
@end example
@end group
@cindex integer to decimal
As a feature, in the special case where one of the @var{sequences} is an
integer (but not a sequence of integers), it is first converted to a string of
digits making up the decimal print representation of the integer.
@group
@example
(setq trees '(pine oak))
@result{} (pine oak)
(char-to-string \054)
@result{} "6"
(setq longer-list (append trees 6 '(spruce)))
@result{} (pine oak 54 spruce)
?x
@result{} 120
(setq x-list (append trees 6 ?x))
@result{} (pine oak 54 . 120)
@end example
@end group
@noindent
Also, somewhat mysteriously, at first:
@group
@example
(append trees 6 ?x nil) @result (pine oak 54 49 50 48)
@r{But note that:}
?x @result 120
(char-to-string \049) @result "1"
(char-to-string \050) @result "2"
(char-to-string \048) @result "0"
@end example
@end group
If no @var{sequences} are given, @code{nil}
is returned.
@group
@example
(append)
@result{} nil
@end example
@end group
See @code{nconc} in @ref{Rearrangement}, for another way to join lists
without copying. See @code{copy-sequence} in @pxref{Sequences Arrays Vectors}, for another way to copy sequences.
@end defun
@defun reverse list
This function creates a new list whose elements are the elements of
@var{list}, but in reverse order. The original @var{list} is
@emph{not} altered.
@example
(setq x '(1 2 3 4))
@result{} (1 2 3 4)
(reverse x)
@result{} (4 3 2 1)
x
@result{} (1 2 3 4)
@end example
@end defun
@node List Elements, Modifying Lists, Building Cons Cells and Lists, Lists
@section Accessing Elements of Lists
@cindex list elements
@defun car cons-cell
This function returns the value pointed to by the first pointer of the
cons cell, @var{cons-cell}. Expressed another way, this function
returns the @sc{car} of @var{cons-cell}. As a special case, if
@var{cons-cell} is @code{nil}, then @code{car} is defined to return
@code{nil}. Therefore, any list is allowed as an argument.
It is an error if the argument is not a cons cell or @code{nil}.
@example
(car '(a b c))
@result{} a
(car '())
@result{} nil
@end example
@end defun
@defun cdr cons-cell
This function returns the value pointed to by the second pointer of
the cons cell, @var{cons-cell}. Expressed another way, this function
returns the @sc{cdr} of @var{cons-cell}. As a special case, if
@var{cons-cell} is @code{nil}, then @code{cdr} is defined to return
@code{nil}. Therefore, any list is allowed as an argument.
It is an error if the argument is not a cons cell or @code{nil}.
@example
(cdr '(a b c))
@result{} (b c)
(cdr '())
@result{} nil
@end example
@end defun
@defun car-safe object
This function lets you take the @sc{car} of a cons cell while avoiding
errors for other data types. It returns the @sc{car} of @var{object} if
@var{object} is a cons cell, @code{nil} otherwise. This is in contrast
to @code{car}, which signals an error if @var{object} is not a list.
@example
(car-safe @var{object})
@equiv{}
(let ((x @var{object}))
(if (consp x)
(car x)
nil))
@end example
@end defun
@defun cdr-safe object
This function lets you take the @sc{car} of a cons cell while
avoiding errors for other data types. It returns the @sc{cdr} of
@var{object} if @var{object} is a cons cell, @code{nil} otherwise.
This is in contrast to @code{cdr}, which signals an error if
@var{object} is not a list.
@example
(cdr-safe @var{object})
@equiv{}
(let ((x @var{object}))
(if (consp x)
(cdr x)
nil))
@end example
@end defun
@defun nth n list
This function returns the @var{n}th element of @var{list}. Elements
are numbered starting with zero, so the @sc{car} of @var{list} is element
number zero. If @var{list} has fewer than @var{n} elements, the value
is @code{nil}.
If @var{n} is less than zero, then the first element is returned.
@example
(nth 2 '(1 2 3 4))
@result{} 3
(nth 10 '(1 2 3 4))
@result{} nil
(nth -3 '(1 2 3 4))
@result{} 1
(nth n x) @equiv{} (car (nthcdr n x))
@end example
@end defun
@defun nthcdr n list
This function returns the @var{n}th cdr of @var{list}. In other
words, it removes the first @var{n} links of @var{list} and returns
what follows.
If @var{n} is less than or equal to zero, then all of @var{list} is
returned. If @var{list} has fewer than @var{n} elements, the value is
@code{nil}.
@example
(nthcdr 1 '(1 2 3 4))
@result{} (2 3 4)
(nthcdr 10 '(1 2 3 4))
@result{} nil
(nthcdr -3 '(1 2 3 4))
@result{} (1 2 3 4)
@end example
@end defun
@node Modifying Lists, Lists as Sets, List Elements, Lists
@section Modifying Existing List Structure
You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the
primitives @code{setcar} and @code{setcdr}.
@quotation
@findex rplaca
@findex rplacd
@b{Common Lisp Note:} Common Lisp uses functions @code{rplaca} and
@code{rplacd} to alter list structure; they change structure the same
way as @code{setcar} and @code{setcdr}, but the Common Lisp functions
return the cons cell while @code{setcar} and @code{setcdr} return the
new @sc{car} or @sc{cdr}.
@end quotation
@menu
* Setcar::
* Setcdr::
* Rearrangement::
@end menu
@node Setcar, Setcdr, Modifying Lists, Modifying Lists
@subsection Altering List Elements with @code{setcar}
Changing the @sc{car} of a cons cell replaces one element of a list
with a different element. This is done with @code{setcar}.
@defun setcar cons object
This function stores @var{object} as the new @sc{car} of @var{cons},
replacing its previous @sc{car}. It returns the value @var{object}.
@example
(setq x '(1 2))
@result{} (1 2)
(setcar x '4)
@result{} 4
x
@result{} (4 2)
@end example
@end defun
When a cons cell is part of the shared structure of several lists,
storing a new @sc{car} into the cons changes one element of each of
these lists. Here is an example:
@example
;; @r{Create two lists that are partly shared.}
(setq x1 '(a b c))
@result{} (a b c)
(setq x2 (cons 'z (cdr x1)))
@result{} (z b c)
;; @r{Replace the @sc{car} of a shared link.}
(setcar (cdr x1) 'foo)
@result{} foo
x1 ; @r{Both lists are changed.}
@result{} (a foo c)
x2
@result{} (z foo c)
;; @r{Replace the @sc{car} of a link that is not shared.}
(setcar x1 'baz)
@result{} baz
x1 ; @r{Only one list is changed.}
@result{} (baz foo c)
x2
@result{} (z foo c)
@end example
Here is a graphical depiction of the shared structure of the two lists
@var{x1} and @var{x2}, showing why replacing @code{b} changes them both:
@group
@example
x1:
--------------- --------------- ---------------
|car |cdr | |car |cdr | |car |cdr |
| a | o---------->| b | o---------->| c | nil |
| | | -->| | | | | |
--------------- | --------------- ---------------
|
x2: |
--------------- |
|car |cdr | |
| z | o-------
| | |
---------------
@end example
@end group
Here is an alternative form of box diagram, showing the same relationship:
@group
@example
___ ___ ___ ___ ___ ___
|___|___|----> |___|___|--> |___|___|--> nil
| --> | |
| | | |
--> a | --> b --> c
|
___ ___ |
|___|___|--
|
|
--> z
@end example
@end group
@node Setcdr, Rearrangement, Setcar, Modifying Lists
@subsection Altering the CDR of a List
The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}:
@defun setcdr cons object
This function stores @var{object} into the cdr of @var{cons}. The
value returned is @var{object}, not @var{cons}.
@example
(setq x '(1 2))
@result{} (1 2)
(setcdr x '(4))
@result{} (4)
x
@result{} (1 4)
@end example
@end defun
You can delete elements from the middle of a list by altering the
@sc{cdr}s of the cons cells in the list. For example, here is the
result of deleting the second element, @code{b}, from the list @code{(a
b c)}, by changing the @sc{cdr} of the first cell:
@example
(setq x1 '(a b c))
@result{} (a b c)
(setcdr x1 '(c))
@result{} (c)
x1
@result{} (a c)
@end example
@group
@example
--------------- ---------------
|car |cdr | |car |cdr |
| a | o---------------------------------->| c | nil |
| | | | | |
--------------- ---------------
@end example
@end group
@noindent
The second cons cell, which previously held the element @code{b}, may
still exist and its @sc{car} may still be @code{b}, but it no longer
forms part of this list.
It is equally easy to insert a new element by changing @sc{cdr}s:
@example
(setq x1 '(a b c))
@result{} (a b c)
(setcdr x1 (cons 'd (cdr x1)))
@result{} (d b c)
x1
@result{} (a d b c)
@end example
@group
@example
--------------- --------------- ---------------
|car |cdr | |car |cdr | |car |cdr |
| a | o | -->| b | o---------->| c | nil |
| | | | | | | | | | |
---------- | -- | --------------- ---------------
| |
------ -------
| |
| --------------- |
| |car |cdr | |
-->| d | o------
| | |
---------------
@end example
@end group
@node Rearrangement, , Setcdr, Modifying Lists
@subsection Functions that Rearrange Lists
Here are some functions that rearrange lists ``destructively'' by
modifying the @sc{cdr}s of their component cons cells. We call these
functions ``destructive'' because the original lists passed as arguments
to them are chewed up to produce a new list that is returned.
@defun nconc &rest lists
@cindex concatenating lists
@cindex joining lists
This function returns a list containing all the elements of
@var{lists}. Unlike @code{append} (@pxref{Building Cons Cells and
Lists}), the @var{lists} are @emph{not} copied; instead, the last
@sc{cdr} of each of the @var{lists} is changed to refer to the
following list. The last of the @var{lists} is not altered.
@example
(setq x '(1 2 3))
@result{} (1 2 3)
(nconc x '(4 5))
@result{} (1 2 3 4 5)
x
@result{} (1 2 3 4 5)
@end example
Since the last argument of @code{nconc} is not itself modified, it is
reasonable to use a constant list, such as @code{`(4 5)}, as is done in
the above example. For the same reason, the last argument need not be a
list:
@example
(setq x '(1 2 3))
@result{} (1 2 3)
(nconc x 'z)
@result{} (1 2 3 . z)
x
@result{} (1 2 3 . z)
@end example
A common pitfall is to use a quoted constant list as a non-last
argument to @code{nconc}. If you do this, your program will change
each time you run it! Here is what happens:
@example
(defun add-foo (x) ; @r{This function should add}
(nconc '(foo) x)) ; @r{@code{foo} to the front of its arg.}
(symbol-function 'add-foo)
@result{} (lambda (x) (nconc (quote (foo)) x))
(setq xx (add-foo '(1 2))) ; @r{It seems to work.}
@result{} (foo 1 2)
(setq xy (add-foo '(3 4))) ; @r{What happened?}
@result{} (foo 1 2 3 4)
(eq xx xy)
@result{} t
(symbol-function 'add-foo)
@result{} (lambda (x) (nconc '(foo 1 2 3 4) x))
@end example
@end defun
@defun nreverse list
This function returns the elements of @var{list} in reverse order.
Unlike @code{reverse}, however, @var{list} is destructively altered by
reversing the @sc{cdr}s in the cons cells forming the list. The last
cons cell of the original list is now the first cell of the list.
@example
(setq x '(1 2 3 4))
@result{} (1 2 3 4)
x
@result{} (1 2 3 4)
(nreverse x)
@result{} (4 3 2 1)
x
@result{} (1)
@end example
Here is the @code{nreverse} of our favorite example, @samp{(a b c)},
presented graphically:
@group
@example
Reversed list:
--------------- --------------- ---------------
|car |cdr | |car |cdr | |car |cdr |
| a | nil |<-- | b | o |<-- | c | o |
| | | | | | | | | | | | |
--------------- | ---------- | -- | ---------- | --
| | | |
--------------- ---------------
@end example
@end group
@end defun
@defun sort list predicate
This function sorts @var{list} stably, though destructively, and
returns the sorted list. It compares elements using @var{predicate}.
A @dfn{stable} sort is one in which elements with equal sort keys
maintain their relative order before and after the sort. Stability is
important when successive sorts are used to order elements according
to different sets of keys.
@var{predicate} must be a function of two arguments. It is called
with two elements of @var{list}. To get an increasing order sort, the
@var{predicate} should return @code{t} if the first element is ``less
than'' the second, or @code{nil} if not.
The destructive aspect of @code{sort} is that it rearranges the cons
cells forming @var{list} by changing @sc{cdr}s. A nondestructive sort
function would create new cons cells to store the elements in their
sorted order.
The @sc{car}s of the cons cells are never changed; the cons cell that
contained the element @code{a} in the original @var{list}, still has
@code{a} in its @sc{car} after sorting, but it now appears in a different
position in the list due to the change of @sc{cdr}s.
@xref{Sorting}, for more functions that perform sorting.
@example
(setq nums '(1 3 2 6 5 4 0))
@result{} (1 3 2 6 5 4 0)
(sort nums '<)
@result{} (0 1 2 3 4 5 6)
nums
@result{} (1 2 3 4 5 6)
@end example
@noindent
Note that @code{nums} no longer contains 0. This shows why you should
save the return-value of sort. Don't assume a variable which held the
argument now holds the entire sorted list!
@end defun
See @code{delq}, in @ref{Lists as Sets}, for another function
that modifies cons cells.
@node Lists as Sets, Association Lists, Modifying Lists, Lists
@section Using Lists as Sets
@cindex lists as sets
@cindex sets
Lists can represent unordered mathematical sets---the elements in the
list are the members of the set. All you have to do is ignore the order.
In these applications, you will probably want to use the functions
@code{memq} and @code{delq}.
@defun memq object list
This function tests to see whether @var{object} is a member of
@var{list}. If it is, @code{memq} returns a list starting with the
first occurrence of @var{object}. Otherwise, it returns @code{nil}.
The letter `q' in @code{memq} says that it uses @code{eq} to compare
@var{objects} against the elements of the list.
@example
(memq 2 '(1 2 3 2 1))
@result{} (2 3 2 1)
(memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
@result{} nil
@end example
@end defun
@defun delq object list
This function removes all elements @code{eq} to @var{object} from
@var{list}.
Elements at the front of the list are removed (when necessary) simply
by advancing down the list and returning a sublist that starts after
those elements:
@example
(delq 'a '(a b c))
@equiv{}
(cdr '(a b c))
@end example
When an element to be deleted appears in the middle of the list,
removing it requires changing the @sc{cdr}s (@pxref{Setcdr}).
@example
(setq sample-list '(1 2 3 (4)))
@result{} (1 2 3 (4))
(delq 1 sample-list)
@result{} (2 3 (4))
sample-list
@result{} (1 2 3 (4))
(delq 2 sample-list)
@result{} (1 3 (4))
sample-list
@result{} (1 3 (4))
(delq '(4) sample-list)
@result{} (1 3 (4))
@end example
Note that @code{(delq 1 sample-list)} does not remove the first element
of @code{sample-list}, but that @code{(delq 2 sample-list)} removes the
second element. Don't assume that a variable which held the argument
now has fewer elements, or, conversely, that it holds the original list!
@end defun
@noindent
(In the final example, the @code{(4)} that @code{delq} attempts to match
and the @code{(4)} in the @code{sample-list} are not @code{eq}.)
@quotation
@b{Common Lisp note:} Common Lisp has functions @code{union} and
@code{intersection} for set operations, but GNU Emacs Lisp does not
have them. You can write them in Lisp if you wish.
@end quotation
@node Association Lists, , Lists as Sets, Lists
@section Association Lists
@cindex alist key
An @dfn{association list}, or @dfn{alist} for short, records a
mapping from keys to values. It is a list of pairs (cons cells): the
@sc{car} of each cell is the key, and the @sc{cdr} is the associated
value. The key can be any Lisp object, and so can the value.
An sample of an alist is shown below; the key, @code{pine}, is
associated with @code{cones}; the key, @code{oak}, is associated with
@code{acorns}; and the key, @code{maple}, is associated with
@code{seeds}.
@example
'((pine . cones)
(oak . acorns)
(maple . seeds))
@end example
The pairs in an alist may be of any kind. For example, in the
following alist, the symbol @code{a} is associated with the number
@code{1}, and the string @code{"b"} is associated with the @emph{list}
@code{(2 3)}.
@example
((a . 1) ("b" 2 3))
@end example
We recommend you use dotted pairs consistently, since they are the simplest
to handle.
Association lists are often used to record information that you might
otherwise keep on a stack since new pairs may be simply added to the front
of the list. When searching an association list for a pair with a given
key, the first pair with that key is returned, even if there are several
such pairs.
It is @emph{not} an error if an element of an association list is not a
cons cell. The alist search functions simply ignore such elements.
Note that property lists are similar to association lists in several
respects. A property list behaves like an association list in which
each key can occur only once. @xref{Property Lists}, for a comparison
of property lists and association lists.
@defun assoc key alist
This function returns the first pair associated with @var{key} in
@var{alist}. It compares @var{key} against the alist elements using
@code{equal}. It returns @code{nil} if no pair in @var{alist} has a
@sc{car} @code{equal} to @var{key}.
@example
(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
@result{} ((pine . cones) (oak . acorns) (maple . seeds))
(assoc 'oak trees)
@result{} (oak . acorns)
(cdr (assoc 'oak trees))
@result{} acorns
(assoc 'birch trees)
@result{} nil
@end example
The elements of an association list need not be dotted pairs:
@example
(setq colors '((rose red) (lilly white) (buttercup yellow)))
@result{} ((rose red) (lilly white) (buttercup yellow))
(assoc 'rose colors)
@result{} (rose red)
(cdr (assoc 'rose colors))
@result{} (red)
@end example
@noindent
In the last example, the @sc{cdr} is the @emph{list} @code{(red)};
contrast this with the example using dotted pairs in which the atom
@code{acorn} is returned.
Also, the key and the associated value can be any kind of Lisp
object, such as numbers, strings, or lists:
@example
(setq needles-per-cluster
'((2 . ("Austrian Pine" "Red Pine"))
(3 . "Pitch Pine")
(5 . "White Pine")))
(cdr (assoc 3 needles-per-cluster))
@result{} "Pitch Pine"
(cdr (assoc 2 needles-per-cluster))
@result{} ("Austrian Pine" "Red Pine")
@end example
@end defun
@defun assq key alist
This function is like @code{assoc} in that it returns the first pair
associated with @var{key} in @var{alist}, but it makes the comparison
using @code{eq} instead of @code{equal}. @code{assq} returns @code{nil}
if no pair in @var{alist} has a @sc{car} @code{eq} to @var{key}. This
function is used more often than @code{assoc}, since @code{eq} is faster
than @code{equal} and most alists use symbols as keys.
@example
(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
(assq 'pine trees)
@result{} (pine . cones)
@end example
On the other hand, @code{assq} returns @code{nil} in the following case:
@example
(setq leaves
'(("simple leaves" . oak)
("compound leaves" . horsechestnut)))
(assq "simple leaves" leaves)
@result{} nil
(assoc "simple leaves" leaves)
@result{} ("simple leaves" . oak)
@end example
@end defun
@defun rassq alist value
@code{rassq} is like @code{assq} except that the @sc{cdr} of the
@var{alist} pairs is tested instead of the @sc{car}. You can think of
this as ``reverse assq'', finding the key for a given value.
This function returns the first pair associated with @var{value} in
@var{alist}. It returns @code{nil} if no pair in @var{alist} has a
@sc{cdr} @code{eq} to @var{value}.
@example
(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
(rassq 'acorns trees)
@result{} (oak . acorns)
@end example
However, @code{rassq} will return @code{nil} if it cannot match
@var{value} with the alist:
@example
(setq colors '((rose red) (lilly white) (buttercup yellow)))
(rassq 'white colors)
@result{} nil
@end example
In this case, the @sc{cdr} of the pair @code{(lilly white)} is not the
symbol, @code{white}, but is the list @code{(white)}. This can be seen
more clearly if the pair is expressed in the equivalent dotted pair notation:
@example
(lilly white) @equiv{} (lilly . (white))
@end example
@end defun
@defun copy-alist alist
@cindex copying lists
This function returns a two-level deep copy of @var{alist}: it creates a
new copy of each pair, so that you can alter the associations of the new
alist without changing the old one.
@example
(setq needles-per-cluster
'((2 . ("Austrian Pine" "Red Pine"))
(3 . "Pitch Pine")
(5 . "White Pine")))
@result{}
((2 "Austrian Pine" "Red Pine")
(3 . "Pitch Pine")
(5 . "White Pine"))
(setq copy (copy-alist needles-per-cluster))
@result{}
((2 "Austrian Pine" "Red Pine")
(3 . "Pitch Pine")
(5 . "White Pine"))
(eq needles-per-cluster copy)
@result{} nil
(equal needles-per-cluster copy)
@result{} t
(eq (car needles-per-cluster) (car copy))
@result{} nil
(cdr (car (cdr needles-per-cluster)))
@result{} "Pitch Pine"
(eq (cdr (car (cdr needles-per-cluster)))
(cdr (car (cdr copy))))
@result{} t
@end example
@end defun