Ordered sets are lists with unique elements sorted to the standard
order of terms (see sort/2).
Exploiting ordering, many of the set operations can be expressed in
order N rather than N^
2 when dealing with unordered sets
that may contain duplicates. The library(ordsets) is available in a
number of Prolog implementations. Our predicates are designed to be
compatible with common practice in the Prolog community. The
implementation is incomplete and relies partly on library(oset), an
older ordered set library distributed with SWI-Prolog. New applications
are advised to use library(ordsets).
Some of these predicates match directly to corresponding list operations. It is advised to use the versions from this library to make clear you are operating on ordered sets. An exception is member/2. See ord_memberchk/2.
The ordsets library is based on the standard order of terms. This implies it can handle all Prolog terms, including variables. Note however, that the ordering is not stable if a term inside the set is further instantiated. Also note that variable ordering changes if variables in the set are unified with each other or a variable in the set is unified with a variable that is `older' than the newest variable in the set. In practice, this implies that it is allowed to use member(X, OrdSet) on an ordered set that holds variables only if X is a fresh variable. In other cases one should cease using it as an ordset because the order it relies on may have been changed.
Some Prolog implementations also provide ord_member/2, with the same semantics as ord_memberchk/2. We believe that having a semidet ord_member/2 is unacceptably inconsistent with the *_chk convention. Portable code should use ord_memberchk/2 or member/2.
ord_union(Set1, Set2, Union), ord_intersection(Set1, Set2, Intersection), ord_subtract(Union, Intersection, Difference).
For example:
?- ord_symdiff([1,2], [2,3], X). X = [1,3].