% File : SETUTL.PL
% Author : Lawrence Byrd + R.A.O'Keefe
% Updated: 19 July 1984
% Purpose: Set manipulation utilities
% Sets are represented as lists with no repeated elements.
% An ordered representation could be much more efficient, but
% these routines were designed before sort/2 entered the language.
:- public
add_element/3, % Elem x Set -> Set
del_element/3, % Elem x Set -> Set
disjoint/1, % List ->
disjoint/2, % Set x Set ->
intersect/2, % Set x Set ->
intersect/3, % Set x Set -> Set
% length/2, % List -> Integer
listtoset/2, % List -> Set
member/2, % Elem <- Set
memberchk/2, % Elem x Set ->
nonmember/2, % Elem x Set ->
pairfrom/4, % Set -> Elem x Elem x Set
select/3, % Elem <- Set -> Set
seteq/2, % Set x Set ->
subset/2, % Set x Set ->
subtract/3, % Set x Set -> Set
symdiff/3, % Set x Set -> Set
union/3. % Set x Set -> Set
:- mode
% length(+, -),
% length(+, +, -),
member(?, ?),
memberchk(+, +),
nonmember(+, +),
pairfrom(?, ?, ?, ?),
select(?, ?, ?),
add_element(+, +, -),
del_element(+, +, -),
disjoint(+),
disjoint(+, +),
intersect(+, +),
subset(+, +),
seteq(+, +),
listtoset(+, ?),
intersect(+, +, ?),
subtract(+, +, ?),
symdiff(+, +, ?),
symdiff(+, +, ?, ?),
union(+, +, ?).
/* length(List, Length) is true when Length is the number of elements
in List. The definition here is correct, but length is actually in
the Prolog system. Note that this comment is unclosed!
length(List, Length) :-
length(List, 0, Length).
length([], Length, Length).
length([_|Tail], SoFar, Length) :-
Count is SoFar+1,
length(Tail, Count, Length).
/* end of comment */
% member(?Element, ?Set)
% is true when Set is a list, and Element occurs in it. It may be used
% to test for an element or to enumerate all the elements by backtracking.
% Indeed, it may be used to generate the Set!
member(Element, [Element|_]).
member(Element, [_|Rest]) :-
member(Element, Rest).
% memberchk(+Element, +Set)
% means the same thing, but may only be used to test whether a known
% Element occurs in a known Set. In return for this limited use, it
% is more efficient when it is applicable.
memberchk(Element, [Element|_]) :- !.
memberchk(Element, [_|Rest]) :-
memberchk(Element, Rest).
% nonmember(+Element, +Set)
% means that Element does not occur in Set. It does not make sense
% to instantiate Element in any way, as there are infinitely many
% terms which do not occur in any given set. That being so, it is
% sensible to test for membership using == rather than =. So
% nonmember(X, S) is not quite the same as \+member(X, S).
nonmember(_, []).
nonmember(X, [H|T]) :-
X \== H,
nonmember(X, T).
% add_element(Elem, Set1, Set2)
% is true when Set1 and Set2 are sets represented as unordered lists,
% and Set2 = Set1 U {Elem}. It may only be used to calculate Set2
% given Elem and Set1. However, if Set1 is a list with a variable at
% the end, it may still be used, and will add new elements at the end.
add_element(Elem, Set, Set) :-
memberchk(Elem, Set),
!.
add_element(Elem, Set, [Elem|Set]).
% del_element(Elem, Set1, Set2)
% is true when Set1 and Set2 are sets represented as unordered lists,
% and Set2 = Set1 \ {Elem}. It may only be used to calculate Set2
% given Elem and Set1. If Set1 does not contain Elem, Set2 and Set1
% will be equal. I wanted to call this predicate 'delete', but other
% Prologs have used that for 'select'. If Set1 is not an unordered
% set, but contains more than one copy of Elem, only the first will
% be removed.
del_element(Elem, [Elem|Set2], Set2) :- !.
del_element(Elem, [X|Set1], [X|Set2]) :- !,
del_element(Elem, Set1, Set2).
del_element(_, [], []).
% disjoint(+Set)
% is true when Set is a list that contains no repeated elements.
% disjoint/1 and disjoint/2 used to be defined using \+, but for
% speed (as the Dec-10 compiler does not understand \+), this is
% no longer so. Sorry 'bout the !,fails, the price of speed.
disjoint([Head|Tail]) :-
memberchk(Head, Tail),
!, fail.
disjoint([_|Tail]) :- !,
disjoint(Tail).
disjoint([]).
% disjoint(+Set1, +Set2)
% is true when the two given sets have no elements in common.
% It is the opposite of intersect/2.
disjoint(Set1, Set2) :-
member(Element, Set1),
memberchk(Element, Set2),
!, fail.
disjoint(_, _).
% select(?Element, ?Set, ?Residue)
% is true when Set is a list, Element occurs in Set, and Residue is
% everything in Set except Element (things stay in the same order).
select(Element, [Element|Rest], Rest).
select(Element, [Head|Tail], [Head|Rest]) :-
select(Element, Tail, Rest).
% 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.
pairfrom([Element1|Set], Element1, Element2, Residue) :-
select(Element2, Set, Residue).
pairfrom([Head|Tail], Element1, Element2, [Head|Rest]) :-
pairfrom(Tail, Element1, Element2, Rest).
% 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.
intersect(Set1, Set2) :-
member(Element, Set1), % generates Elements from Set1
memberchk(Element, Set2), % tests them against Set2
!. % if it succeeds once, is enough.
% 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. At the moment there is NO predicate for
% generating subsets, but select/3 takes you part-way.
subset([], _).
subset([Element|Residue], Set) :-
memberchk(Element, Set), !,
subset(Residue, Set).
% seteq(+Set1, +Set2)
% is true when each Set is a subset of the other. There are two
% ways of doing this. One is commented out.
seteq(Set1, Set2) :-
subset(Set1, Set2),
subset(Set2, Set1).
% sort(Set1, Ord1),
% sort(Set2, Ord2),
% Ord1 == Ord2.
% listtoset(+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. If you really want to
% convert a list to a set, list_to_ord_set is faster, but this way
% preserves as much of the original ordering as possible.
listtoset([], []).
listtoset([Head|Tail], Set) :-
memberchk(Head, Tail), !,
listtoset(Tail, Set).
listtoset([Head|Tail], [Head|Set]) :-
listtoset(Tail, Set).
% intersect(+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 that order, with elements not in Set2
% deleted. If Set1 contains duplicates, so may Intersection.
% This routine is due to Peter Ross and avoids the problem that
% in the (otherwise) obvious definition,
% ?- intersection([a,b,c],[a,b,c],[c]) will succeed.
intersect([], _, []).
intersect([Element|Residue], Set, Result) :-
member(Element, Set), % Need not be "memberchk" because of
!, % the cut here
Result = [Element|Intersection],
intersect(Residue, Set, Intersection).
intersect([_|Rest], Set, Intersection) :-
intersect(Rest, Set, Intersection).
% subtract(+Set1, +Set2, ?Difference)
% is like intersect, but this time it is the elements of Set1 which
% *are* in Set2 that are deleted.
subtract([], _, []).
subtract([Element|Residue], Set, Difference) :-
memberchk(Element, Set), !,
subtract(Residue, Set, Difference).
subtract([Element|Residue], Set, [Element|Difference]) :-
subtract(Residue, Set, Difference).
% symdiff(+Set1, +Set2, ?Diff)
% is true when Diff is the symmetric difference of Set1 and Set2,
% that is, if each element of Union occurs in one of Set1 and Set2,
% but not both. The construction method is such that the answer
% will contain no duplicates even if the Sets do.
symdiff(Set1, Set2, Diff) :-
symdiff(Set1, Set2, Diff, Mid),
symdiff(Set2, Set1, Mid, []).
symdiff([Elem|Rest], Avoid, Diff, Tail) :-
memberchk(Elem, Avoid), !,
symdiff(Rest, Avoid, Diff, Tail).
symdiff([Elem|Rest], Avoid, [Elem|Diff], Tail) :- !,
symdiff(Rest, [Elem|Avoid], Diff, Tail).
symdiff([], _, Tail, Tail).
% 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.
union([], Set2, Set2).
union([Element|Residue], Set, Union) :-
memberchk(Element, Set), !,
union(Residue, Set, Union).
union([Element|Residue], Set, [Element|Union]) :-
union(Residue, Set, Union).