Function intersection, nintersection

Syntax:

Arguments and Values:

list-1—a proper list.

list-2—a proper list.

15.5.0 15test—a designator for a function of two arguments that returns a generalized boolean.

test-not—a designator for a function of two arguments that returns a generalized boolean.

key—a designator for a function of one argument, or nil.

result-list—a list.

Description:

15.5.0 14intersection and nintersection return a list that contains every element that occurs in both list-1 and list-2.

15.5.0 16nintersection is the destructive version of intersection. It performs the same operation, but may destroy list-1 using its cells to construct the result. This has gone back and forth, but my opinion is that the current state of this is that the second arg is again protected. -kmp 7-Feb-92 This opinion finally validated by clarifying vote in letter ballot (X3J13/93-302). Option REVERT affirms the status quo from both CLtL1 and draft 12.24, overriding the possible effect of REMF-DESTRUCTION-UNSPECIFIED:X3J13-MAR-89. Barmar noted that this next sentence was in conflict with the changes made by REMF-DESTRUCTION-UNSPECIFIED, so I've removed it for now. Mail sent to find out if X3J13 really intended for NINTERSECTION's contract to be changed, or if making this untrue this was a `typo': \param{list-2} is not destroyed. \funref{nintersection} is permitted to modify any part of the \term{list structure} of \param{list-1} or \param{list-2}.list-2 is not destroyed.

The intersection operation is described as follows. For all possible ordered pairs consisting of one element from list-1 and one element from list-2, :test or :test-not are used to determine whether they satisfy the test. The first argument to the :test or :test-not function is an element of list-1; the second argument is an element of list-2. If :test or :test-not is not supplied, eql is used. It is an error if :test and :test-not are supplied in the same function call.

If :key is supplied (and not nil), it is used to extract the part to be tested from the list element. The argument to the :key function is an element of either list-1 or list-2; the :key function typically returns part of the supplied element. If :key is not supplied or nil, the list-1 and list-2 elements are used.

For every pair that satisfies the test, 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 satisfy the test for an element from the other list. If one of the lists contains duplicate elements, there may be duplication in the result.

There is no guarantee that the order of elements in the result will reflect the ordering of the arguments in any particular way. The result list may share cells with, or be eq to, either list-1 or list-2 if appropriate.

Examples:

 (setq list1 (list 1 1 2 3 4 a b c "A" "B" "C" "d")
       list2 (list 1 4 5 b c d "a" "B" "c" "D")) 
  → (1 4 5 B C D "a" "B" "c" "D")
 (intersection list1 list2) → (C B 4 1 1)
 (intersection list1 list2 :test 'equal) → ("B" C B 4 1 1)
 (intersection list1 list2 :test #'equalp) → ("d" "C" "B" "A" C B 4 1 1) 
 (nintersection list1 list2) → (1 1 4 B C)
 list1 → implementation-dependent ;e.g.,  (1 1 4 B C)
 list2 → implementation-dependent ;e.g.,  (1 4 5 B C D "a" "B" "c" "D")
 (setq list1 (copy-list '((1 . 2) (2 . 3) (3 . 4) (4 . 5))))
→ ((1 . 2) (2 . 3) (3 . 4) (4 . 5)) 
 (setq list2 (copy-list '((1 . 3) (2 . 4) (3 . 6) (4 . 8))))
→ ((1 . 3) (2 . 4) (3 . 6) (4 . 8)) 
 (nintersection list1 list2 :key #'cdr) → ((2 . 3) (3 . 4)) 
 list1 → implementation-dependent ;e.g.,  ((1 . 2) (2 . 3) (3 . 4)) 
 list2 → implementation-dependent ;e.g.,  ((1 . 3) (2 . 4) (3 . 6) (4 . 8)) 

Side Effects:

nintersection can modify list-1, or \param{list-2}.but not list-2.

Affected By:

None.

Exceptional Situations:

Should be prepared to signal an error of type type-error if list-1 and list-2 are not proper lists.

See Also:

union, Section 3.2.1 (Compiler Terminology), Section 3.6 (Traversal Rules and Side Effects)

Notes:

The :test-not parameter is deprecated.

Since the nintersection side effect is not required, it should not be used in for-effect-only positions in portable code.