Prolog removing unique elements only

Question

I want to return a list that removes all unique elements for example

remUniqueVals([1,1,2,2,3,4,4,5,6,6,6],Q).   
Q = [1,1,2,2,4,4,6,6,6].  

My problem is that currently I have code that returns

remUniqueVals([1,1,2,2,3,4,4,5,6,6,6],Q).  
Q = [1, 2, 4, 6, 6].

So that only the first instance of these non-unique values are returned. Here is my code:

remUniqueVals([], []).  
remUniqueVals([Q1|RestQ],[Q1|Xs]) :-        
   member(Q1,RestQ),  
   remUniqueVals(RestQ,Xs).  
remUniqueVals([Q1|RestQ],Xs) :-  
   remove(Q1,[Q1|RestQ], NewQ),  
   remUniqueVals(NewQ,Xs).  

I can see that member(Q1,RestQ) fails when it checks 1,2,4 the second time because they are now no longer in the list and so removes them. I'd like some helping solving this problem, my thoughts are to check member(Q1, PreviousQ), where this is the elements already in the final Q. Not sure how to go about implementing that though any help would be appreciated.

Update:

Ok so thanks for the suggestions I ended up going with this in the end:

remUniqueVals(_,[], []).  
remUniqueVals(_,[Q1|RestQ],[Q1|Xs]) :-        
   member(Q1,RestQ), 
   remUniqueVals(Q1,RestQ,Xs).  
remUniqueVals(PrevQ,[Q1|RestQ],[Q1|Xs]) :-        
   Q1 = PrevQ, 
   remUniqueVals(PrevQ,RestQ,Xs).  
remUniqueVals(PrevQ,[_|RestQ],Xs) :-  
   remUniqueVals(PrevQ,RestQ,Xs). 

remUniqueVals(0,[4,1,1,3,2,2,5,5],Q).
Q = [1, 1, 2, 2, 5, 5].

remUniqueVals(0, [A,B,C], [1,1]).
A = 1,
B = 1,
C = 1.

Answer 1

This is a purified version of @mbratch's solution. It uses a reïfied version of member/2 which is free of redundant answers like for member(X,[a,a]).

memberd_truth_dcg(X, Xs, Truth) :-
   phrase(( all(dif(X)), ( [X], {Truth = true}, ... | {Truth = false} ) ), Xs).

A slightly generalized version which only requires to have a list prefix, but not a list:

memberd_truth(_X, [], false).
memberd_truth(X, [X|_], true).
memberd_truth(X, [Y|Ys], Truth) :-
   dif(X,Y),
   memberd_truth(X, Ys, Truth).

The variables are named in the same manner as in @mbratch's solution:

remove_uniq_valsBR(L, R) :-
   remove_uniq_valsBR(L, [], R).

remove_uniq_valsBR([], _, []).
remove_uniq_valsBR([X|T], A, R) :-
    memberd_truth(X, A, MemT1),
    (  MemT1 = true,
       R = [X|T1], A1 = A
    ;  MemT1 = false,
       memberd_truth(X, T, MemT2),
       (  MemT2 = true,
          R = [X|T1], A1 = [X|A]
       ;  MemT2 = false,
          R = T1, A1 = A
       )
    ),
    remove_uniq_valsBR(T, A1, T1).

More compactly using if/3:

remove_uniq_valsBR([], _, []).
remove_uniq_valsBR([X|T], A, R) :-
    if_( memberd_truth(X, A),
       ( R = [X|T1], A1 = A ),
       if_( memberd_truth(X, T),
          ( R = [X|T1], A1 = [X|A] ),
          ( R = T1, A1 = A ) ) )
    ),
    remove_uniq_valsBR(T, A1, T1).

What I do not like is the many redundant dif/2 constraints. I hoped this version would have less of them:

?- length(L,_),remove_uniq_valsBR(L,L).
   L = []
;  L = [_A,_A]
;  L = [_A,_A,_A]
;  L = [_A,_A,_A,_A]
;  L = [_A,_A,_B,_B], dif(_B,_A)
;  L = [_A,_B,_A,_B],
   dif(_A,_B), dif(_B,_A), dif(_B,_A), dif(_A,_B)
;  ... .

Of course it is possible to check whether or not a dif/2 is already present, but I'd prefer a version where there are fewer dif/2 goals posted right from the beginning.

Answer 2

This is similar to the original solution but it collects the non-unique values in an auxiliary list and checks it to avoid removing the last one from the original:

remove_uniq_vals(L, R) :-
    remove_uniq_vals(L, [], R).

remove_uniq_vals([], _, []).
remove_uniq_vals([X|T], A, R) :-
    (   member(X, A)
    ->  R = [X|T1], A1 = A
    ;   member(X, T)
    ->  R = [X|T1], A1 = [X|A]
    ;   R = T1, A1 = A
    ),
    remove_uniq_vals(T, A1, T1).

Testing...

| ?- remove_uniq_vals([1,2,3,1,2,3,1,2,3,4,3], Q).

Q = [1,2,3,1,2,3,1,2,3,3]

(1 ms) yes
| ?- remove_uniq_vals([1,1,2,2,3,4,4,5,6,6,6], Q).

Q = [1,1,2,2,4,4,6,6,6]

yes

So the predicate works great if the first argument is an input, and it maintains the original order of the remaining elements in the list.

However, this predicate is not completely relational in that it will fail a case in which the first argument is an uninstantiated list of a known number of elements and the second argument is a list of a different fixed number of elements. So something like this will work:

| ?- remove_uniq_vals([A,B,C], L).

B = A
C = A
L = [A,A,A]

(1 ms) yes

But something like the following fails:

| ?- remove_uniq_vals([A,B,C], [1,1]).

no

Answer 3

Preserve logical-purity! Based on if_/3, (=)/3, and meta-predicate tpartition/4 we define:

remUniqueValues([], []).
remUniqueValues([X|Xs1], Ys1) :-
   tpartition(=(X), Xs1, Eqs, Xs0),
   if_(Eqs = [],
       Ys1 = Ys0,
       append([X|Eqs], Ys0, Ys1)),
   remUniqueValues(Xs0, Ys0).

Let's see it in action!

?- remUniqueValues([A,B,C], [1,1]).
       A=1 ,     B=1 , dif(C,1)
;      A=1 , dif(B,1),     C=1
;  dif(A,1),     B=1 ,     C=1
;  false.

?- remUniqueValues([1,1,2,2,3,4,4,5,6,6,6], Vs).
Vs = [1,1,2,2,4,4,6,6,6].                   % succeeds deterministically

Answer 4

a solution based on 3 builtins:

remUniqueVals(Es, NUs) :-
    findall(E, (select(E, Es, R), memberchk(E, R)), NUs).

can be read as

find all elements that still appear in list after have been selected