Next: lib-sockets, Previous: lib-samsort, Up: The Prolog Library [Contents][Index]

`library(sets)`

This library module provides operations on sets represented as unordered lists with no repeated elements.

**Please note**: You should probably not use this module.
The ordered representation used in `library(ordsets)`

is **much more
efficient**, but these routines were designed before sort/2
entered the language.
Exported predicates:

`add_element(`

`+Element`,`+Set1`,`-Set2`)-
is true when

`Set1`and`Set2`are sets represented as unordered lists, and`Set2 = Set1 U {Element}`. It may only be used to calculate`Set2`given`Element`and`Set1`. `del_element(`

`+Element`,`+Set1`,`-Set2`)-
is true when

`Set1`and`Set2`are sets represented as unordered lists, and`Set2 = Set1 \ {Element}`. It may only be used to calculate`Set2`given`Element`and`Set1`. If`Set1`does not contain`Element`,`Set2`will be identical to`Set1`(the old version made a new copy of`Set1`). If`Set1`is not an unordered set, but contains more than one copy of`Element`, only the first will be removed. If you want to delete all copies of a given element, use`lists:delete/3`

. For a version which fails if`Element`is not in`Set1`, use`selectchk/3`

. `disjoint(`

`+Set1`,`+Set2`)-
is true when the two given sets have no elements in common. It is the opposite of

`intersect/2`

. If either of the arguments is improper,`disjoint/2`

will fail. `is_set(`

`+List`)-
is true when

`List`is a proper list that contains no repeated elements. `pairfrom(`

`?Set`,`?Element1`,`?Element2`,`?Residue`)-
is true when

`Set`is a list,`Element1`occurs in list,`Element2`occurs in list after`Element1`, and`Residue`is everything in`Set`bar the two`Elements`. The point of this thing is to select pairs of elements from a set without selecting the same pair twice in different orders. `intersect(`

`+Set1`,`+Set2`)-
is true when the two sets have a member in common. It assumes that both sets are known, and that you don’t care which element it is that they share.

`subset(`

`+Set1`,`+Set2`)-
is true when each member of

`Set1`occurs in`Set2`. It can only be used to test two given sets; it cannot be used to generate subsets. There is no predicate for generating subsets as such, but the predicates`subseq/3`

,`subseq0/2`

,`subseq1/2`

in`library(lists)`

may do what you want (they preserve the order of elements within a list). Could be defined as:subset(Set1, Set2) :- ( foreach(X,Set1), param(Set2) do memberchk(X,Set2) ).

`set_order(`

`+Xs`,`+Ys`,`-R`)-
is true when

`R`is`<`

,`=`

, or`>`

according as`Xs`is a subset of`Ys`, equivalent to`Ys`, or a superset of`Ys`. `seteq(`

`+Set1`,`+Set2`)-
is true when each Set is a subset of the other.

`list_to_set(`

`+List`,`-Set`)-
is true when

`List`and`Set`are lists, and`Set`has the same elements as`List`in the same order, except that it contains no duplicates. The two are thus equal considered as sets. `power_set(`

`+Set`,`-PowerSet`)-
is true when

`Set`is a list and`PowerSet`is a list of lists which represents the power set of the set that Set represents. `intersection(`

`+Set1`,`+Set2`,`-Intersection`)-
is true when all three arguments are lists representing sets, and

`Intersection`contains every element of`Set1`which is also an element of`Set2`, the order of elements in`Intersection`being the same as in`Set1`. That is,`Intersection`represents the intersection of the sets represented by`Set1`and`Set2`. Could be defined as:intersection(Set1, Set2, Intersection) :- ( foreach(X,Set1), fromto(Intersection,S0,S,[]), param(Set2) do (member(X, Set2) -> S0 = [X|S] ; S0 = S) ).

`intersection(`

`+ListOfSets`,`-Intersection`)is true when

`Intersection`is the intersection of all the sets in`ListOfSets`. The order of elements in`Intersection`is taken from the first set in`ListOfSets`. This has been turned inside out to minimise the storage turnover. Could be defined as:intersection([Set1|Sets], Intersection) :- ( foreach(X,Set1), fromto(Intersection,S0,S,[]), param(Sets) do ( ( foreach(Set,Sets), param(X) do memberchk(X, Set) ) -> S0 = [X|S] ; S0 = S ) ).

`subtract(`

`+Set1`,`+Set2`,`-Difference`)-
is like

`intersect/3`

, but this time it is the elements of`Set1`which*are*in`Set2`that are deleted. Note that duplicated`Elements`of`Set1`which are not in`Set2`are retained in`Difference`. Could be defined as:subtract(Set1, Set2, Difference) :- ( foreach(X,Set1), fromto(Difference,S0,S,[]), param(Set2) do (member(X, Set2) -> S0 = S ; S0 = [X|S]) ).

`symdiff(+`

`Set1`,`+Set2`,`-Difference`)-
is true when

`Difference`is the symmetric difference of`Set1`and`Set2`, that is, if each element of`Difference`occurs in one of`Set1`and`Set2`but not both. The construction method is such that the answer will have no duplicates even if the`Sets`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 for each element`Elt1`of`Set1`and`Elt2`of`Set2`. Could be defined as: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 ) ).

`disjoint_union(`

`+Set1`,`+Set2`,`-Union`)-
is true when

`disjoint(Set1, Set2)`

and`union(Set1, Set2, Union)`

, that is,`Set1`and`Set2`have no element in command and`Union`is their union. Could be defined as:disjoint_union(Set1, Set2, Union) :- ( foreach(X,Set1), fromto(Union,[X|S],S,Set2), param(Set2) do nonmember(X, Set2) ).

`union(`

`+Set1`,`+Set2`,`-Union`)-
is true when

`subtract(Set1,Set2,Diff)`

and`append(Diff,Set2,Union)`

, that is, when`Union`is the elements of`Set1`that do not occur in`Set2`, followed by all the elements of`Set2`. Could be defined as:union(Set1, Set2, Union) :- ( foreach(X,Set1), fromto(Union,S0,S,Set2), param(Set2) do (member(X, Set2) -> S0 = S ; S0 = [X|S]) ).

`union(`

`+Set1`,`+Set2`,`-Union`,`-Difference`)is true when

`union(Set1, Set2, Union)`

and`subtract(Set1, Set2, Difference)`

. Could be defined as:union(Set1, Set2, Union, Difference) :- ( foreach(X,Set1), fromto(Union,S0,S,Set2), fromto(Difference,T0,T,[]), param(Set2) do ( member(X, Set2) -> S0 = S, T0 = T ; S0 = [X|S], T0 = [X|T] ) ).

`union(`

`+ListOfSets`,`-Union`)is true when

`Union`is the union of all the sets in`ListOfSets`. It has been arranged with storage turnover in mind. Could be defined as:union(Sets, Union) :- ( foreach(Set,Sets), param(Answer) do ( foreach(X,Set), param(Answer) do memberchk(X, Answer) ) ), append(Answer, [], Answer), % cauterise it !, Union = Answer.

Send feedback on this subject.