1:- module(pset, [
    2    pset_empty/2,
    3    list_set/3,
    4    set_list/2,
    5    subset/3,
    6    punion/3,
    7    pdifference/3,
    8    pintersection/3
    9]).   10
   11:- use_module(purity).   12
   13
   14% p_is_set/1
   15pset_empty(Domain, set(Domain, [])).
   16
   17% subset(SubSet, Set, Truth)
   18%
   19% Truth is true if Set contains SubSet, otherwise false.
   20%
   21subset(set(D, Sub), set(D, Set), T) :-
   22    subset_(Sub, Set, D, T).
   23
   24subset_([],_,_,true).
   25subset_([A|Sub],Set,D,T) :-
   26    subset__(Set, [A|Sub],D,T).
   27
   28subset__([],_,_,false).
   29subset__([B|Set],[A|Sub],D,T) :-
   30    pcompare(D,A,B,C),
   31    subset_c(C,[A|Sub],[B|Set],D,T).
   32
   33subset_c(=,[_|Sub],[_|Set],D,T) :- 
   34    subset_(Sub,Set,D,T).
   35subset_c(<,_,_,_,false).
   36subset_c(>,Sub,[_|Set],D,T) :- 
   37    subset_(Sub,Set,D,T).
   38
   39% list_set(Domain, List, Set).
   40
   41list_set(D, L, set(D, Set)) :-
   42    psort(D,L,B),
   43    remove_dups_sorted(B,D,Set).
   44
   45remove_dups_sorted([], _, []).
   46remove_dups_sorted([A|T],D,R) :-
   47    remove_dups_sorted_(T,A,D,R).
   48
   49remove_dups_sorted_([],A,_,[A]).
   50remove_dups_sorted_([B|T],A,D,R) :-
   51    pdif(D,A,B,C),
   52    remove_dups_sorted_(C,[A,B|T],D,R).
   53
   54remove_dups_sorted_(true,[A,B|T],D,[A|R]) :-
   55    remove_dups_sorted([B|T],D,R).
   56remove_dups_sorted_(false,[A,A|T],D,R) :-
   57    remove_dups_sorted([A|T],D,R).
   58
   59
   60set_list(set(_, List), List).
   61
   62
   63% punion/3
   64punion(set(D,S1),set(D,S2),set(D,S3)) :-
   65    punion_(S1,S2,S3,D).
   66 
   67punion_([],B,B,_).
   68punion_([A|At],B,R,D) :-
   69    punion_1(B,[A|At],R,D).
   70
   71punion_1([],A,A,_).
   72punion_1([B|Bt],[A|At],R,D) :-
   73    pcompare(D,A,B,C),
   74    punion_c(C,[A|At],[B|Bt],R,D).
   75
   76punion_c(=,[A|At],[A|Bt],[A|R],D) :- 
   77    punion_(At,Bt,R,D).
   78punion_c(<,[A|At],[B|Bt],[A|R],D) :- 
   79    punion_(At,[B|Bt],R,D).
   80punion_c(>,[A|At],[B|Bt],[B|R],D) :- 
   81    punion_([A|At],Bt,R,D).
   82
   83
   84% difference(Set1, Set2, Set3).
   85%
   86% Set3 is Set1 - Set2
   87%
   88pdifference(set(D,S1),set(D,S2),set(D,S3)) :-
   89    pdifference_(S1,S2,S3,D).
   90 
   91pdifference_([],_,[],_).
   92pdifference_([A|At],B,R,D) :-
   93    pdifference_1(B,[A|At],R,D).
   94
   95pdifference_1([],A,A,_).
   96pdifference_1([B|Bt],[A|At],R,D) :-
   97    pcompare(D,A,B,C),
   98    pdifference_c(C,[A|At],[B|Bt],R,D).
   99
  100pdifference_c(=,[A|At],[A|Bt],R,D) :- 
  101    pdifference_(At,Bt,R,D).
  102pdifference_c(<,[A|At],[B|Bt],[A|R],D) :- 
  103    pdifference_(At,[B|Bt],R,D).
  104pdifference_c(>,[A|At],[_|Bt],[A|R],D) :- 
  105    pdifference_([A|At],Bt,R,D).
  106
  107
  108% pintersection/3
  109pintersection(set(D,S1),set(D,S2),set(D,S3)) :-
  110    pintersection_(S1,S2,S3,D).
  111 
  112pintersection_([],_,[],_).
  113pintersection_([A|At],B,R,D) :-
  114    pintersection_1(B,[A|At],R,D).
  115
  116pintersection_1([],_,[],_).
  117pintersection_1([B|Bt],[A|At],R,D) :-
  118    pcompare(D,A,B,C),
  119    pintersection_c(C,[A|At],[B|Bt],R,D).
  120
  121pintersection_c(=,[A|At],[A|Bt],[A|R],D) :- 
  122    pintersection_(At,Bt,R,D).
  123pintersection_c(<,[_|At],[B|Bt],R,D) :- 
  124    pintersection_(At,[B|Bt],R,D).
  125pintersection_c(>,[A|At],[_|Bt],R,D) :- 
  126    pintersection_([A|At],Bt,R,D)