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)
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)
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_set/1
does not check for
any particular order. If Set is not a proper list, is_set/1
fails.
disjoint(
+Set1,
+Set2)
disjoint/2
is the opposite of intersect/2
(below).
select(
?Element,
?Set,
?Residue)
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)
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)
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)
intersect/3
subset(
+SubSet,
+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)
seteq/2
works even if Set1 and Set2 do contain duplicates.
list_to_set(
+List,
?Set)
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)
intersection(
+Sets,
?Intersection)
subtract(
+Set1,
+Set2,
?Difference)
intersection/3
, but
here it is the elements of Set1 that
are in Set2 that are deleted.
symdiff(
+Set1,
+Set2,
?Diff)
setproduct(
+Set1,
+Set2,
?CartesianProduct)
| ?- setproduct([b,a], [1,2], Product). Product = [[b-1],[b-2],[a-1],[a-2]]
union(
+Set1,
+Set2,
?Union)
subtract(Set1, Set2, Diff) append(Diff, Set2, Union.
union(
+Sets,
?Union)
union(
+Set1,
+Set2,
?Union,
?Difference)
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)
length(
PowerSet) = 2^length(
Set)
,
so this is only useful for a small Set.
| ?- power_set([a,b], X). X = [[a,b],[a],[b],[]]