Go to the previous, next section.

# Lists

The functions described here operate on lists.

## List Functions

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

This function is equivalent to `(car (cdr (cdr x)))`. Likewise, this package defines all 28 `cxxxr` functions where 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.

Function: first x

This function is a synonym for `(car x)`. Likewise, the functions `second`, `third`, ..., through `tenth` return the given element of the list x.

Function: rest x

This function is a synonym for `(cdr x)`.

Function: endp 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`.

Function: list-length x

This function returns the length of list x, exactly like `(length x)`, except that if 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.)

Function: last x &optional n

This function returns the last cons, or the nth-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 x n) (last x n))``` will return a list equal to 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* a b c)` is equivalent to `(cons a (cons b c))`, and `(list* a b nil)` is equivalent to `(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*`.)

Function: ldiff list sublist

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.

Function: copy-list list

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

## Substitution of Expressions

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`.

## Lists as Sets

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

Function: member item list

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.

Function: tailp sublist list

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 item list)`, but only if 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.

## Association Lists

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.

Function: rassoc item a-list

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.