Appeared in Volume 8/3, August 1995

Richard A. O'Keefe

A few months ago, in the comp.lang.prolog newsgroup, I offered the following code for subset/2:

member(X, [X|_]). member(X, [_|Xs]) :- member(X, Xs). subset([], _). subset([X|Xs], Ys) :- member(X, Ys), subset(Xs, Ys).and pointed out that the query

`?- subset([A,B], [1,2,3]).`

finds all nine solutions:

B = 1, A = 1 ; B = 2, A = 1 ; B = 3, A = 1 ; B = 1, A = 2 ; B = 2, A = 2 ; B = 3, A = 2 ; B = 1, A = 3 ; B = 2, A = 3 ; B = 3, A = 3 .Gerard Ellis challenged me about this, claiming that there are

I started from the meaning:

subset(Small, Large) is to be true if and only if Small is a list containing the elements of a set in no particular order, possibly containing duplicates. Large is a list containing the elements of a set in no particular order, possibly containing duplicates. Also, the set that Small represents is a subset of the set that Large represents.

In particular, this means that:

`subset(X, [1])`

has infinitely many solutions:

`X = [] ; X = [1] ; X = [1,1] ; X = [1,1,1] ; ...`

The fact that duplicates are allowed in Small meant that the solutions [1,1],
[2,2], and [3,3] are allowed. These are solutions with *two*-element
*lists* representing *one*-element *sets*.

You *have* to be explicit about your intended representation of sets. In
my view, there is only really one good choice in plain Prolog (a list in sorted
order without duplicates); there are also extensions of Prolog with direct
support for sets.

Suppose we now decide that a list representing a set should not contain duplicates, and we say:

subset(Small, Large) is only to be used when Large is a list containing the elements of a set in no particular order, there being no duplicates. It is then true when Small is a list containing the elements of a set in no particular order, there being no duplicates. Also, the set that Small represents is a subset of the set that Large represents.

In that case, we need different code, because the meaning is different.

subset([], _). subset([X|Xs], Set) :- select(X, Set, Set1), subset(Xs, Set1). select(X, [X|R], R). select(X, [H|T], [H|R]) :- select(X, T, R).The use of select/3 instead of member/2 ensures that no element can be selected twice. (This is a standard technique.) With this definition, the query:

`?- subset(X, [1]).`

has precisely two answers: X = [] ; X = [1]

and the query:

`?- subset([A,B], [1,2,3]).`

has the six answers:

B = 2, A = 1 ; B = 3, A = 1 ; B = 1, A = 2 ; B = 3, A = 2 ; B = 1, A = 3 ; B = 2, A = 3.The three sets {1,2}, {1,3}, and {2,3} are each represented by two lists. It is

If we want a one-to-one correspondence between lists and sets, we have to use a data structure with this correspondence built in, such as the sorted list representation. We can build a subset predicate which assumes this representation in Large and thereby implicitly yields it in Small:

subset([], _). subset([X|Xs], Set) :- append(_, [X|Set1], Set), subset(Xs, Set1). append([], L, L). append([H|T], L, [H|R]) :- append(T, L, R).With this definition, the query:

`?- subset([A,B], [1,2,3]).`

has the three answers:

`B = 2, A = 1 ; B = 3, A = 1 ; B = 3, A = 2.`

Note, however, that the query:

`?- subset([A,B], [3,2,1]).`

yields answers where the first argument is *not* a sorted list. The
implementation *assumes* the validity of the second argument.

If you want a subset predicate where the second argument is in no particular order, but you still get only one list for each possible subset, you have to force the order you want. One way to do that is this:

subset([], _). subset([X|Xs], Set) :- select(X, Set, Set1), subset(Xs, X, Set1). subset([], _, _). subset([X|Xs], Z, Set) :- select(X, Set, Set1), X @> Z, subset(Xs, X, Set1).which will yield sorted subsets whether the second argument is sorted or not, and whether the second argument contains duplicates or not. It requires only that the second argument be ground.

The important point here is: what counts as a valid solution to the question
subset(S, L), and hence what counts as a correct implementation of the
predicate, depends on what meaning you *want* subset/2 to have. In other
words, it depends on exactly which lists are allowed as representatives of any
given set. Other set data structures are possible.

Richard A. O'Keefe Dept. of Computer Science, RMIT Melbourne, Australia Email: ok@goanna.cs.rmit.edu.au URL: http://www.cs.rmit.edu.au/~ok