Prolog remove non-duplicates

342 views Asked by At

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.

2

There are 2 answers

0
CapelliC On

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

0
Nicholas Carey On

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