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.

I suspect you are getting more than one answer. At least, you have three times the six.... — false, Feb 23 '14 at 17:16
I'm not sure I understand what you mean… The three 6's aren't the same thing. To put it into context I'm looking at tuples so for example the above could be [[a,6],[b,6],[c,6]]. I would like to remove all tuples whose last element is unique. — jalog3343646, Feb 23 '14 at 17:25
For `remUniqueVals([6,6,6],Q)`, there will be two answers for `member(E, [6,6])` - but you do not report them. — false, Feb 23 '14 at 17:30
I think my problem is not that they aren't reported it's that there are only two answers. So it checks member(6,[6,6]). (Unifies Q = [6]) Then checks member(6,[6]). (Q = [6,6]) Then checks member(6,[]). This fails and so returns Q = [6,6]. This is my problem. I would like to return Q = [6,6,6] but am not sure how to go about doing this using this approach. — jalog3343646, Feb 23 '14 at 17:44
Do you require that the original order of the remaining elements be maintained? — lurker, Feb 24 '14 at 02:29
What is the meaning of the first argument of your new remUniqueVals/3? — false, Feb 25 '14 at 17:38
The first argument is used to store the value of the number that came before it. I initialise it with 0 as in my problem 0 will never be in the set of numbers I'm looking to remove uniques from — jalog3343646, Feb 25 '14 at 17:47
In fact I don't believe it matters what it is initialised with. — jalog3343646, Feb 25 '14 at 17:57
@jalog3343646: In any case, your cuts are all malplaced, setting a cut after a recursive goal is practically never useful. — false, Feb 25 '14 at 18:28

false · Answer 1 · 2022-08-19T19:06:13.043

Prolog rules are read independently of each other, so you need one rule for the case where the element is unique and one where it is not. Provided the order of the elements is not relevant, you might use:

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

?- remUniqueVals([1,1,2,2,3,4,4,5,6,6,6],Q).
   Q = [1,1,2,2,4,4,6,6,6]
;  false.

remUniqueVals([], []).
remUniqueVals([Q1|RestQ],[Q1|Xs0]) :-
   memberd(Q1, RestQ),
   phrase(delall(Q1, RestQ, NewQ), Xs0, Xs),
   remUniqueVals(NewQ, Xs).
remUniqueVals([Q1|RestQ],Xs) :-
   maplist(dif(Q1), RestQ),
   remUniqueVals(RestQ,Xs).

memberd(X, [X|_Xs]).
memberd(X, [Y|Xs]) :-
   dif(X,Y),
   memberd(X, Xs).

delall(_X, [], []) --> [].
delall(X, [X|Xs], Ys) -->
   [X],
   delall(X, Xs, Ys).
delall(X, [Y|Xs], [Y|Ys]) -->
   {dif(X,Y)},
   delall(X, Xs, Ys).

Here is an alternate definition for memberd/2 which might be more efficient using if_/3:

memberd(E, [X|Xs]) :-
   if_(E = X, true, memberd(E, Xs) ).

Ok thanks! Looks like it might do the trick I'll take some time to look over and understand it all first. — jalog3343646, Feb 23 '14 at 18:01

lurker · Accepted Answer · 2014-02-24T13:01:34.053

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

score 5 · Answer 3 · edited May 23 '17 at 12:16

This is another pure, relational solution inspired by @CapelliC's solution. This one now retains the order of the duplicates. What is interesting to see is how the implicit quantification happening in @CapelliC's solution now has to be done explicitly.

The biggest advantage of having a pure, relational definition is that noes are noes. And ayes are ayes. That is: You do not have to worry whether or not the answer you get happens to be correct or not. It is correct (or incorrect — but it is not partially correct). Non-relational solutions can often be cleansed by producing instantiation_error in case the method fails. But as you can verify yourself, both have "forgotten" such tests thereby preparing a nice habitat for bugs. A safe test for those other solutions would have been ground(Xs) or ground(Xs), acyclic_term(Xs) but much too often this is considered too restricted.

remUniqueVals2(Xs, Ys) :-
   tfilter(list_withduplicate_truth(Xs),Xs,Ys).

list_withduplicate_truth(L, E, Truth) :-
   phrase(
      (  all(dif(E)),
         (  {Truth = false}
         |  [E],
            all(dif(E)),
            (   {Truth = false}
            |   {Truth = true},
                [E],
                ...
            )
         )
      ),  L).

all(_) --> [].
all(P_1) -->
   [E],
   {call(P_1,E)},
   all(P_1).

... --> [] | [_], ... .

tfilter(     _, [], []).
tfilter(TFilter_2, [E|Es], Fs0) :-
   call(TFilter_2,E,Truth),
   (  Truth = false,
      Fs0 = Fs
   ;  Truth = true,
      Fs0 = [E|Fs]
   ),
   tfilter(TFilter_2, Es, Fs).

Another, more compact way using if_/3

tfilter(   _, [], []).
tfilter(TFilter_2, [E|Es], Fs0) :-
   if_(call(TFilter_2,E), Fs0 = [E|Fs], Fs0 = Fs ),
   tfilter(TFilter_2, Es, Fs).

Thanks for this (+1). This is an innocent enough sounding predicate, but seems particularly challenging for a pure, relational solution. — lurker, Feb 24 '14 at 19:47
@mbratch: What about purifying your approach? (Make a new, separate answer). — false, Feb 24 '14 at 20:22
I've been looking at it in little bits and pieces of time I can spend on it. After fooling with a couple of failed notions, it seems pretty challenging at the moment... :) — lurker, Feb 24 '14 at 20:28

false · Answer 4 · 2022-08-19T19:02:04.390

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.

score 3 · Answer 5 · edited May 23 '17 at 11:58

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

edited May 23 '17 at 11:58

Community

1
1

answered May 26 '15 at 08:27

repeat

18,496
4
54
166

2

could you perhaps edit the logical-purity tag info with the explanation of what this "logical purity" means, because, as it is written right now (*"programs using only Horn clauses"*) I don't see how `if_/3` qualifies, using as much as it is the cut, and the various meta-logical (what's the proper terminology? `var/1` and such) predicates, i.e. the low-level stuff. I get it that it achieves some "pure" effect, I'd just like to see it explicated so I (and presumably others) don't have to guess. Would appreciate it very much. -- So, how does `if_/3` qualify as logically pure? – Will Ness Aug 10 '15 at 19:09
2

@WillNess: It would be best if you ask a question about this. – false Aug 11 '15 at 10:59

score 2 · Answer 6 · edited Feb 24 '14 at 00:20

2

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

edited Feb 24 '14 at 00:20

false

10,264
13
101
209

answered Feb 23 '14 at 22:25

CapelliC

59,646
5
47
90

2

Nice, but non-relational. E.g., fails for `remUniqueValsCC([A,B],[]).` – false Feb 24 '14 at 00:13

Prolog removing unique elements only

6 Answers6

Linked

Related