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