/*
    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. 

    The following built-ins are used:

        append(A,B,C): C is the concatenation of A and B
        member(X,A): X is an element of A
        sort(L1,L2): L2 is the sorted list of L1 without duplicates

    and the following loop constructs of B-Prolog are used:

        foreach(E1 in L1, E2 in L2, ..., En in Ln, Goal) 
            For each tuple of values E1 in L1, E2 in L2, ..., En in Ln, do Goal

        L @= [T : E1 in L1, E2 in L2, ..., En in Ln, Goal)
            Fach each tuple of values E1 in L1, E2 in L2, ..., En in Ln, 
            T is an element in list L if Goal succeeds.

    To run this program, follow the following steps:

        1. Save the program into a file, say named "set.pl".

        2. Open a command terminal.

        3. Change the directory to where "set.pl" is saved (say c:\Prolog).

              cd c:\Prolog

        4.  Start B-Prolog

              bp

        5.  Compile and load the program

              ?- cl(set).

        6.   Run the test predicate.

              ?-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),
    union(A,B,AuB), writeln(union(AuB)),
    intersection(A,B,AiB), writeln(intersection(AiB)),
    difference(A,B,AmB),writeln(difference(AmB)),
    xor(A,B,AxB),writeln(xor(AxB)).

% test if A is a subset of B
subset(A,B):-
    foreach(X in A, member(X,B)).

% 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),
    sort(AB,C).   % 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.
xor(A,B,C):-
    C1 @= [X : X in A, not member(X,B)],
    C2 @= [X : X in B, not member(X,A)],
    append(C1,C2,C).

% 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):-
    power(T,P1),
    P2 @= [[H|S] : S in P1],
    append(P1,P2,P).