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

Try:

twice(E,L) :- 
    append(B1,[E|A1],L), 
    \+ member(E,B1), 
    append(B2,[E|A2],A1), 
    \+ member(E,B2), 
    \+ member(E,A2).

Addendum

In case that the list of number could be (partially) unbound, following variant solves the issues. It uses "dif" instead of "\=", "+". In addition, it is a few optimized ("append" and "member" have been joined to a single "appendchk"):

appendchk(L,L).
appendchk([E|Q2],[H|R]) :-
    dif(H,E),
    appendchk([E|Q2],R).

notmember(_,[]).
notmember(X,[H|Q]) :-
    dif(X,H),
    notmember(X,Q).

twice(E,L) :- 
    appendchk([E|A1],L), 
    appendchk([E|A2],A1), 
    notmember(E,A2).

Examples:

twice(1,[1,2,3,4,2,3,2]).
false

twice(2,[1,2,3,4,2,3,2]).
false

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

twice(X,[1,2,3,4,2,3,2]).
X = 3
false

twice(X,[A,B]).
A = B, B = X

twice(X,[A,B,C]).
A = B, B = X,
dif(X, C)
A = C, C = X,
dif(B, X)
B = C, C = X,
dif(A, X)

Answer 3

Here is how we can declare, courtesy library(aggregate), the required constraint:

twice(El, L) :-
    aggregate(count, P^nth1(P,L,El), 2).

Where list' elements are restricted to integers, library(clpfd) reification hint hosts another solution:

twice(El, L) :- vs_n_num(L,El,2).
    % aggregate(count, P^nth1(P,L,El), 2).

Answer 4

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).