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]
memberitemlist&key :test :test-not :key
member-ifpredicatelist&key :key
member-if-notpredicatelist&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]
tailpsublistlist

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 (nthcdrnlist) 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]
adjoinitemlist&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 (fnitem) 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]
unionlist1list2&key :test :test-not :key
nunionlist1list2&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]
intersectionlist1list2&key :test :test-not :key
nintersectionlist1list2&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-differencelist1list2&key :test :test-not :key
nset-differencelist1list2&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]
subsetplist1list2&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

AI.Repository@cs.cmu.edu