Set Operations
/* difference(Xs, Ys, Zs) is true if Zs is the list of the set of elements */
/* in the difference of the sets of elements in lists Xs and Ys. The */
/* elements of Zs are in the same order as they are in Xs. */
difference([], _, []).
difference([X|Xs], Ys, Zs):-member(X, Ys), !, difference(Xs, Ys, Zs).
difference([X|Xs], Ys, [X|Zs]):-difference(Xs, Ys, Zs).
/* intersection(Xs, Ys, Zs) is true if Zs is the list of the set of */
/* elements in the intersection of the sets of elements in lists Xs and */
/* Ys. The elements of Zs are in the same order as they are in Xs. */
intersection([], _, []).
intersection([X|Xs], Ys, Ws):-
member(X, Ys), !, Ws = [X|Zs], intersection(Xs, Ys, Zs).
intersection([_|Xs], Ys, Zs):-intersection(Xs, Ys, Zs).
/* union(Xs, Ys, Zs) is true if Zs is the list of the set of elements in */
/* the union of the sets of elements in lists Xs and Ys. The elements */
/* of Zs are the elements of Xs which are not also elements of Ys, in */
/* the same order as they are in Xs, followed by the elements of Ys in */
/* the same order as they are in Ys. */
union([], Ys, Ys).
union([X|Xs], Ys, Zs):-member(X, Ys), !, union(Xs, Ys, Zs).
union([X|Xs], Ys, [X|Zs]):-union(Xs, Ys, Zs).
/* subset(Set, Subset) is true if Subset is a subset of Set. */
subset([], []).
subset([_|Xs], Ys):-subset(Xs, Ys).
subset([X|Xs], [X|Ys]):-subset(Xs, Ys).
/* powerset(Set, PowerSet) is true if PowerSet is a list of all subsets of */
/* the Set. The items in the subsets are in the reverse order of the */
/* same items in the Set. */
/* e.g. powerset([1,2,3], [[],[3],[2],[3,2],[1],[3,1],[2,1],[3,2,1]]). */
powerset(Set, PowerSet):-
powerset_1(Set, [[]], PowerSet).
powerset_1([], Yss, Yss).
powerset_1([X|Xs], Yss0, Yss):-
powerset_2(Yss0, X, Yss1),
powerset_1(Xs, Yss1, Yss).
powerset_2([], _, []).
powerset_2([Zs|Zss], X, [Zs, [X|Zs]|Yss]):-
powerset_2(Zss, X, Yss).
/* set(Xs, Ys) is true if Ys is the list of the elements appearing in Xs */
/* without duplication. The elements in Ys are in the reverse order of */
/* Xs with the first duplicate values being kept. */
set(Xs, Ys):-set_1(Xs, [], Ys).
set_1([], As, As).
set_1([X|Xs], As, Ys):-member(X, As), !, set_1(Xs, As, Ys).
set_1([X|Xs], As, Ys):-set_1(Xs, [X|As], Ys).
LPA Index
Home Page