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?

it can perhaps be easier if you write another predicate `counts(List,Counts)` that will be true if `Counts` is a list of pairs `[Element,Count]` for each element of `List`. i.e. `counts([1,1,2,5,33,5,1,1,5,1,5,1],[[1,6],[2,1],[5,4],[33,1]])`. then `twice(Elem,List) :- member([Elem,2],List).` — fferri, Jun 08 '15 at 15:02
see here on counting occurrences in a list: http://stackoverflow.com/questions/9088062/count-the-number-of-occurrences-of-a-number-in-a-list — fferri, Jun 08 '15 at 15:14

score 5 · Accepted Answer · edited May 23 '17 at 12:31

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:

First, is a possibly empty sequence which does not contain E
then, there is one occurrence of E
then again a possibly empty sequence without E
then, there is the second occurrence of E
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.

@CapelliC: Use [`tcount(=(E), L, 2)`](http://stackoverflow.com/a/29960878/4609915) for brevity. — false, Jun 10 '15 at 12:03

score 4 · Answer 2 · edited May 23 '17 at 12:24

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

pasaba por aqui · Answer 3 · 2015-06-09T13:25:02.970

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)

edited Jun 09 '15 at 13:25

answered Jun 08 '15 at 17:40

pasaba por aqui

3,446
16
40

2

`twice(E,[A,B])` correctly succeeds with `A = B`. But `twice(E,[A,B,C])` fails. – false Jun 08 '15 at 19:06
`s(X)` for the nice & pure addendum! Pure code like that is much easier to debug: Simply look at the answers you got. – false Jun 10 '15 at 11:22
BTW, what Prolog do you use? I suspect SWI, but somehow you removed all the `;` and `.` from SWI's answers. They are here to insist that you can re-enter them! – false Jun 10 '15 at 11:22
@false: when I've made this test, I'd only a small tablet without any prolog, so I used "swish" at internet. In this GUI, some of the usual symbols are not present or lost at copy&paste; I do not understand the "s(X)" meaning. – pasaba por aqui Jun 10 '15 at 14:37
`s(X)` means: successor of `X`. Other languages call this `+1`. – false Jun 10 '15 at 14:42

CapelliC · Answer 4 · 2015-06-10T09:47:09.000

1

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

edited Jun 10 '15 at 09:47

answered Jun 10 '15 at 08:32

CapelliC

59,646
5
47
90

Your first definition fails for `twice(e,[e,X])` but succeeds for `X=e, twice(e,[e,X])`. So whatever this aggregate provides, is not a pure relation. – false Jun 10 '15 at 11:28
Your second definition is very weak: `vs_n_num([X,Y,Y],X,2).` succeeds with an inconsistency, while it could simply and quickly fail. In general, `library(clpfd)` is not very strong for equality and inequality. – false Jun 10 '15 at 11:33

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

4 Answers4

Edit