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