Common Lisp the Language, 2nd Edition

Next: Association Lists Up: Lists Previous: Substitution of Expressions

# 15.5. Using Lists as Sets

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
``member-if predicate list &key :key
``member-if-not predicate list &key :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.

Compatibility note: In MacLisp, the `member` function uses an `equal` comparison rather than `eql`, which is the default test for `member` in Common Lisp. Where in MacLisp one would write `(member x y)`, in Common Lisp one must write `(member x y :test #'equal)` to get a completely identical effect. Similarly, one can get the precise effect, and no more, of the MacLisp `(memq x y)` by writing in Common Lisp `(member x y :test #'eq)`.

[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 sublist, for some value of n. See `ldiff`.

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

    (eql sublist (nthcdr n list))

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

    (adjoin item list) == (if (member item list) list (cons item list))

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.

    (adjoin item list :key fn)
      == (if (member (funcall fn item) list

See `pushnew`.

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

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
``nunion 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 ``:test` #'equalp`, for example, because `mismatch` will determine that `#(a b)` and `(a b)` are the same, while `equalp` would regard them as not the same.

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

Compatibility note: An approximately equivalent Interlisp function is `ldifference`.

[Function]

    set-exclusive-or list1 list2 &key :test :test-not :key
    nset-exclusive-or list1 list2 &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.

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

Next: Association Lists Up: Lists Previous: Substitution of Expressions