A predicate that selects items that are in the list twice, no less, no more

Question

I am trying to write a predicate twice(El,L) that will return true. when El will be displayed exactly twice. Here is what I have:

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

It works fine 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... X = 1 ; X = 1 ; X = 2... X = 1 ; X = 1 ; X = 2... How could I avoid this without using any battery?

Answer 1

You want to describe a sequence of elements. For this, there is a special formalism in the Prolog called Grimmar of a Specific Class. Before using formalism, try to figure out what the sequence with E looks exactly two times:

• Firstly, it is possibly an empty sequence that does not contain E
• i.e. one occurrence of E
• then again an empty sequence is possible without E
• that is, the second occurrence of E
• then again possibly an empty sequence without E

Now, to put this in 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, using all // 1 and avoiding auxiliary definitions:

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

Essentially, there is only one drawback of these definitions: in modern systems they are not optimally implemented. See this one if you want to know more.

Answer 2

Stay logically clean and efficient using if_/3 and (=)/3 @false. This happens as follows:

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

What is it. Run some queries!

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

Now something is 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. 

The following are the requests provided by OP:

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

Edit

Alternatively, use meta-predicate tcount/3 in combination with (=)/3 as follows:

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

Answer 3

Try:

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

Adding

If the list of numbers may be (partially) unrelated, the next option solves the problem. It uses "dif" instead of "\ =", "+". In addition, several optimized ones ("append" and "member" were combined with one "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 4

Here's how we can declare an aggregate library, the required restriction:

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

In cases where the list items are limited to integers, the library (clpfd) hint reification contains another solution:

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