Go to the previous, next section.

The functions described here operate on lists.

This section describes a number of simple operations on lists, i.e., chains of cons cells.

This function is equivalent to `(car (cdr (cdr `

.
Likewise, this package defines all 28 `x`)))`c`

functions
where `xxx`r`xxx` is up to four ``a'`s and/or ``d'`s.
All of these functions are `setf`

-able, and calls to them
are expanded inline by the byte-compiler for maximum efficiency.

This function is a synonym for `(car `

. Likewise,
the functions `x`)`second`

, `third`

, ..., through
`tenth`

return the given element of the list `x`.

This function is a synonym for `(cdr `

.
`x`)

Common Lisp defines this function to act like `null`

, but
signalling an error if `x`

is neither a `nil`

nor a
cons cell. This package simply defines `endp`

as a synonym
for `null`

.

This function returns the length of list `x`, exactly like
`(length `

, except that if `x`)`x` is a circular
list (where the cdr-chain forms a loop rather than terminating
with `nil`

), this function returns `nil`

. (The regular
`length`

function would get stuck if given a circular list.)

This function returns the last cons, or the `n`th-to-last cons,
of the list `x`. If `n` is omitted it defaults to 1.
The "last cons" means the first cons cell of the list whose
`cdr`

is not another cons cell. (For normal lists, the
`cdr`

of the last cons will be `nil`

.) This function
returns `nil`

if `x` is `nil`

or shorter than
`n`. Note that the last *element* of the list is
`(car (last `

.
`x`))

__Function:__ **butlast** *x &optional n*

This function returns the list `x` with the last element,
or the last `n` elements, removed. If `n` is greater
than zero it makes a copy of the list so as not to damage the
original list. In general, `(append (butlast `

will return a list equal to `x` `n`)
(last `x` `n`))`x`.

__Function:__ **nbutlast** *x &optional n*

This is a version of `butlast`

that works by destructively
modifying the `cdr`

of the appropriate element, rather than
making a copy of the list.

__Function:__ **list*** *arg &rest others*

This function constructs a list of its arguments. The final
argument becomes the `cdr`

of the last cell constructed.
Thus, `(list* `

is equivalent to
`a` `b` `c`)`(cons `

, and
`a` (cons `b` `c`))`(list* `

is equivalent to
`a` `b` nil)`(list `

.
`a` `b`)

(Note that this function really is called `list*`

in Common
Lisp; it is not a name invented for this package like `member*`

or `defun*`

.)

If `sublist` is a sublist of `list`, i.e., is `eq`

to
one of the cons cells of `list`, then this function returns
a copy of the part of `list` up to but not including
`sublist`. For example, `(ldiff x (cddr x))`

returns
the first two elements of the list `x`

. The result is a
copy; the original `list` is not modified. If `sublist`
is not a sublist of `list`, a copy of the entire `list`
is returned.

This function returns a copy of the list `list`. It copies
dotted lists like `(1 2 . 3)`

correctly.

__Function:__ **copy-tree** *x &optional vecp*

This function returns a copy of the tree of cons cells `x`.
Unlike `copy-sequence`

(and its alias `copy-list`

),
which copies only along the `cdr`

direction, this function
copies (recursively) along both the `car`

and the `cdr`

directions. If `x` is not a cons cell, the function simply
returns `x` unchanged. If the optional `vecp` argument
is true, this function copies vectors (recursively) as well as
cons cells.

__Function:__ **tree-equal** *x y &key :test :test-not :key*

This function compares two trees of cons cells. If `x` and
`y` are both cons cells, their `car`

s and `cdr`

s are
compared recursively. If neither `x` nor `y` is a cons
cell, they are compared by `eql`

, or according to the
specified test. The `:key`

function, if specified, is
applied to the elements of both trees. See section Sequences.

@secno=3

These functions substitute elements throughout a tree of cons
cells. (See section Sequence Functions, for the `substitute`

function, which works on just the top-level elements of a list.)

__Function:__ **subst** *new old tree &key :test :test-not :key*

This function substitutes occurrences of `old` with `new`
in `tree`, a tree of cons cells. It returns a substituted
tree, which will be a copy except that it may share storage with
the argument `tree` in parts where no substitutions occurred.
The original `tree` is not modified. This function recurses
on, and compares against `old`, both `car`

s and `cdr`

s
of the component cons cells. If `old` is itself a cons cell,
then matching cells in the tree are substituted as usual without
recursively substituting in that cell. Comparisons with `old`
are done according to the specified test (`eql`

by default).
The `:key`

function is applied to the elements of the tree
but not to `old`.

__Function:__ **nsubst** *new old tree &key :test :test-not :key*

This function is like `subst`

, except that it works by
destructive modification (by `setcar`

or `setcdr`

)
rather than copying.

The `subst-if`

, `subst-if-not`

, `nsubst-if`

, and
`nsubst-if-not`

functions are defined similarly.

__Function:__ **sublis** *alist tree &key :test :test-not :key*

This function is like `subst`

, except that it takes an
association list `alist` of `old`-`new` pairs.
Each element of the tree (after applying the `:key`

function, if any), is compared with the `car`

s of
`alist`; if it matches, it is replaced by the corresponding
`cdr`

.

__Function:__ **nsublis** *alist tree &key :test :test-not :key*

This is a destructive version of `sublis`

.

These functions perform operations on lists which represent sets of elements.

This MacLisp-compatible function searches `list` for an element
which is `equal`

to `item`. The `member`

function is
built-in to Emacs 19; this package defines it equivalently in Emacs 18.
See the following function for a Common-Lisp compatible version.

__Function:__ **member*** *item list &key :test :test-not :key*

This function searches `list` for an element matching `item`.
If a match is found, it returns the cons cell whose `car`

was
the matching element. Otherwise, it returns `nil`

. Elements
are compared by `eql`

by default; you can use the `:test`

,
`:test-not`

, and `:key`

arguments to modify this behavior.
See section Sequences.

Note that this function's name is suffixed by ``*'` to avoid
the incompatible `member`

function defined in Emacs 19.
(That function uses `equal`

for comparisons; it is equivalent
to `(member* `

.)
`item` `list` :test 'equal)

The `member-if`

and `member-if-not`

functions
analogously search for elements which satisfy a given predicate.

This function returns `t`

if `sublist` is a sublist of
`list`, i.e., if `sublist` is `eql`

to `list` or to
any of its `cdr`

s.

__Function:__ **adjoin** *item list &key :test :test-not :key*

This function conses `item` onto the front of `list`,
like `(cons `

, but only if `item` `list`)`item`
is not already present on the list (as determined by `member*`

).
If a `:key`

argument is specified, it is applied to
`item` as well as to the elements of `list` during
the search, on the reasoning that `item` is "about" to
become part of the list.

__Function:__ **union** *list1 list2 &key :test :test-not :key*

This function combines two lists which represent sets of items,
returning a list that represents the union of those two sets.
The result list will contain all items which appear in `list1`
or `list2`, and no others. If an item appears in both
`list1` and `list2` it will be copied only once. If
an item is duplicated in `list1` or `list2`, it is
undefined whether or not that duplication will survive in the
result list. The order of elements in the result list is also
undefined.

__Function:__ **nunion** *list1 list2 &key :test :test-not :key*

This is a destructive version of `union`

; rather than copying,
it tries to reuse the storage of the argument lists if possible.

__Function:__ **intersection** *list1 list2 &key :test :test-not :key*

This function computes the intersection of the sets represented
by `list1` and `list2`. It returns the list of items
which appear in both `list1` and `list2`.

__Function:__ **nintersection** *list1 list2 &key :test :test-not :key*

This is a destructive version of `intersection`

. It
tries to reuse storage of `list1` rather than copying.
It does *not* reuse the storage of `list2`.

__Function:__ **set-difference** *list1 list2 &key :test :test-not :key*

This function computes the "set difference" of `list1`
and `list2`, i.e., the set of elements that appear in
`list1` but *not* in `list2`.

__Function:__ **nset-difference** *list1 list2 &key :test :test-not :key*

This is a destructive `set-difference`

, which will try
to reuse `list1` if possible.

__Function:__ **set-exclusive-or** *list1 list2 &key :test :test-not :key*

This function computes the "set exclusive or" of `list1`
and `list2`, i.e., the set of elements that appear in
exactly one of `list1` and `list2`.

__Function:__ **nset-exclusive-or** *list1 list2 &key :test :test-not :key*

This is a destructive `set-exclusive-or`

, which will try
to reuse `list1` and `list2` if possible.

__Function:__ **subsetp** *list1 list2 &key :test :test-not :key*

This function checks whether `list1` represents a subset
of `list2`, i.e., whether every element of `list1`
also appears in `list2`.

An association list is a list representing a mapping from one set of values to another; any list whose elements are cons cells is an association list.

__Function:__ **assoc*** *item a-list &key :test :test-not :key*

This function searches the association list `a-list` for an
element whose `car`

matches (in the sense of `:test`

,
`:test-not`

, and `:key`

, or by comparison with `eql`

)
a given `item`. It returns the matching element, if any,
otherwise `nil`

. It ignores elements of `a-list` which
are not cons cells. (This corresponds to the behavior of
`assq`

and `assoc`

in Emacs Lisp; Common Lisp's
`assoc`

ignores `nil`

s but considers any other non-cons
elements of `a-list` to be an error.)

__Function:__ **rassoc*** *item a-list &key :test :test-not :key*

This function searches for an element whose `cdr`

matches
`item`. If `a-list` represents a mapping, this applies
the inverse of the mapping to `item`.

This function searches like `rassoc*`

with a `:test`

argument of `equal`

. It is analogous to Emacs Lisp's
standard `assoc`

function, which derives from the MacLisp
rather than the Common Lisp tradition.

The `assoc-if`

, `assoc-if-not`

, `rassoc-if`

,
and `rassoc-if-not`

functions are defined similarly.

Two simple functions for constructing association lists are:

__Function:__ **acons** *key value alist*

This is equivalent to `(cons (cons `

.
`key` `value`) `alist`)

__Function:__ **pairlis** *keys values &optional alist*

This is equivalent to `(nconc (mapcar* 'cons `

.
`keys` `values`)
`alist`)

Go to the previous, next section.