(SWI)Prolog: Order of sub-goals

Question

I have two, slightly different, implementations of a predicate, unique_element/2, in Prolog. The predicate succeeds when given an element X and a list L, the element X appears only once in the list. Below are the implementations and the results:

Implementation 1:

%%% unique_element/2
unique_element(Elem, [Elem|T]) :-
    not(member(Elem, T)). 
unique_element(Elem, [H|T]) :-
    member(Elem, T), 
    H\==Elem, 
    unique_element(Elem, T), 
    !. 

Results:

?- unique_element(X, [a, a, b, c, c, b]). 
false.

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

Implementation 2:

%%% unique_element/2
unique_element(Elem, [Elem|T]) :- 
    not(member(Elem, T)). 
unique_element(Elem, [H|T]) :-
    H\==Elem, 
    member(Elem, T), 
    unique_element(Elem, T), 
    !. 

In case you didn't notice at first sight: H\==Elem and member(Elem, T) are flipped on the 2nd impl, rule 2.

Results:

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

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

Question: How does the order, in this case, affect the result? I realize that the order of the rules/facts/etc matters. The two specific rules that are flipped though, don't seem to be "connected" or affect each other somehow (e.g. a cut in the wrong place/order).

Note: We are talking about SWI-Prolog here.

Note 2: I am aware of, probably different and better implementations. My question here is about the order of sub-goals being changed.

Answer 1

TL;DR: Read the documentation and figure out why:

?- X = a, X \== a.
false.

?- X \== a, X = a.
X = a.

---

I wonder why you stop so close from figuring it out yourself ;-)

There are too many ways to compare things in Prolog. At the very least, you have unification, which sometimes can compare, and sometimes does more; than you have equvalence, and its negation, the one you are using. So what does it do:

?- a \== b. % two different ground terms
true.

?- a \== a. % the same ground term
false.

Now it gets interesting:

?- X \== a. % a free variable and a ground term
true.

?- X \== X. % the same free variable
false.

?- X \== Y. % two different free variables
true.

I would suggest that you do the following: figure out how member/2 does its thing (does it use unification? equivalence? something else?) then replace whatever member/2 is using in all the examples above and see if the results are any different.

And since you are trying to make sure that things are different, try out what dif/2 does. As in:

?- dif(a, b).

or

?- dif(X, X).

or

?- dif(X, a).

and so on.

See also this question and answers: I think the answers are relevant to your question.

Hope that helps.

Answer 2

H\==Elem is testing for syntactic inequality at the point in time when the goal is executed. But later unification might make variables identical:

?- H\==Elem, H = Elem.
H = Elem.

?- H\==Elem, H = Elem, H\==Elem.
false.

So here we test if they are (syntactically) different, and then they are unified nevertheless and thus are no longer different. It is thus just a temporary test.

The goal member(Elem, T) on the other hand is true if that Elem is actually an element of T. Consider:

 ?- member(Elem, [X]).
 Elem = X.

Which can be read as

(When) does it hold that Elem is an element of the list [X]?

and the answer is

It holds under certain circumstances, namely when Elem = X.

If you now mix those different kinds of goals in your programs you get odd results that can only explained by inspecting your program in detail.

As a beginner, it is best to stick to the pure parts of Prolog only. In your case:

• use dif/2 in place of \==

• do not use cuts - in your case it limits the number of answers to two. As in unique_element(X, [a,b,c])

• do not use not/1 nor (\+)/1. It produces even more incorrectness. Consider unique_element(a,[a,X]),X=b. which incorrectly fails while X=b,unique_element(a,[a,X]) correctly succeeds.

---

Here is a directly purified version of your program. There is still room for improvement!

non_member(_X, []).
non_member(X, [E|Es]) :-
   dif(X, E),
   non_member(X, Es).

unique_element(Elem, [Elem|T]) :- 
    non_member(Elem, T). 
unique_element(Elem, [H|T]) :-
    dif(H,Elem), 
     % member(Elem, T),          % makes unique_element(a,[b,a,a|Xs]) loop
    unique_element(Elem, T).

?- unique_element(a,[a,X]).
   dif(X, a)
;  false.              % superfluous

?- unique_element(X,[E1,E2,E3]).
   X = E1,
   dif(E1, E3),
   dif(E1, E2)
;  X = E2,
   dif(E2, E3),
   dif(E1, E2)
;  X = E3,
   dif(E2, E3),
   dif(E1, E3)
;  false.

Note how the last query reads?

When is X a unique element of (any) list [E1,E2,E3]?

The answer is threefold. Considering one element after the other:

X is E1 but only if it is different to E2 and E3

etc.

Answer 3

Here is another possibility do define unique_element/2 using if_/3 and maplist/2:

:- use_module(library(apply)).

unique_element(Y,[X|Xs]) :-
   if_(Y=X,maplist(dif(Y),Xs),unique_element(Y,Xs)).

In contrast to @user27815's very elegant solution (+s(0)) this version does not build on clpfd (used by tcount/3). The example queries given by the OP work as expected:

   ?- unique_element(a,[a, a, b, c, c, b]).
no
   ?- unique_element(X,[a, b, c, c, b, d]).
X = a ? ;
X = d ? ;
no

The example provided by @false now succeeds without leaving a superfluous choicepoint:

   ?- unique_element(a,[a,X]).
dif(a,X)

The other more general query yields the same results:

   ?- unique_element(X,[E1,E2,E3]).
E1 = X,
dif(X,E3),
dif(X,E2) ? ;
E2 = X,
dif(X,E3),
dif(X,E1) ? ;
E3 = X,
dif(X,E2),
dif(X,E1) ? ;
no

Answer 4

Can you not define unique_element like tcount Prolog - count repetitions in list

unique_element(X, List):- tcount(=(X),List,1).