Why would Prolog match a variable to a result that

Question

I'm making a Prolog program that finds a subset of a set of lists. This subset must match some specific conditions, an aspect of which is that the subset's lists cannot be identical. What's confusing me is that when I try to find a match for a variable, X, it generates results that return false if I plug them into the query in place of X. For example:

?- containsSet(2, [[3],[7],[7]], X).
X = [[3], [7]] ;
X = [[3], [7]] ;
X = [[7], [7]] ;
false.

?- containsSet(2, [[3],[7],[7]], [[7],[7]]).
false.

How could it possibly match X to [[7], [7]] if, when plugged in directly, it returns false?

The idea of containsSet is to find a length-N (in this case 2) subset of lists that has no matching elements in matching positions (i.e. no two lists in the subset have the same first element, or the same second element, etc). In the example above, the first (and only) elements of [7] and [7] match, so it returns false.

Answer 1

First, congratulations for one of the most declarative and justified observations I have seen in questions by beginners!

On the one hand, it is one of the most basic and well-known properties that conjunction is commutative in logic. On the other hand, many Prolog beginners fail to realize that using one of the non-monotonic predicates like (\+)/1 almost invariably destroys such basic invariants. You noticed that something very unexpected is going on here, and you are right to expect more correct behaviour from Prolog. Luckily, declarative solutions for such problems are now more widely spread than ever before among Prolog systems.

First, consider some problems that soon arise if you use (\+)/1 in your programs:

?- X = d, \+ member(X, [a,b,c]).
X = d.

yet, if we simply exchange the goals by commutativity of conjunction, we get the different answer:

?-  \+ member(X, [a,b,c]), X = d.
false.

This shows that (\+)/1 is not monotonic: It can cause a more general query to fail although a more specific query yields solutions:

?-  \+ member(X, [a,b,c]).
false.

?- \+ member(d, [a,b,c]).
true.

Thus, non-monotonic predicates cause all kinds of impurities and violate declarative semantics. Declaratively, knowing that there are solutions, we certainly expect the more general query to succeed, but it fails.

In this concrete, to specify that a term is different from all other terms in a list, use the constraint dif/2. dif/2 works in all directions, and yields correct answers also if its arguments are variables. For example:

not_member(X, Ls) :- maplist(dif(X), Ls).

This definition preserves commutativity of conjunction, as we deeply desire and in fact expect from pure logical relations:

?- not_member(X, [a,b,c]), X = d.
X = d.

?- X = d, not_member(X, [a,b,c]).
X = d.

Since not_member/2 uses only pure predicates, you have ensured — already by construction — that it gives only declaratively correct answers.

For reasoning declaratively about your code, which I applaud in your approach, I recommend you stay in the pure monotonic subset of Prolog. See logical-purity and prolog-dif for more information.