**Common Lisp the Language, 2nd Edition**

Common Lisp includes functions that allow a list of items to be
treated as a *set*.
There are functions to add, remove, and search for items in a list,
based on various criteria.
There are also set union, intersection, and difference functions.

The naming conventions for these functions and for their keyword arguments generally follow the conventions that apply to the generic sequence functions. See chapter 14.

**[Function]**

`member item list &key :test :test-not :key `

The *list* is searched for an element that satisfies the test.
If none is found, `nil` is returned;
otherwise, the tail of *list* beginning
with the first element that satisfied the test is returned.
The *list* is searched on the top level only.
These functions are suitable for use as predicates.

For example:

(member 'snerd '(a b c d)) =>nil(member-if #'numberp '(a #\Space 5/3 foo)) => (5/3 foo) (member 'a '(g (a y) c a d e a f)) => (a d e a f)

Note, in the last example,
that the value returned by `member` is `eq` to the portion of the list
beginning with `a`.
Thus `rplaca` on the result of `member` may be used
to alter the found list element,
if a check is first made that `member` did not return `nil`.

See also `find` and `position`.

X3J13 voted in January 1989
(MAPPING-DESTRUCTIVE-INTERACTION)
to restrict user side effects; see section 7.9.

**[Function]**

`tailp sublist list`

This predicate is true if *sublist* is a sublist of *list* (that is,
one of the conses that makes up *list*); otherwise it is false.
Another way to look at this is that `tailp` is true if
`(nthcdr n list)` is

X3J13 voted in January 1989
(TAILP-NIL)
to strike the parenthetical remark that suggests
that the *sublist* must be a cons, to clarify that `tailp`
is true if and only if there exists an integer *n* such that

(eqlsublist(nthcdrnlist))

and to specify that *list* may be a dotted list (implying that
implementations must use `atom` and not `endp` to check for
the end of the *list*).

**[Function]**

`adjoin item list &key :test :test-not :key`

`adjoin` is used to add an element to a set, provided that
it is not already a member. The equality test defaults to `eql`.

(adjoinitemlist) == (if (memberitemlist)list(consitemlist))

In general, the test may be any predicate; the *item* is added to the
list only if there is no element of the list that ``satisfies the test.''

`adjoin` deviates from the usual rules described in chapter 14
for the treatment of arguments named *item* and `:key`.
If a `:key` function is specified, it is applied to *item*
as well as to each element of the list. The rationale is that
if the *item* is not yet in the list, it soon will be, and so
the test is more properly viewed as being between two elements
rather than between a separate *item* and an element.

(adjoinitemlist:keyfn) == (if (member (funcallfnitem)list

See `pushnew`.

*Notice of correction.*
In the first edition, the form `( fn item)` appeared
in this example without the required

X3J13 voted in January 1989
(MAPPING-DESTRUCTIVE-INTERACTION)
to restrict user side effects; see section 7.9.

**[Function]**

`union list1 list2 &key :test :test-not :key `

`union` takes two lists and returns a new list containing
everything that is an element of either of the *lists*.
If there is a duplication between two lists,
only one of the duplicate instances will be in the result.
If either of the arguments has duplicate entries within it,
the redundant entries
may or may not appear in the result.
For example:

(union '(a b c) '(f a d)) => (a b c f d) or (b c f a d) or (d f a b c) or ... (union '((x 5) (y 6)) '((z 2) (x 4)) :key #'car) => ((x 5) (y 6) (z 2)) or ((x 4) (y 6) (z 2)) or ...

There is no guarantee that the order of elements in the result will
reflect the ordering of the arguments in any particular way.
The implementation is therefore free to use any of a variety of strategies.
The result list may share cells with, or be `eq` to, either of the arguments
if appropriate.

In general, the test may be any predicate, and the union operation may be
described as follows. For all possible ordered pairs consisting of one
element from *list1* and one element from *list2*, the test is used
to determine whether they ``match.'' For every matching pair, at least
one of the two elements of the pair will be in the result. Moreover, any
element from either list that matches no element of the other will appear
in the result. All this is very general, but probably not particularly
useful unless the test is an equivalence relation.

The `:test-not` argument can be useful when the test function
is the logical negation of an equivalence test. A good example
of this is the function `mismatch`, which is logically inverted
so that possibly useful information can be returned if the arguments do not
match. This additional ``useful information'' is discarded in the following
example; `mismatch` is used purely as a predicate.

(union '(#(a b) #(5 0 6) #(f 3)) '(#(5 0 6) (a b) #(g h)) :test-not #'mismatch) => (#(a b) #(5 0 6) #(f 3) #(g h)) ;One possible result => ((a b) #(f 3) #(5 0 6) #(g h)) ;Another possible result

Using ` :test-not #'mismatch` differs from using

`nunion` is the destructive version of `union`.
It performs the same operation but may destroy the argument lists,
perhaps in order to use their cells to construct the result.

X3J13 voted in January 1989
(MAPPING-DESTRUCTIVE-INTERACTION)
to restrict user side effects; see section 7.9.

X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED)
to clarify the permissible side effects of certain operations;
`nunion` is permitted to perform a `setf` on any part,
*car* or *cdr*, of the top-level list structure of
any of the argument lists.

**[Function]**

`intersection list1 list2 &key :test :test-not :key `

`intersection` takes two lists and returns a new list containing
everything that is an element of both argument lists.
If either list has duplicate entries, the redundant entries
may or may not appear in the result.
For example:

(intersection '(a b c) '(f a d)) => (a)

There is no guarantee that the order of elements in the result will
reflect the ordering of the arguments in any particular way.
The implementation is therefore free to use any of a variety of strategies.
The result list may share cells with, or be `eq` to, either of the arguments
if appropriate.

In general, the test may be any predicate, and the intersection operation
may be described as follows. For all possible ordered pairs consisting of
one element from *list1* and one element from *list2*, the test is
used to determine whether they ``match.'' For every matching pair,
exactly one of the two elements of the pair will be put in the result.
No element from either list appears in the result that does not match
an element from the other list.
All this is very general, but probably
not particularly useful unless the test is an equivalence relation.

`nintersection` is the destructive version of `intersection`.
It performs the same operation, but may destroy *list1*,
perhaps in order to use its cells to construct the result.
(The argument *list2* is *not* destroyed.)

X3J13 voted in January 1989
(MAPPING-DESTRUCTIVE-INTERACTION)
to restrict user side effects; see section 7.9.

X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED)
to clarify the permissible side effects of certain operations;
`nintersection` is permitted to perform a `setf` on any part,
*car* or *cdr*, of the top-level list structure of
any of the argument lists.

**[Function]**

`set-difference list1 list2 &key :test :test-not :key `

`set-difference` returns a list of elements of *list1*
that do not appear in *list2*. This operation is
not destructive.

There is no guarantee that the order of elements in the result will
reflect the ordering of the arguments in any particular way.
The implementation is therefore free to use any of a variety of strategies.
The result list may share cells with, or be `eq` to, either of the arguments
if appropriate.

In general, the test may be any predicate, and the set difference operation
may be described as follows. For all possible ordered pairs consisting of
one element from *list1* and one element from *list2*, the test is
used to determine whether they ``match.'' An element of *list1*
appears in the result if and only if it does not match any element
of *list2*. This is very general and permits interesting applications.
For example, one can remove from a list of strings all those strings
containing one of a given list of characters:

;; Remove all flavor names that contain "c" or "w". (set-difference '("strawberry" "chocolate" "banana" "lemon" "pistachio" "rhubarb") '(#\c #\w) :test #'(lambda (s c) (find c s))) => ("banana" "rhubarb" "lemon") ;One possible ordering

`nset-difference` is the destructive version of `set-difference`.
This operation may destroy *list1*.

X3J13 voted in January 1989
(MAPPING-DESTRUCTIVE-INTERACTION)
to restrict user side effects; see section 7.9.

**[Function]**

set-exclusive-orlist1list2&key :test :test-not :key nset-exclusive-orlist1list2&key :test :test-not :key

`set-exclusive-or` returns a list of elements that appear
in exactly one of *list1* and *list2*.
This operation is not destructive.

`eq` to, either of the arguments
if appropriate.

In general, the test may be any predicate, and the set-exclusive-or operation
may be described as follows. For all possible ordered pairs consisting of
one element from *list1* and one element from *list2*, the test is
used to determine whether they ``match.'' The result contains precisely
those elements of *list1* and *list2* that appear in no matching pair.

`nset-exclusive-or` is the destructive version of `set-exclusive-or`.
Both lists may be destroyed in producing the result.

X3J13 voted in January 1989
(MAPPING-DESTRUCTIVE-INTERACTION)
to restrict user side effects; see section 7.9.

X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED)
to clarify the permissible side effects of certain operations;
`nset-exclusive-or` is permitted to perform a `setf` on any part,
*car* or *cdr*, of the top-level list structure of
any of the argument lists.

**[Function]**

`subsetp list1 list2 &key :test :test-not :key`

`subsetp` is a predicate that is true if every element of *list1*
appears in (``matches'' some element of) *list2*, and false otherwise.

X3J13 voted in January 1989
(MAPPING-DESTRUCTIVE-INTERACTION)
to restrict user side effects; see section 7.9.

AI.Repository@cs.cmu.edu