10.14 Ordered Set Operations—library(ordsets)
This library module provides operations on sets represented as ordered lists with no
duplicates. Thus {c,r,a,f,t}
would be [a,c,f,r,t]
. The ordering
is defined by the @<
family of term comparison predicates, which
is the ordering used by sort/2
and setof/3
.
The benefit of the ordered representation is that the elementary
set operations can be done in time proportional to the sum of the
argument sizes rather than their product. You should use the
operations defined here in preference to those in library(sets)
unless there is a compelling reason why you can't. Some of the
unordered set routines, such as member/2
, length/2
and select/3
can
be used unchanged on ordered sets; feel free so to use them.
There is no ordset_to_list/2
, as an ordered set is a list already.
Exported predicates:
is_ordset(
+List)

is true when List is a list of terms [T1,T2,...,Tn] and the
terms are strictly increasing: T1 @< T2 @< ... @< Tn. The
output of
sort/2
always satisfies this test. Anything which
satisfies this test can be given to the predicates in this
file, regardless of where you got it.
list_to_ord_set(
+List,
Set)

is true when Set is the ordered representation of the set represented
by the unordered representation List. The only reason for giving it
a name at all is that you may not have realised that
sort/2
could be
used this way.
ord_add_element(
+Set1,
+Element,
Set2)

Equivalent to
ord_union(
Set1, [
Element],
Set2)
, but a bit
faster.
ord_del_element(
+Set1,
+Element,
Set2)

Equivalent to
ord_subtract(
Set1, [
Element],
Set2)
, but a bit
faster.
ord_disjoint(
+Set1,
+Set2)

is true when the two ordered sets have no element in common.
ord_intersect(
+Set1,
+Set2)

is true when the two ordered sets have at least one element in common.
ord_intersection(
+Set1,
+Set2,
Intersection)

is true when Intersection is the ordered representation of Set1
and Set2, provided that Set1 and Set2 are ordered sets.
ord_intersection(
+Set1,
+Set2,
?Intersection,
?Difference)
 is true when Intersection is the intersection of Set1 and Set2,
and Difference is Set2 \ Set1 (like in ord_union/4),
provided that Set1 and Set2 are ordered sets.
ord_intersection(
+ListOfSets,
Intersection)
 is true when ListOfSets is a nonempty proper list of ordered sets
and Intersection is their intersection.
ord_member(
+Elt,
+Set)

is true when Elt is a member of Set. Suggested by Mark Johnson.
ord_nonmember(
+Item,
+Set)

is true when the given Item is not an element of the given Set.
ord_seteq(
+Set1,
+Set2)

is true when the two arguments represent the same set. Since they
are assumed to be ordered representations, they must be identical.
ord_setproduct(
+Set1,
+Set2,
Product)

If Set1 and Set2 are ordered sets, Product will be an ordered
set of x1x2 pairs. Note that we cannot solve for Set1 and
Set2, because there are infinitely many solutions when
Product is empty, and may be a large number in other cases.
ord_subset(
+Set1,
+Set2)

is true when every element of the ordered set Set1 appears in the
ordered set Set2.
ord_subtract(
+Set1,
+Set2,
Difference)

is true when Difference contains all and only the elements of Set1
which are not also in Set2.
ord_symdiff(
+Set1,
+Set2,
Difference)

is true when Difference is the symmetric difference of Set1 and Set2.
ord_disjoint_union(
+Set1,
+Set2,
Union)

is true when Set1 and Set2 (given to be ordered sets) have no element
in common, and Union is their union. The meaning is the same as
ord_disjoint(Set1, Set2),
ord_union(Set1, Set2, Union)
but it is more efficient.
ord_union(
+Set1,
+Set2,
Union)

is true when Union is the union of Set1 and Set2. Note that when
something occurs in both sets, we want to retain only one copy.
ord_union(
+OldSet,
+NewSet,
Union,
ReallyNew)
 is true when Union is NewSet U OldSet and ReallyNew is NewSet \ OldSet.
This is useful when you have an iterative problem, and you're adding
some possibly new elements (NewSet) to a set (OldSet), and as well as
getting the updated set (Union) you would like to know which if any of
the "new" elements didn't already occur in the set (ReallyNew).
ord_union(
+ListOfSets,
Union)
 is true when ListOfSets is given as a proper list of ordered sets
and Union is their union. Letting K be the length of ListOfSets,
and N the sum of the sizes of its elements, the cost is
O(N lg K).
ordset_order(
+Xs,
+Ys,
R)

is true when R is
<
, =
, or >
according as Xs is a subset of Ys,
equal to Ys, or a superset of Ys. Xs and Ys are ordered sets.
Send feedback on this subject.