5.3 Functions for Manipulating Lists
The following functions are meant for the special pairs which are lists, as described in Section
5.1. An argument which is not a list could give unexpected results. For example, length is used
to determine the number of top level elements in a list.
1 lisp> (length '(a b c))
3
2 lisp> (length '(a b . c))
2
Selecting List Elements
(first L:pair): any macro
A synonym for car.
(second L:pair): any macro
A synonym for cadr.
(third L:pair): any macro
A synonym for caddr.
(fourth L:pair): any macro
A synonym for cadddr.
(rest L:pair): any macro
A synonym for cdr.
(lastpair L:pair): any expr
Returns the last pair of a L. It is often useful to think of this as a pointer to
the last element for use with destructive functions such as rplaca. If L is not
a pair then a type mismatch error occurs.
(de lastpair (l)
(if (or (atom l) (atom (cdr l)))
l
(lastpair (cdr l))))
(lastcar L:pair): any expr
Returns the last element of the pair L. A type mismatch error results if L is
not a pair.
(de lastcar (l)
(if (atom l) l (car (lastpair l))))
(nth L:pair N:integer): any expr
Returns the Nth element of the list L. If L is atomic or contains fewer than
N elements, an out of range error occurs.
(de nth (l n)
(cond ((null l) (range-error))
((onep n) (first l))
(t (nth (rest l) (sub1 n)))))
Note that this definition is not compatible with Common LISP. The Common LISP definition
reverses the arguments and defines the car of a list to be the ”zeroth” element.
(pnth L:list N:integer): any expr
Returns a list starting with the nth element of the list L. Note that the result
is a pointer to the nth element of L, a destructive function like rplaca can be
used to modify the structure of L. If L is atomic or contains fewer than N
elements, an out of range error occurs.
(de pnth (l n)
(cond ((onep n) l)
((not (pairp l)) (range-error))
(t (pnth (rest l) (sub1 n)))))
5.3.1 Membership and Length of Lists
(member A:any L:list): extra-boolean expr
Returns nil if A is not equal to some top level element of the list L;
otherwise it returns the remainder of L whose first element is equal to A.
(de member (a l)
(cond ((not (pairp l)) nil)
((equal a (car l)) l)
(t (member a (cdr l)))))
(memq A:any B:list): extra-boolean expr
The same as member except that eq is used for comparison instead of equal.
Note that the value returned by either member or memq is eq to the portion
of the list which begins with A. Thus a function like rplaca may be used to
alter A.
1 lisp> (setq sequence '(1 3 3))
(1 3 3)
2 lisp> (rplaca (memq 3 sequence) 2)
(2 3)
3 lisp> sequence
(1 2 3)
(length X:any): integer expr
The top level length of the list X is returned.
(de length (l)
(if (atom l) 0 (add1 (length (cdr l)))))
Constructing, Appending, and Concatenating Lists
(list [U:any]): list fexpr
Construct a list of the arguments.
1 lisp> (list (car '(left . right)) (list 'next))
(LEFT (NEXT))
(append U:list V:list): list expr
Returns a constructed list in which the last element of U is followed by the
first element of V. The list U is copied, but V is not.
(de append (u v)
(cond ((not (pairp u)) v)
(t (cons (first u) (append (rest u) v)))))
(nconc U:list V:list): list expr
Destructive version of append, the cdr of the last pair of U is modified
to reference V. While append creates a copy of U, nconc uses U itself in
constructing the result.
(de nconc (u v)
(if (not (pairp u))
v
(rplacd (lastpair u) v)))
1 lisp> (setq a '(swan))
(SWAN)
3 lisp> (nconc a '(giles))
(SWAN GILES)
4 lisp> a
(SWAN GILES)
(aconc U:list V:any): list expr
Destructively adds element V to the tail of list U.
1 lisp> (setq a '(phillips))
(PHILLIPS)
2 lisp> (progn (aconc a 'posner) a)
(PHILLIPS POSNER)
(lconc PTR:list LST:list): list expr
Effectively nconc, but avoids scanning from the front to the end of the first
list by maintaining a pointer. PTR is a pair whose car is a list L and whose
cdr is a reference to the last pair of L. The value returned is the updated pair
PTR.
(progn (rplacd (cdr ptr) lst)
(rplacd ptr (lastpair lst)))
This function is useful for building lists from left to right, PTR should be initialized to (nil . nil)
before the first call on lconc.
(tconc PTR:list ELM:any): list expr
Effectively aconc, but avoids scanning from the front to the end of the first
list by maintaining a pointer. PTR is a pair whose car is a list L and whose
cdr is a reference to the last pair of L. The value returned is the updated pair
PTR.
(progn (setq elm (ncons elm))
(rplacd (cdr ptr) elm)
(rplacd ptr elm))
This function is useful for building lists from left to right. PTR should be initialized to (nil . nil)
before the first call on tconc.
Lists as Sets
A set is a list in which each element occurs only once. Since the order of elements in a set does
not matter, these functions may not preserve order.
(adjoin ELEMENT:any SET:list): list expr
Add Element to SET if it is not already a member.
(de adjoin (elm set)
(if (member elm set) set (cons elm set)))
Recall that member uses equal to test for equality.
(adjoinq ELEMENT:any SET:list): list expr
Similar to adjoin except that eq is used to test for set membership.
(union X:list Y:list): list expr
Returns the union of sets X and Y.
(de union (x y)
(if (not (pairp x))
y
(union (rest x)
(if (member (first x) y)
y
(cons (first x) y)))))
Notice that the two arguments to union are assumed to be sets, if either contains duplicates then
the result may contain duplicates as well.
1 lisp> (union '(1 2 2) '(3))
(2 1 3)
2 lisp> (union '(3) '(1 2 2))
(3 1 2 2)
(unionq X:list Y:list): list expr
Similar to union except that eq is used to test for set membership.
(intersection U:list V:list): list expr
Returns the intersection of sets U and V.
(de intersection (u v)
(cond ((not (pairp u)) nil)
((member (car u) v)
(cons (car u)
(intersection (cdr u) (delete (car u) v))))
(t (intersection (cdr u) v))))
Notice that the two arguments to intersection are assumed to be sets, if either contains
duplicates then the result may contain duplicates as well.
1 lisp> (intersection '(1 2) '(2))
(2)
2 lisp> (intersection '(2 2) '(1 2 2))
(2 2)
(intersectionq U:list V:list): list expr
Similar to intersection except that eq is used to test for set membership.
(list2set SET:list): list expr
Remove redundant elements from the top level of SET using equal.
(list2setq SET:list): list expr
Remove redundant elements from the top level of SET using eq.
5.3.2 Deleting Elements of Lists
Note that the functions suffixed by IP will destructively modify the list from which elements are
being deleted. If you use such a function do not rely on the result being eq to the
argument. The value returned will have all of the elements removed, but the modifications
which have been made to the argument may not reflect this. In particular, the leading
elements which are equal to the element being deleted will not be spliced out of the
list.
1 lisp> (setq this '(a b c))
(a b c)
2 lisp> (deletip 'a this)
(b c)
3 lisp> this
(a b c)
2 lisp> (reversip this)
(c b a)
3 lisp> this
(a)
(delete U:any V:list): list expr
Returns V with the first top level occurrence of U removed from it. Equal
is used for comparing elements. The result consists of a copy of the portion
of U which comes before the deleted element, and the portion of U which
follows the deleted element.
(de delete (u v)
(cond ((not (pairp v)) v)
((equal (car v) u) (cdr v))
(t (cons (car v) (delete u (cdr v))))))
(del F:function U:any V:list): list expr
Generalized delete function with F as the comparison function.
1 lisp> (del '(lambda (i e) (> i e)) 0 '(-2 3 -1))
(-2 -1)
(deletip U:any V:list): list expr
The destructive version of delete, V may be modified.
(delq U:any V:list): list expr
Returns V with the first top level occurrence of U removed from it. Eq is
used for comparing elements. The result consists of a copy of the portion
of U which comes before the deleted element, and the portion of U which
follows the deleted element.
(delqip U:any V:list): list expr
The destructive version of delq, V may be modified.
(delasc U:any V:a-list): a-list expr
Returns V with the first top level occurrence of (U . ANY) removed from it.
Equal is used for comparisons. The result consists of a copy of the portion
of U which comes before the deleted element, and the portion of U which
follows the deleted element.
(delascip U:any V:a-list): a-list expr
The destructive version of delasc, V may be modified.
(delatq U:any V:a-list): a-list expr
Returns V with the first top level occurrence of (U . ANY) removed from
it. Eq is used for comparisons. The result consists of a copy of the portion
of U which comes before the deleted element, and the portion of U which
follows the deleted element.
(delatqip U:any V:a-list): a-list expr
The destructive version of delatq, V may be modified.
5.3.3 List Reversal
(reverse U:list): list expr
Returns a copy of the top level of U in reverse order.
(de reverse (l)
(do ((result nil (cons (car pointer) result))
(pointer l (cdr pointer)))
((not (pairp pointer)) result)))
(reversip U:list): list expr
The destructive version of reverse. The argument may be destructively
modified to produce the result. Note also that the result may not be eq to the
argument.
(de reversip (l)
(prog (next result)
(while (pairp l)
(setq next (cdr l))
(setq result (rplacd l result))
(setq l next))
(return result)))
5.3.4 Functions for Sorting
The gsort module provides functions for sorting lists. Some of the functions take a comparison
function as an argument. The comparison function takes two arguments and should return nil if
the second argument should come before the first in the sorted result. A lambda expression is
acceptable as a comparison function. Note that since sorting requires many comparisons, and
thus many calls on the comparison function, the sort will be much faster if the comparison
function is compiled.
(gsort TABLE:list LEQ-FN:id,function): list expr
Returns a sorted list. LEQ-FN is the comparison function used to determine
the sorting order. The original TABLE is unchanged. Gsort uses a stable
sorting algorithm. In other words, if X appears before Y in TABLE then X
will appear before Y in the result unless X and Y are out of order.
(gmergesort TABLE:list LEQ-FN:id,function): list expr
The destructive version of gsort, this function is somewhat faster than gsort.
Note that you should use the value returned by the function, don’t depend
on the modified argument to give the right answer.
(idsort TABLE:list): list expr
Returns a list of the ids in TABLE, sorted into alphabetical order. The
original list is unchanged. Case is not significant in determining the
alphabetical order.
1 lisp> (setq x '(3 8 -7 2 1 5))
(3 8 -7 2 1 5)
2 lisp> % sort from smallest to largest
2 lisp> (gsort x 'leq)
(-7 1 2 3 5 8)
3 lisp> % sort from largest to smallest
3 lisp> (gmergesort x 'geq)
(8 5 3 2 1 -7)
4 lisp> % note that the value of x has been modified
4 lisp> x
(3 2 1 -7)
5 lisp> (idsort '(the quick brown fox jumped over the lazy dog))
(brown dog fox jumped lazy over quick the the)