5

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.

false
  • 10,264
  • 13
  • 101
  • 209
Fatalize
  • 3,513
  • 15
  • 25
  • 2
    Too lazy for an answer right now, but you should take a look at least at library(ordsets). You can also use a "look-up table" as implemented in library(assoc) and SWI-Prolog's `dict` as a set: use the keys, all values can be the atom `true` or something along these lines. They don't provide ready answers to your your question, but at least they are better set implementation than what you are showing. –  Nov 02 '16 at 16:44

3 Answers3

3

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!

Community
  • 1
  • 1
false
  • 10,264
  • 13
  • 101
  • 209
3

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.

coder
  • 12,832
  • 5
  • 39
  • 53
  • 4
    If you are into algebraic properties like associativity and commutativity, you will inevitably have already accepted logical purity. For, without it, those properties will not materialize! – false Nov 02 '16 at 16:56
  • 2
    Indeed very useful comment @false, thanks!!! I will edit the answer were I mention the logical purity. – coder Nov 02 '16 at 16:59
2

First, to add an additional example of what we currently have to cope with:

?- union(A, [], A).
A = [].

Which we can read as:

The empty set is the only set.

Who would have thought?

A very nice library for reasoning about sets is available in ECLiPSe as library(conjunto):

Conjunto is a system to solve set constraints over finite set domain terms. It has been developed using the kernel of ECLiPSe based on metaterms. It contains the finite domain library of ECLiPSe. The library conjunto.pl implements constraints over set domain terms that contain herbrand terms as well as ground sets.

Note also:

As of ECLiPSe release 5.1, the library described in this chapter is being phased out and replaced by the new set solver library lib(ic_sets).

These are great libraries, and I recommend you use them as a starting point if you are interested in set constraints.

A nice example of what can be done with set constraints is available from:

http://csplib.org/Problems/prob010/models/golf.ecl.html

mat
  • 40,498
  • 3
  • 51
  • 78
  • 1
    A slightly different interpretation of your first example: Only the empty set unifies with the empty set. – false Nov 02 '16 at 17:23
  • 1
    On the other hand, this specialization succeeds:`?- A = [a], union(A, [], A).` – mat Nov 03 '16 at 11:11
  • 1
    Indeed, we cannot give the entire definition any meaningful interpretation. We can only give concrete answers one. – false Nov 03 '16 at 11:13
  • csplib.org link now needs "www.": https://www.csplib.org/Problems/prob010/models/golf.ecl.html. If it breaks again, it's the "Social Golfers Problem" – GeoffChurch Mar 05 '22 at 13:52