title: Properly working with sets in Prolog
body: <p>In Prolog it seems that sets are represented using lists.</p>
  
  <p>For example, here is the implementation of <code>union/3</code> from SWI-Prolog:</p>
  
  <pre><code>union([], L, L) :- !.
  union([H|T], L, R) :-
      memberchk(H, L), !,
      union(T, L, R).
  union([H|T], L, [H|R]) :-
  union(T, L, R).
  </code></pre>
  
  <p>However this predicate isn't very declarative, for example:</p>
  
  <pre><code>?- union([1,2,3],X,[1,2,3,4]).
  X = [1, 2, 3, 4].
  </code></pre>
  
  <p>which should leave some choice points, or:</p>
  
  <pre><code>?- union(X,[1,2],[1,2,3,4]).
  &lt;infinite loop&gt;
  </code></pre>
  
  <p>which doesn't even work!</p>
  
  <p><strong>That aside</strong>, we also find the following problems:</p>
  
  <pre><code>?- union([1,2,3],[4,5],[1,2,3,5,4]).
  false.
  
  ?- union([1,1,1],[4,5],[1,1,1,4,5]).
  true.
  </code></pre>
  
  <p>which are obviously wrong if we would be really talking about sets.</p>
  
  <p>We can clearly see that using lists to talk about sets isn't straightforward because:</p>
  
  <ul>
  <li>Sets are not ordered whereas lists are;</li>
  <li>Sets do not contain duplicate values whereas lists can.</li>
  </ul>
  
  <p>As a consequence we either find predicates working on sets that cut possible solutions (e.g. this implementation of union which only works if the set is ordered) or predicates which provide useless choice points depending on variables' instanciation (e.g. a union predicate which would have as many choice points as the number of permutations of the resulting set).</p>
  
  <p><strong>How should predicates that work on sets be properly implemented in Prolog?</strong></p>
  
  <p><em>This question is very general and not specific to the example of <code>union/3</code> used here.</em></p>