Element appears exactly once in the list in Prolog

4
votes

I want to write a predicate which check if the Element appeares exactly once in the List.

once(Element, List).

My code:

once(X, [H | T]) :-
    \+ X = H,
    once(X, T).
once(X, [X | T]) :-
    \+ member(X, T).

?- once(c, [b,a,a,c,b,a]).
true

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

But if I ask:

once(X, [b,a,a,c,b,a]).

Prolog answers:

false

Why? Prolog should find X = c solution. Where is bug?

2
listprologpredicate
interesting - my first attempt at writing this procedure was exactly the same and I too was wondering why I couldn't substitute the 1st arg for a logvar – bph
i think the error comes from not fully grasping the concept of unification, i.e. using it in the wrong way here as you might use == in a procedural language – bph

2 Answers

2
votes

Running a trace in prolog can be very helpful in determining the answer to this sort of question. We'll do the trace manually here for illustration.

Let's look at your predicate:

once(X, [H | T]) :-
    \+ X = H,
    once(X, T).
once(X, [X | T]) :-
    \+ member(X, T).

Let's consider now the query:

once(X, [b,a,a,c,b,a]).

First, Prolog attempts the first clause of your predicate. The head is once(X, [H|T]) and first expression is \+ X = H, which will become:

once(X, [b|[a,a,c,b,a]]) :-  % [H|T] instantiated with [b,a,a,c,b,a] here
                             %   So, H is b, and T is [a,a,c,b,a]
    \+ X = b,
    ...

X is instantiated (be unified with) with the atom b here, and the result of that unification succeeds. However, you have a negation in front of this, so the result of \+ X = b, when X is initially unbound, will be false since X = b unifies X with b and is true.

The first clause thus fails. Prolog moves to the next clause. The clause head is once(X, [X|T]) and following is \+ member(X, T), which become:

once(b, [b|[a,a,c,b,a]]) :-    % X was instantiated with 'b' here,
                               %   and T instantiated with [a,a,c,b,a]
    \+ member(b, [a,a,c,b,a]).

member(b, [a,a,c,b,a]) succeeds because b is a member of [a,a,c,b,a]. Therefore, \+ member(b, [a,a,c,b,a]) fails.

The second clause fails, too.

There are no more clauses for the predicate once(X, [b,a,a,c,b,a]). All of them failed. So the query fails. The primary issue is that \+ X = H (or even X \= H, when X is not instantiated, won't choose a value from the list that is not the same as the value instantiated in H. Its behavior isn't logically what you want.

A more straight-on approach to the predicate would be:

once(X, L) :-           % X occurs once in L if...
    select(X, L, R),    % I can remove X from L giving R, and
    \+ member(X, R).    % X is not a member of R

The select will query as desired for uninstantiated X, so this will yield:

?- once(c, [b,a,a,c,b,a]).
true ;
false.

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

?- once(X, [b,a,a,c,b,a]).
X = c ;
false.

As an aside, I'd avoid the predicate name once since it is the name of a built-in predicate in Prolog. But it has no bearing on this particular problem.

2
votes

Using we can preserve !

The following code is based on the previous answer by @lurker, but is logically pure:

onceMember_of(X,Xs) :-
   select(X,Xs,Xs0),
   maplist(dif(X),Xs0).

Let's look at some queries:

?- onceMember_of(c,[b,a,a,c,b,a]).
true ;                              % succeeds, but leaves choicepoint
false.
?- onceMember_of(b,[b,a,a,c,b,a]).
false.
?- onceMember_of(X,[b,a,a,c,b,a]).
X = c ;
false.

The code is monotone, so we get logically sound answers for more general uses, too!

?- onceMember_of(X,[A,B,C]).
X = A, dif(A,C), dif(A,B) ;
X = B, dif(B,C), dif(B,A) ;
X = C, dif(C,B), dif(C,A) ;
false.

Let's look at all lists in increasing size:

?- length(Xs,_), onceMember_of(X,Xs).
Xs = [X] ;
Xs = [X,_A],        dif(X,_A) ;
Xs = [_A,X],        dif(X,_A) ;
Xs = [ X,_A,_B],    dif(X,_A), dif(X,_B) ;
Xs = [_A, X,_B],    dif(X,_A), dif(X,_B) ;
Xs = [_A,_B, X],    dif(X,_A), dif(X,_B) ;
Xs = [ X,_A,_B,_C], dif(X,_A), dif(X,_B), dif(X,_C) ...

At last, let's have the most general query:

?- onceMember_of(X,Xs).
Xs = [X] ;
Xs = [X,_A],       dif(X,_A) ;
Xs = [X,_A,_B],    dif(X,_A), dif(X,_B) ;
Xs = [X,_A,_B,_C], dif(X,_A), dif(X,_B),dif(X,_C) ...

Edit 2015-05-13

We can do even better by using selectfirst/3, a drop-in replacement of select/3:

onceMember_ofB(X,Xs) :-
   selectfirst(X,Xs,Xs0),
   maplist(dif(X),Xs0).

Let's run onceMember_of/2 and onceMember_ofB/2 head to head:

?- onceMember_of(c,[b,a,a,c,b,a]).
true ;                              % succeeds, but leaves choicepoint
false.
?- onceMember_ofB(c,[b,a,a,c,b,a]).
true.                               % succeeds deterministically

But we can still get better! Consider:

?- onceMember_ofB(X,[A,B,C]).
X = A, dif(A,C), dif(A,B) ;
X = B, dif(B,C), dif(A,B),dif(B,A) ;             % 1 redundant constraint
X = C, dif(A,C),dif(C,A), dif(B,C),dif(C,B) ;    % 2 redundant constraints
false.

Note the redundant dif/2 constraints? They come from the goal maplist(dif(X),Xs0) and we can eliminate them, like so:

onceMember_ofC(E,[X|Xs]) :-
   if_(E = X, maplist(dif(X),Xs),
              onceMember_ofC(E,Xs)).

Let's see if it works!

?- onceMember_ofC(X,[A,B,C]).
X = A, dif(A,C), dif(A,B) ;
X = B, dif(B,C), dif(B,A) ;
X = C, dif(C,B), dif(C,A) ;
false.