|Did you know ...||Search Documentation:|
|library(ordsets): Ordered set manipulation|
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
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
an older ordered set library distributed with SWI-Prolog. New
applications are advised to use
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.
ord_subtract(Set2, Set1, Difference).
ord_union(Set1, [Element], Set2).
ord_subtract(Set, [Element], NewSet).
select(Item, Set1, Set2)and Set1, Set2 are both sorted lists without duplicates. This implementation is only expected to work for Item ground and either Set1 or Set2 ground. The "chk" suffix is meant to remind you of memberchk/2, which also expects its first argument to be ground.
ord_selectchk(X, S, T)=>
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)and
ord_subtract(Set2, Set1, New).
ord_union(Set1, Set2, Union), ord_intersection(Set1, Set2, Intersection), ord_subtract(Union, Intersection, Difference).
?- ord_symdiff([1,2], [2,3], X). X = [1,3].