[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

11. Lists

The functions described here operate on lists.

11.1 List Functions  `caddr', `first', `last', `list*', etc.
11.2 Substitution of Expressions  `subst', `sublis', etc.
11.3 Lists as Sets  `member*', `adjoin', `union', etc.
11.4 Association Lists  `assoc*', `rassoc*', `acons', `pairlis'


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

11.1 List Functions

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

Function: caddr x
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 cars and cdrs 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 10. Sequences.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

11.2 Substitution of Expressions

These functions substitute elements throughout a tree of cons cells. (See section 10.3 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 cars and cdrs 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 cars 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.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

11.3 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 10. 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 cdrs.

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.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

11.4 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 nils 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).


[ << ] [ >> ]           [Top] [Contents] [Index] [ ? ]

This document was generated by XEmacs Webmaster on August, 3 2012 using texi2html