Lists as Ordered Sets -- library(ordsets)

In this group of predicates, sets are represented by 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, and is the ordering used by the built-in predicates sort/2 and setof/3. Note that sort/2 and setof/3 produce ordered sets as their results. See ref-all for more information.

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.

A number of predicates described elsewhere can be used on unordered sets. Examples are length/2 (built-in; see ref-lte), member/2 (from library(basics); see lib-lis-basics-member), subseq1/2 (from library(lists); see lib-lis-lists), select/3 (from library(sets); see lib-lis-set-sets), and sublist/3 (from library(maplist); see lib-abs).

is_ordset(+List)

is true when List is a proper list of terms [T1,T2, ...,Tn] and the terms are strictly increasing: T1 @< T2 @< ... @< Tn. The output of sort/2 and setof/3 always satisfies this test. Anything that satisfies this test can be given to the predicates in library(ordsets), regardless of how it was generated.

list_to_ord_set(+List, ?Set)

is true when Set is the ordered representation of the set designated by the unordered representation List. (This is in fact no more than an alias for sort/2.)

ord_add_element(+Set1, +Element, ?Set2)

calculates Set2 = Set1 U {Element}. It only works this way around. ord_add_element/3 is the ordered equivalent of add_element/3 (lib-lis-set-sets).

ord_del_element(+Set1, +Element, ?Set2)

calculates Set2 = Set1 \ {Element}. It only works this way around. ord_del_element/3 is the ordered equivalent of del_element/3 (lib-lis-set-sets).

ord_disjoint(+Set1, +Set2)

is true when Set1 and Set2 have no element in common. It is not defined for unsorted lists.

ord_intersect(+Set1, +Set2)

is true when Set1 and Set2 have at least one element in common. Note that the test is == rather than = .

ord_intersect(+Set1, +Set2, ?Intersection)

is an obsolete synonym for ord_intersection/3. It should not be used in new programs.

ord_intersection(+Set1, +Set2, ?Intersection)

is true when Intersection is the ordered representation of the intersection of Set1 and Set2, provided that Set1 and Set2 are ordered sets.

ord_intersection(+Sets, ?Intersection)

is true when Intersection is the ordered representation of the intersection of all the sets in Sets (which must be a non-empty proper list of ordered sets).

ord_seteq(+Set1, +Set2)

is true when Set1 and Set2 represent the same set. Since they are assumed to be ordered representations, Set1 and Set2 must be identical.

ord_setproduct(+Set1, +Set2, ?Product)

is true when Product is a sorted list of Elt1-Elt2 pairs, with a pair for each element Elt1 of Set1 and each element Elt2 of Set2. Set1 and Set2 are assumed to be ordered; if they are not, the result may not be.

          | ?- list_to_ord_set([t,o,y], Set1),
          |    list_to_ord_set([d,o,g], Set2),
          |    ord_setproduct(Set1, Set2, Product).
          
          Set1 = [o,t,y],
          Set2 = [d,g,o],
          Product = [o-d,o-g,o-o,t-d,t-g,t-o,y-d,y-g,y-o]
          
          | ?- % but with unordered arguments:
          |    ord_setproduct([t,o,y], [d,o,g], Product).
          
          Product = [t-d,t-o,t-g,o-d,o-o,o-g,y-d,y-o,y-g]
          

ord_subset(+Set1, +Set2)

is true when every element of the ordered set Set1 appears in the ordered set Set2. To generate subsets, use a member of the subseq0/2 family from library(lists) (lib-lis-lists).

ord_subtract(+Set1, +Set2, ?Difference)

is true when Difference contains all and only the elements of Set1 that are not also in Set2.

ord_symdiff(+Set1, +Set2, ?Difference)

is true when Difference is the symmetric difference of Set1 and Set2.

ord_union(+Set1, +Set2, ?Union)

is true when Union is the union of Set1 and Set2. Note that when an element occurs in both Set1 and Set2, only one copy is retained.

ord_union(+Sets, ?Union)

is true when Union is the ordered representation of the union of all the sets in Sets (which must be a proper list of ordered sets). This is quite efficient. In fact ord_union/2 can be seen as a generalization of sort/2.

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).

If operations on ordered sets or ordered lists are useful to you, you may also find library(ordered) (lib-abs) or library(ordprefix) (lib-abs) of interest.