```    1%   File   : set_utilities.PL
2%   Author : Lawrence Byrd + R.A.O'Keefe
3%   Updated: 15 November 1983
4%   Purpose: Set manipulation utilities
5
6% Updated by Neil Smith, for compatability with LPA Prolog
7
8%   Sets are represented as lists with no repeated elements.
9%   An ordered representation could be much more efficient, but
10%   these routines were designed before sort/2 entered the language.
11
12:- module(set_utilities,
13      [ add_element/3,		%  Elem x Set -> Set
14	del_element/3,		%  Elem x Set -> Set
15	disjoint/1,		%  List ->
16	disjoint/2,		%  Set x Set ->
17	intersect/2,		%  Set x Set ->
18	intersect/3,		%  Set x Set -> Set
19	listtoset/2,		%  List -> Set
20	% member/2,		%  Elem <- Set
21	memberchk/2,		%  Elem x Set ->
22	pairfrom/4,		%  Set -> Elem x Elem x Set
23	select/3,		%  Elem <- Set -> Set
24	seteq/2,		%  Set x Set ->
25	subset/2,		%  Set x Set ->
26	subtract/3,		%  Set x Set -> Set
27	symdiff/3,		%  Set x Set -> Set
28	union/3 		%  Set x Set -> Set
29      ]).   30
33/**********************
34 *:- mode
35*	memberchk(+, +),
36*	pairfrom(?, ?, ?, ?),
37*	select(?, ?, ?),
39*	del_element(+, +, -),
40*	disjoint(+),
41*	disjoint(+, +),
42*	intersect(+, +),
43*	subset(+, +),
44*	seteq(+, +),
45*	listtoset(+, ?),
46*	intersect(+, +, ?),
47*	subtract(+, +, ?),
48*	symdiff(+, +, ?),
49*	    symdiff(+, +, ?, ?),
50*	union(+, +, ?).
51**************************/
52
53
54%   memberchk(+Element, +Set)
55%   means the same thing as member/2, but may only be used to test
56%   whether a known Element occurs in a known Set.  In return for
57%   this limited use, it is more efficient when it is applicable.
58
59% memberchk(Element, [Element|_]) :- !.
60% memberchk(Element, [_|Rest]) :-
61% 	memberchk(Element, Rest).
62
63memberchk(Element, List) :-
64	one member(Element, List).
65
66
67
69%   is true when Set1 and Set2 are sets represented as unordered lists,
70%   and Set2 = Set1 U {Elem}.  It may only be used to calculate Set2
71%   given Elem and Set1.  However, if Set1 is a list with a variable at
72%   the end, it may still be used, and will add new elements at the end.
73
75	memberchk(Elem, Set),
76	!.
78
79
80%   del_element(Elem, Set1, Set2)
81%   is true when Set1 and Set2 are sets represented as unordered lists,
82%   and Set2 = Set1 \ {Elem}.  It may only be used to calculate Set2
83%   given Elem and Set1.  If Set1 does not contain Elem, Set2 and Set1
84%   will be equal.  I wanted to call this predicate 'delete', but other
85%   Prologs have used that for 'select'.  If Set1 is not an unordered
86%   set, but contains more than one copy of Elem, only the first will
87%   be removed.
88
89del_element(Elem, [Elem|Set2], Set2) :- !.
90del_element(Elem, [X|Set1], [X|Set2]) :- !,
91	del_element(Elem, Set1, Set2).
92del_element(_, [], []).
93
94
95%   disjoint(+Set)
96%   is true when Set is a list that contains no repeated elements.
97%   disjoint/1 and disjoint/2 used to be defined using \+, but for
98%   speed (as the Dec-10 compiler does not understand \+), this is
99%   no longer so.  Sorry 'bout the !,fails, the price of speed.
100
103	!, fail.
104disjoint([_|Tail]) :- !,
105	disjoint(Tail).
106disjoint([]).
107
108
109
110%   disjoint(+Set1, +Set2)
111%   is true when the two given sets have no elements in common.
112%   It is the opposite of intersect/2.
113
114disjoint(Set1, Set2) :-
115	member(Element, Set1),
116	memberchk(Element, Set2),
117	!, fail.
118disjoint(_, _).
119
120
121
122%   select(?Element, ?Set, ?Residue)
123%   is true when Set is a list, Element occurs in Set, and Residue is
124%   everything in Set except Element (things stay in the same order).
125
126select(Element, [Element|Rest], Rest).
128	select(Element, Tail, Rest).
129
130
131
132%   pairfrom(?Set, ?Element1, ?Element2, ?Residue)
133%   is true when Set is a list, Element1 occurs in list, Element2
134%   occurs in list after Element1, and Residue is everything in Set
135%   bar the two Elements.  The point of this thing is to select
136%   pairs of elements from a set without selecting the same pair
137%   twice in different orders.
138
139pairfrom([Element1|Set], Element1, Element2, Residue) :-
140	select(Element2, Set, Residue).
142	pairfrom(Tail, Element1, Element2, Rest).
143
144
145
146%   intersect(Set1, Set2)
147%   is true when the two sets have a member in common.  It assumes
148%   that both sets are known, and that you don't care which element
149%   it is that they share.
150
151intersect(Set1, Set2) :-
152	member(Element, Set1),		%  generates Elements from Set1
153	memberchk(Element, Set2),	%  tests them against Set2
154	!.				%  if it succeeds once, is enough.
155
156
157
158%   subset(+Set1, +Set2)
159%   is true when each member of Set1 occurs in Set2.
160%   It can only be used to test two given sets; it cannot be used
161%   to generate subsets.  At the moment there is NO predicate for
162%   generating subsets, but select/3 takes you part-way.
163
164subset([], _).
165subset([Element|Residue], Set) :-
166	memberchk(Element, Set), !,
167	subset(Residue, Set).
168
169
170
171%   seteq(+Set1, +Set2)
172%   is true when each Set is a subset of the other.  There are two
173%   ways of doing this.  One is commented out.
174
175seteq(Set1, Set2) :-
176	subset(Set1, Set2),
177	subset(Set2, Set1).
178%	sort(Set1, Ord1),
179%	sort(Set2, Ord2),
180%	Ord1 == Ord2.
181
182
183
184%   listtoset(+List, ?Set)
185%   is true when List and Set are lists, and Set has the same elements
186%   as List in the same order, except that it contains no duplicates.
187%   The two are thus equal considered as sets.  If you really want to
188%   convert a list to a set, list_to_ord_set is faster, but this way
189%   preserves as much of the original ordering as possible.
190
191listtoset([], []).
194	listtoset(Tail, Set).
196	listtoset(Tail, Set).
197
198
199
200%   intersect(+Set1, +Set2, ?Intersection)
201%   is true when Intersection is the intersection of Set1 and Set2,
202%   *taken in a particular order*.  In fact it is precisely the
203%   elements of Set1 taken in that order, with elements not in Set2
204%   deleted.  If Set1 contains duplicates, so may Intersection..
205
206intersect([], _, []).
207intersect([Element|Residue], Set, [Element|Intersection]) :-
208	memberchk(Element, Set), !,
209	intersect(Residue, Set, Intersection).
210intersect([_|Rest], Set, Intersection) :-
211	intersect(Rest, Set, Intersection).
212
213
214
215%   subtract(+Set1, +Set2, ?Difference)
216%   is like intersect, but this time it is the elements of Set1 which
217%   *are* in Set2 that are deleted.
218
219subtract([], _, []).
220subtract([Element|Residue], Set, Difference) :-
221	memberchk(Element, Set), !,
222	subtract(Residue, Set, Difference).
223subtract([Element|Residue], Set, [Element|Difference]) :-
224	subtract(Residue, Set, Difference).
225
226
227
228%   symdiff(+Set1, +Set2, ?Diff)
229%   is true when Diff is the symmetric difference of Set1 and Set2,
230%   that is, if each element of Union occurs in one of Set1 and Set2,
231%   but not both.  The construction method is such that the answer
232%   will contain no duplicates even if the Sets do.
233
234symdiff(Set1, Set2, Diff) :-
235	symdiff(Set1, Set2, Diff, Mid),
236	symdiff(Set2, Set1, Mid, []).
237
238symdiff([Elem|Rest], Avoid, Diff, Tail) :-
239	memberchk(Elem, Avoid), !,
240	symdiff(Rest, Avoid, Diff, Tail).
241symdiff([Elem|Rest], Avoid, [Elem|Diff], Tail) :- !,
242	symdiff(Rest, [Elem|Avoid], Diff, Tail).
243symdiff([], _, Tail, Tail).
244
245
246
247%   union(+Set1, +Set2, ?Union)
248%   is true when subtract(Set1,Set2,Diff) and append(Diff,Set2,Union),
249%   that is, when Union is the elements of Set1 that do not occur in
250%   Set2, followed by all the elements of Set2.
251
252union([], Set2, Set2).
253union([Element|Residue], Set, Union) :-
254	memberchk(Element, Set), !,
255	union(Residue, Set, Union).
256union([Element|Residue], Set, [Element|Union]) :-
257	union(Residue, Set, Union)```