Module "ordsets"

This module provides ordered sets. The ordered sets are represented by lists [x1, .., xn]. The lists must be ordered and duplicate free. If this precondition is violated the behaviour of the predicates is undefined.

Examples:
?- ord_union([2,3,4],[1,2,4,5],X).
X = [1,2,3,4,5]
?- ord_union([1,2,4,5],[2,3,4],X).
X = [1,2,3,4,5]

The realization uses a membership check based on (==)/2 and lexical ordering based on (@<)/2. As a result the predicates are safe to be used with non-ground terms. On the other hand, since this comparison is not arithmetical, 1 and 1.0 are for example considered different.

An unordered set can be converted into an ordered set by using the ISO predicate sort/2. Also there is no need for predicate permutation/2 here, since equality of ordered sets can be tested via the ISO predicate ==/2, provided the elements are sufficiently normalized.

The following ordered sets predicates are provided:

ord_contains(O, E):
The predicate succeeds when the set O contains the element E.
ord_delete(O, E, P):
The predicate succeeds when P unifies with the subtract of O by [E].
ord_add(O, E, P):
The predicate succeeds when P unifies with the union of [E] and O.
ord_subtract(O, P, Q):
The predicate succeeds when Q unifies with the subtract of O by P.
ord_intersection(O, P, Q):
The predicate succeeds when Q unifies with the intersection of O and P.
ord_union(O, P, Q):
The predicate succeeds when Q unifies with the union of O and P.
ord_symdiff(O, P, Q):
The predicate succeeds when R unifies with the symmetric subtract of S and T.
ord_subset(O, P):
The predicate succeeds when O is a subset of P.
ord_disjoint(O, P):
The predicate succeeds when O is disjoint to P.

Comments