Prolog remove non-duplicates

Question

I've been trying to write some code that takes a list of values, and removes all values which are only in the list once, the non-duplicates:

dbltaker([], []).
dbltaker([H | X], Y):-
        \+mem(H, X),
    dbltaker(X, Y).
dbltaker([H | X], [H | Y]):-
    mem(H, X), !,
    dbltaker(X, Y).
dbltaker([H | X], [H | Y]):-
    mem(H, Y),
    dbltaker(X, Y).
mem(H, [H | _]).
mem(H, [_ | T]):-
    mem(H, T).

The trouble I've been having is that after I move a non-duplicate to the other list, it's duplicate is no longer a duplicate so isn't moved into the list. For example, the list [1, 1, 1, 2, 2, 3] gives [1, 1, 2] as the output, as the last one and two aren't considered duplicates as they're no longer members of their tails, and I can't check to see if they're members of the new list, as it's yet to be instantiated.

Is there a way around this?

Thanks.

Answer 1

I think the simpler way should be to should pass around to original list, to be able to check when an element is duplicate or not.

dbltaker(L, R) :- dbltaker(L, L, R).

dbltaker([], _L, []).
dbltaker([H|T], L, [H|R]) :- at_least_2(H, L), !, dbltaker(T, L, R).
dbltaker([_|T], L, R) :- dbltaker(T, L, R).

the service predicate at_least_2(H, L) can easily be implemented...

Answer 2

This is how I'd do it:

• First, a check for list membership:

  exists_in( A , [A|_] ) :- ! .
  exists_in( A , [_|B] ) :- exists_in(A,B) .
  

• Then a conditional add. If X is not contained in Y, add X to Y giving Z:

  add_if_not_exists( X , Z , Z     ) :-  exists(X,T) , ! .
  add_if_not_exists( X , Y , [X|Y] ) .
  

• A worker predicate that does the hard work, using an accumulator (seeded to the empty list []) to build the set of distinct elements:

  dedupe( []     , Z , Z ) .   % if the source list is exhausted, we're done: the accumulator is the set of distinct list members.
  dedupe( [X|Xs] , Y , Z ) :-  % otherwise...
    add_if_not_exists(X,Y,T) , % - add X to the accumulator if it's not already there.
    dedupe(Xs,T,Z)             % - and recurse down.
    .                          % Easy!
  

• And finally, the public interface predicate that simply invokes the worker predicate:

  dedupe( Xs, Ys ) :-     % dedupe a list
    dedupe( Xs, [] , Ys ) % by invoking the helper predicate with the accumulator seeded with the empty set.
    .                     %
  

  Note: the worker predicate builds the deduped list in reverse order. If order is important, reversing a list is trivial:

  rev( []     , [] ) .
  rev( [X|Xs] , Rs ) :- rev( Xs , [X|Rs] ) .
  

  Just modify the public interface to do the reversal:

  dedupe1( Xs, Ys ) :-     % dedupe a list
    dedupe( Xs, [] , T ) , % by invoking the helper predicate with the accumulator seeded to the empty set.
    rev(T,Ys)              % and reversing the result.
    .                      %