Set Processing -- library(sets)

The library(sets) package represents sets as lists with no repeated elements. Some of the predicates provided by this package may return sensible answers if given arguments that contain repeated elements, but that is a lucky accident. When in doubt, use list_to_set/2 to convert from a list (with possibly repeated elements) to a set. For a list of predicates related to set manipulation that are not in the library(sets) package, see lib-lis-set-pre. For some applications, ordered sets are more appropriate; see lib-lis-ordsets for more information.

The predicates defined in library(sets) are described below:

add_element(+Elem, +Set1, -Set2)

is true when Set1 and Set2 are sets represented as unordered lists, and Set2 = Set1 U {Elem}. add_element/3 may only be used to calculate Set2 given Elem and Set1. However, it is permissible for Set1 to be a list with a variable at the end; in this case, add_element/3 will add new elements to the end of Set2.

del_element(+Elem, +Set1, -Set2)

is true when Set1 and Set2 are sets represented as unordered lists, and Set2 = Set1 \ {Elem}. del_element/3 may only be used to calculate Set2 given Elem and Set1. If Set1 does not contain Elem, Set1 and Set2 will be equal. If Set1 contains more than one copy of Elem (in which case Set1 is not really a set representation), only the first copy of Elem will be removed. See delete/3 in library(lists) (lib-lis-lists) for a predicate that removes all copies of a given element. When Set1 and Set2 are identical, there are infinitely many Elems that would make this predicate true, so we could not solve for Elem. Therefore, we do not attempt to solve for Elem in any case, which is why it is a + argument.

is_set(+Set)

is true when Set is a proper list that contains no repeated elements (that is, a proper set). is_set/1 does not check for any particular order. If Set is not a proper list, is_set/1 fails.

disjoint(+Set1, +Set2)

is true when Set1 and Set2 have no elements in common. disjoint/2 is the opposite of intersect/2 (below).

select(?Element, ?Set, ?Residue)

is true when Set is a list, Element occurs in Set, and Residue is everything in Set except Element (the order of elements is preserved). To ensure termination, either Set or Residue should be proper. select/3 works on lists as well as on sets.

select/3 is closely related to the predicate select/4 in library(lists) (lib-lis-lists). Although select/3 is normally used to solve for Element and Residue, you can read select(X, S, Y, R) as dq"replace X by Y in S giving R", and select(X, S, R) can be read as "replace X by nothing in S giving R".

          | ?- select(a, [a,r,a], R).
          
          R = [r,a] ;
          
          R = [a,r] ;
          
          no
          
          | ?- select(a, [a,r,a], e, R).
          
          R = [e,r,a] ;
          
          R = [a,r,e] ;
          
          no
          

selectchk(+Element, +Set, ?Residue)

is to select/3 what memberchk/2 is to member/2 in library(basics). That is, it locates the first occurrence of Element in Set and deletes it, returning the resulting list in Residue. It is steadfast in Residue.

pairfrom(?Set, ?Element1, ?Element2, ?Residue)

is true when Set is a set, Element1 occurs in Set, Element2 occurs in Set after Element1, and Residue is everything in Set except Element1 and Element2. The point of pairfrom/4 is to select pairs of elements from a set without selecting the same pair twice in different orders. To ensure termination, either Set or Residue should be proper. pairfrom/4 works on lists as well as on sets.

intersect(+Set1, +Set2)

is true when Set1 and Set2 have a member in common. It assumes that both sets are known, and that you do not need to know which element it is that they share.

intersect/3

is an obsolete predicate and should not be used in new programs.

subset(+SubSet, +Set)

is true when each member of SubSet occurs in Set. subset/2 can only be used to test two given sets; it cannot be used to generate subsets.

To generate subsets, use subseq0/[2,3] or subseq1/[2,3] from library(lists) (lib-lis-lists); they will generate each subset (or each proper subset) (and, for the three-argument versions, its complement) precisely once, but cannot be used for testing whether a given set is a subset of another. Note that they generate sub-sequences; to really generate sub-sets they would have to enumerate all the permutations of each subsequence, which would be quite costly.

seteq(+Set1, +Set2)

is true when Set1 is a subset of Set2, and vice-versa. Since set representations should not contain duplicates, we could check whether one is a permutation of the other. The method used by seteq/2 works even if Set1 and Set2 do contain duplicates.

list_to_set(+List, ?Set)

is true when List and Set are lists, and Set contains the same elements as List in the same order, except that Set contains no duplicates. List and Set are thus equal when considered as sets. list_to_ord_set/2 is faster at converting a list to a set, but the method used by list_to_set/2 preserves as much of the original ordering as possible.

intersection(+Set1, +Set2, ?Intersection)

is true when Intersection is the intersection of Set1 and Set2, taken in a particular order. In fact it is precisely the elements of Set1 taken in their original order, with elements not in Set2 deleted. If Set1 contains duplicates, so may Intersection.

intersection(+Sets, ?Intersection)

is true when Sets is a proper list of sets, and Intersection is the intersection of all the sets in Sets. In fact, Intersection is precisely the elements of the head of Sets, with elements that do not occur in all of the other sets dropped. Sets must not be empty.

subtract(+Set1, +Set2, ?Difference)

is like intersection/3, but here it is the elements of Set1 that are in Set2 that are deleted.

symdiff(+Set1, +Set2, ?Diff)

is true when Diff is the symmetric difference of Set1 and Set2; that is, if each element of Diff occurs in one of Set1 and Set2, but not both. The construction method is such that the answer will contain no duplicates even if Set1 and Set2 do.

setproduct(+Set1, +Set2, ?CartesianProduct)

is true when Set1 is a set (list) and Set2 is a set (list) and CartesianProduct is a set of Elt1-Elt2 pairs, with a pair for each element Elt1 of Set1 and Elt2 of Set2. For example,

          | ?- setproduct([b,a], [1,2], Product).
          
          Product = [[b-1],[b-2],[a-1],[a-2]]
          

union(+Set1, +Set2, ?Union)

is true when Union is the elements of Set1 that do not occur in Set2, followed by all the elements of Set2, that is, when the following are true:

          subtract(Set1, Set2, Diff)
          append(Diff, Set2, Union.
          

union(+Sets, ?Union)

is true when Sets is a list of sets and Union is the union of all the sets in Sets. Sets must be a proper list, but it may be empty.

union(+Set1, +Set2, ?Union, ?Difference)

added to keep sets.pl and ordsets.pl parallel. This predicate is true when the following are true:

          union(Set1, Set2, Union),
          subtract(Set1, Set2, Difference).
          

power_set(?Set, ?PowerSet)

is true when Set is a list and PowerSet is a list of all the subsets of Set. The elements of PowerSet are ordered so that if A and B are subsets of Set and B is a subset of A (for example, Set=[1,2,3], A=[1,3], B=[3]) then A will appear before B in PowerSet. Note that length(PowerSet) = 2^length(Set), so this is only useful for a small Set.

          | ?- power_set([a,b], X).
          X = [[a,b],[a],[b],[]]