Formally, lists are ordered sequences. They differ with sets in two ways:
A D V E R T I S E M E N T
Sets are unordered, but lists are. (a b c) and (c b a)
are two different lists.
An element either belong to a set or it does not. There is no notion of
multiple occurrences. Yet, a list may contain multiple occurrences of the
same element. (a b b c) and (a b c) are two different
However, one may use lists to approximate sets, although the performance of such
implementation is not the greatest.
We have already seen how we can use the built-in function member to
test set membership. LISP also defines functions like (intersection L1L2), (union L1L2) and (difference
L1L2) for boolean operations on sets. In fact, these
functions are not difficult to implement. Consider the following implementation
of set intersection:
(defun list-intersection (L1 L2)
"Return a list containing elements belonging to both L1 and L2."
((null L1) nil)
((member (first L1) L2)
(cons (first L1) (list-intersection (rest L1) L2)))
(t (list-intersection (rest L1) L2))))
The correctness of the implementation is easy to see. L1 is either an
empty set (nil) or it is not:
Case 1: L1 is an empty set.
Then its interection with L2 is obviously empty.
Case 2: L1 is not empty. L1 has both a first component and a rest
component. There are two cases: either (first L1) is a
member of L2 or it is not.
Case 2.1: (first L1) is a member of
L2. (first L1) belongs to both L1 and L2,
and thus belong to their intersection. Therefore, the intersection of
L1 and L2 is simply (first L1) plus
the intersection of (rest L1) and L2.
Case 2.2: (first L1) is not a member of
Since (first L1) does not belong to L2, it
does not belong to the intersection of L1 and L2. As a
result, the intersection of L1 and L2 is exactly the
intersection of (rest L1) and L2.