Predicate that pick elements which are on list twice not less not more

Question

I'm trying to write a predicate twice(El,L) which will return true. when El is on list exactly twice. Here is what I have:

twice(El,L) :- select(El,L,L1), member(El,L1), \+ twice(El,L1).

It works nice for twice(2,[1,2,2,3,4]) but for twice(X,[1,1,2,2,3,3]) it doubles every number X = 1 ; X = 1 ; X = 2... How could I avoid this without using any accumulator?

Answer 1

You want to describe a sequence of elements. For such, there is a special formalism in Prolog called Definite Clause Grammars. Before using the formalism, let's try to figure out how a sequence with E occurring exactly twice looks like:

1. First, is a possibly empty sequence which does not contain E
2. then, there is one occurrence of E
3. then again a possibly empty sequence without E
4. then, there is the second occurrence of E
5. then again a possibly empty sequence without E.

Now, to put this into the DCG formalism

twice(E, L) :-
   phrase(twice_occurring(E), L).  % Interface

twice_occurring(E) -->
   seq_without(E),    % 1.
   [E],               % 2.
   seq_without(E),    % 3.
   [E],               % 4.
   seq_without(E).    % 5.

seq_without(_E) -->
   [].
seq_without(E) -->
   [X],
   {dif(X,E)},
   seq_without(E).

Or, more compactly by using all//1 and avoiding auxiliary definitions:

twice(E, L) :-
    phrase(( all(dif(E)), [E], all(dif(E)), [E], all(dif(E)) ), L).

There is essentially only one drawback with these definitions: On current systems, they are not optimally implemented. See this if you want to know more.

Answer 2

Stay both logically pure and efficient by using if_/3 and (=)/3 by @false. It goes like this:

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

list_member2x([X|Xs],E) :-
   if_(X=E, list_member1x(Xs,E), list_member2x(Xs,E)).

twice(E,Xs) :-
   list_member2x(Xs,E).

That's it. Let's run some queries!

?- twice(E,[1,2,3,4,5,2,3,4]).
E = 2 ;
E = 3 ;
E = 4 ;
false.

Now something a little more general:

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

Here are the queries the OP gave:

?- twice(2,[1,2,2,3,4]).
true.

?- twice(E,[1,1,2,2,3,3]).
E = 1 ;
E = 2 ;
E = 3 ;
false.

Edit

As an alternative, use meta-predicate tcount/3 in combination with (=)/3 like this:

twice(E,Xs) :- tcount(=(E),Xs,2).