What is wrong with intersection/3 and friends?
The library(lists) contains a number of old predicates for manipulating
sets represented as unordered lists, notably intersection/3, union/3,
subset/2 and subtract/3. These predicates all use memberchk/2 to find
equivalent elements. As a result these are not logical while
unification can easily lead to dubious results. Operating on unordered
sets these predicates typically have complexity |Set1|*|Set2|.
When using these predicates
- Make sure to respect the mode, i.e., make sure the input lists
are proper lists. See is_list/1.
- Make sure elements are sufficiently instantiated such that their
equality can safely be checked using unification. See ?=/2.
- Make sure the inputs are indeed sets, i.e., the lists contain
no duplicates. In this case, a list is considered to have
a duplicate if two members of the list can unify.
Intended behavior
?- intersection([a,b,c], [b,e], X).
X = [b].
?- union([a,b,c], [b,e], X).
X = [a, c, b, e].
?- subset([a,b,c], [b,e]).
false.
?- subset([b], [b,e]).
true.
?- subtract([a,b,c], [b,e], X).
X = [a, c].
Dubious behavior
?- intersection([a,b,c], [b,E], X).
E = a,
X = [a, b].
?- subtract([a,b,c], [b,E], X).
E = a,
X = [c].
Insufficient instantiation also leads to problems
?- subtract([a,b,c], X, [c]).
false.
Note that duplicates in the input may result in duplicates in the output
(example by Boris).
?- intersection([a,b,a], [b,a,b], I).
I = [a, b, a].
- deprecated
- - New code should use library(ordsets) instead.