CODEWITHSUNDEEP
prologsetnegation
Michael Schuller
Michael Schuller

Reputation: 494

Negation and testing for a unique set in Prolog

I've just started experimenting with Prolog, and I was trying to write a rule to find out whether a list contained only unique elements. I got it working in the second variation (by negating a positive test), but I've completely failed to understand why the first variation doesn't work.

Given this file:

uniqueElements([X|Y]) :-
     notmember(X, Y),
     uniqueElements(Y).

notmember(X, Y) :-
     \+ member(X, Y).

hasRepeatedElements([X|Y]) :-
     (
         member(X, Y) ->
         true
     ;   hasRepeatedElements(Y)
     ).

uniqueElements_2(X) :-
     \+ hasRepeatedElements(X).

The GNU Prolog interpreter gives these responses:

| ?- uniqueElements([1,2,3]).

no
| ?- uniqueElements([1,2,3,2,3]).

no

| ?- uniqueElements_2([1,2,3]).

yes
| ?- uniqueElements_2([1,2,3,2,3]).

no

Why is the first response 'no'? (I would have expected member to return false, be negated to true, and thus have notmemeber return true on each iteration of uniqueElements). I guess I'm expecting '\+' to behave like '!' does in a C if clause, or the 'not' keyword in Python. Is this a misunderstanding?

Upvotes: 1

Views: 264

Answers (1)

Will Ness
Will Ness

Reputation: 71119

In uniqueElements, you haven't provided the base case for the recursion:

uniqueElements([]).

Without that clause, when a particular call chain gets to the empty list case, it doesn't find any applicable clauses, which means fail in Prolog. Meaning, "unprovable". So, your call uniqueElements([1,2,3]) has produced an equivalent of true && true && true && false.

Now it should work.

hasRepeatedElements doesn't have a clause defined for the base case either, but its failure in finding whether there were repeated elements in an empty list [] is consistent with its semantics - it should have found that there are no repeated elements in empty list, in the first place.

In Prolog, "not" means "can't prove that ...".

Upvotes: 2

Related Questions