Properly working with sets in Prolog

Question

In Prolog it seems that sets are represented using lists.

For example, here is the implementation of union/3 from SWI-Prolog:

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).

However this predicate isn't very declarative, for example:

?- union([1,2,3],X,[1,2,3,4]).
X = [1, 2, 3, 4].

which should leave some choice points, or:

?- union(X,[1,2],[1,2,3,4]).
<infinite loop>

which doesn't even work!

That aside, we also find the following problems:

?- union([1,2,3],[4,5],[1,2,3,5,4]).
false.

?- union([1,1,1],[4,5],[1,1,1,4,5]).
true.

which are obviously wrong if we would be really talking about sets.

We can clearly see that using lists to talk about sets isn't straightforward because:

• Sets are not ordered whereas lists are;
• Sets do not contain duplicate values whereas lists can.

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).

How should predicates that work on sets be properly implemented in Prolog?

This question is very general and not specific to the example of union/3 used here.

Answer 1

If you want the very general notion, you will have to implement your own data type, with its own unification algorithm. Compared to your previous question, AC-unification is "much" simpler than pure associative unification. You "only" have to solve Diophantine equations and the like. There is much more literature on AC-unification than there is on associative unification.

But that really is more of a research project than a programming task. What can you do in pure Prolog today?

You can approximate sets with lists in a still pure and declarative way, provided you take into account functional dependencies. See this answer for more!

Answer 2

How should predicates that work on sets be properly implemented in Prolog?

First of all a union predicate in prolog should respect the basic mathematical properties of set union so it which are:

• associativity: A ∪ (B ∪ C) = (A ∪ B) ∪ C
• commutative: A ∪ B = B ∪ A

(These properties ensure that union is unambiguous which though shouldn't concern a Prolog predicate implementation with to arguments.)

Moreover a union implementation( or other set-predicates) should also have the following properties in Prolog:

• Handle duplicates.

If one of the lists have at least an element more than one times then this element should be counted only one time.

• Handle cases where at least one argument is not instantiated.

for example Union([X],Union_Set,[Y]). should obviously return Union_set=[X,Y]. Another example : Union([X],[X1,Y1],[Y]). should obviously return X1=X, Y1=Y. through unification.

• Be deterministic Union is a set is the set of all distinct elements in the collection. This definition is well defined (mathematically) which doesn't leave nonuniqueness option (the result must be unique for every well defined mathematical operation(not only for union) ).
• Also another desird feature could be logical purity which is provided by the algebraic properties (commutative,associativity).
• Handle infinite loop-occasions.

As in your example in union predicate: union(X,[1,2],[1,2,3,4]). should return some instantiation error.

These are some features that I should be included since we are talking about Set operations, but of course these are not all the properties that we could consider. This has to do also with the implementations that we make when defining predicates.

Finally one more comment on: Sets are not ordered whereas lists are;

This is not true. Partial or total ordering applies in both lists and sets and it is has to do whether if we can compare all elements or just some elements, which means that we can put them in order. Any data structure like lists doesn't provide the order (order has to do with semantics) unless we consider it as for example in a heap where it is a tree structure but we consider that is ordered.