/* 

  Some set predicates in Picat.

  Port of the B-Prolog code
  http://www.sci.brooklyn.cuny.edu/~zhou/teaching/cis2210/set.pl
  """
  by Neng-Fa Zhou, January 2012
  These predicates in B-Prolog (www.probp.com) implement the set operations 
  covered in my Discrete Structures class. As the students are not yet familiar 
  with recursion, no recursion is used except for power/2. 
  """

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

module set_util.

% main => test.


test =>
    A = [X : X in 0..11],
    B = [X : X in 0..18, X mod 2 == 0],
    write('A='),writeln(A),
    write('B='),writeln(B),
    AuB=union(A,B), writeln($union(AuB)),
    AiB=intersection(A,B), writeln($intersection(AiB)),
    AmB=difference(A,B),writeln($difference(AmB)),
    AxB=xorx(A,B),writeln($xorx(AxB)),

    C = [1,2,3,4],
    D = [4,5,6],
    Power=power(C),writeln($power(Power)),
    Product=product(C,D),writeln($product(Product)),

    E = [2,3],
    if subset(E,C) then printf("%w is a subset of %w\n", E,C) end,

    nl.

% test if A is a subset of B
subset(A,B)=>
    foreach(X in A) member(X,B) end.

% test if A is a proper subset of B
proper_subset(A,B)=>
    subset(A,B),
    member(X,B), 
    not member(X,A).

% test if sets A and B are equal
equal(A,B)=>
    subset(A,B),
    subset(B,A).

% C is the union of A and B
union(A,B) = C =>
    append(A,B,AB),
    C=sort(AB).remove_dups().   % eliminate duplicates

% C is the intersection of A and B
intersection(A,B) = C =>
    C = [X : X in A, member(X,B)].

% C is the relative complement of A w.r.t. B (A-B)
difference(A,B) = C =>
    C = [X : X in A, not member(X,B)].

% C is the exclusive or of A and B.
xorx(A,B) = C =>
    C = [X : X in A, not member(X,B)] ++ [X : X in B, not member(X,A)].

% P is the product of A and B
product(A,B) = P =>
    P = [(X,Y) : X in A, Y in B].

% P is the power set of A
power([]) = P => P = [[]].
power([H|T]) = P =>
    P1 = power(T),
    P2 = [[H|S] : S in P1],
    append(P1,P2,P).