10.27 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 x1-x2 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. Could be defined as:

ord_setproduct(Set1, Set2, Product) :-
	(   foreach(H1,Set1),
	    param(Set2),
	    fromto(Product,P1,P3,[])
	do  (   foreach(H2,Set2),
		param(H1),
		fromto(P1,[H1-H2|P2],P2,P3)
	    do  true
	    )
	).

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.