Remove duplicates in list (Prolog)

Question

I am completely new to Prolog and trying some exercises. One of them is:

Write a predicate set(InList,OutList) which takes as input an arbitrary list, and returns a list in which each element of the input list appears only once.

Here is my solution:

member(X,[X|_]).
member(X,[_|T]) :- member(X,T).

set([],[]).
set([H|T],[H|Out]) :-
    not(member(H,T)),
    set(T,Out).
set([H|T],Out) :-
    member(H,T),
    set(T,Out).

I'm not allowed to use any of built-in predicates (It would be better even do not use not/1). The problem is, that set/2 gives multiple same solutions. The more repetitions in the input list, the more solutions will result. What am I doing wrong? Thanks in advance.

Answer 1

You are getting multiple solutions due to Prolog's backtracking. Technically, each solution provided is correct, which is why it is being generated. If you want just one solution to be generated, you are going to have to stop backtracking at some point. This is what the Prolog cut is used for. You might find that reading up on that will help you with this problem.

Update: Right. Your member() predicate is evaluating as true in several different ways if the first variable is in multiple positions in the second variable.

I've used the name mymember() for this predicate, so as not to conflict with GNU Prolog's builtin member() predicate. My knowledge base now looks like this:

mymember(X,[X|_]).
mymember(X,[_|T]) :- mymember(X,T).

not(A) :- \+ call(A).

set([],[]).
set([H|T],[H|Out]) :-
    not(mymember(H,T)),
    set(T,Out).
set([H|T],Out) :-
    mymember(H,T),
    set(T,Out).

So, mymember(1, [1, 1, 1]). evaluates as true in three different ways:

| ?- mymember(1, [1, 1, 1]).

true ? a

true

true

no

If you want to have only one answer, you're going to have to use a cut. Changing the first definition of mymember() to this:

mymember(X,[X|_]) :- !.

Solves your problem.

Furthermore, you can avoid not() altogether, if you wish, by defining a notamember() predicate yourself. The choice is yours.

Answer 2

You are on the right track... Stay pure---it's easy!

Use reified equality predicates =/3 and dif/3 in combination with if_/3, as implemented in Prolog union for A U B U C:

=(X, Y, R) :- X == Y,    !, R = true.
=(X, Y, R) :- ?=(X, Y),  !, R = false. % syntactically different
=(X, Y, R) :- X \= Y,    !, R = false. % semantically different
=(X, Y, R) :- R == true, !, X = Y.
=(X, X, true).
=(X, Y, false) :-
   dif(X, Y).

% dif/3 is defined like (=)/3
dif(X, Y, R) :- X == Y,    !, R = false.
dif(X, Y, R) :- ?=(X, Y),  !, R = true. % syntactically different
dif(X, Y, R) :- X \= Y,    !, R = true. % semantically different
dif(X, Y, R) :- R == true, !, X \= Y.
dif(X, Y, true) :-         % succeed first!
   dif(X, Y).
dif(X, X, false).

if_(C_1, Then_0, Else_0) :-
   call(C_1, Truth),
   functor(Truth,_,0),  % safety check
   ( Truth == true -> Then_0 ; Truth == false, Else_0 ).

Based on these predicates we build a reified membership predicate list_item_isMember/3. It is semantically equivalent with memberd_truth/3 by @false. We rearrange the argument order so the list is the 1st argument. This enables first-argument indexing which prevents leaving useless choice-points behind as memberd_truth/3 would create.

list_item_isMember([],_,false).
list_item_isMember([X|Xs],E,Truth) :-
   if_(E = X, Truth = true, list_item_isMember(Xs,E,Truth)).

list_set([],[]).
list_set([X|Xs],Ys) :-
    if_(list_item_isMember(Xs,X), Ys = Ys0, Ys = [X|Ys0]),
    list_set(Xs,Ys0).

A simple query shows that all redundant answers have been eliminated and that the goal succeeds without leaving any choice-points behind:

?- list_set([1,2,3,4,1,2,3,4,1,2,3,1,2,1],Xs).
Xs = [4,3,2,1].                         % succeeds deterministically

---

Edit 2015-04-23

I was inspired by @Ludwig's answer of set/2, which goes like this:

set([],[]).
set([H|T],[H|T1]) :- subtract(T,[H],T2), set(T2,T1).

SWI-Prolog's builtin predicate subtract/3 can be non-monotone, which may restrict its use. list_item_subtracted/3 is a monotone variant of it:

list_item_subtracted([],_,[]).
list_item_subtracted([A|As],E,Bs1) :-
    if_(dif(A,E), Bs1 = [A|Bs], Bs = Bs1),
    list_item_subtracted(As,E,Bs).

list_setB/2 is like set/2, but is based on list_item_subtracted/3---not subtract/3:

list_setB([],[]).
list_setB([X|Xs1],[X|Ys]) :-
    list_item_subtracted(Xs1,X,Xs),
    list_setB(Xs,Ys).

The following queries compare list_set/2 and list_setB/2:

?- list_set([1,2,3,4,1,2,3,4,1,2,3,1,2,1], Xs).
Xs = [4,3,2,1].                          % succeeds deterministically
?- list_setB([1,2,3,4,1,2,3,4,1,2,3,1,2,1],Xs).
Xs = [1,2,3,4].                          % succeeds deterministically

?- list_set(Xs,[a,b]).
   Xs = [a,b]
;  Xs = [a,b,b]
;  Xs = [a,b,b,b] 
...                                      % does not terminate universally
?- list_setB(Xs,[a,b]).
   Xs = [a,b]
;  Xs = [a,b,b]
;  Xs = [a,b,b,b]
...                                      % does not terminate universally

Answer 3

A simpler (and likely faster) solution is to use library predicate sort/2 which remove duplicates in O(n log n). Definitely works in Yap prolog and SWIPL

Answer 4

I think that a better way to do this would be:

set([], []).
set([H|T], [H|T1]) :- subtract(T, [H], T2), set(T2, T1).

So, for example ?- set([1,4,1,1,3,4],S) give you as output:

S = [1, 4, 3]

Answer 5

Adding my answer to this old thread:

notmember(_,[]).
notmember(X,[H|T]):-X\=H,notmember(X,T).

set([],[]).
set([H|T],S):-set(T,S),member(H,S).
set([H|T],[H|S]):-set(T,S),not(member(H,S)).

The only virtue of this solution is that it uses only those predicates that have been introduced by the point where this exercise appears in the original text.

Answer 6

You just have to stop the backtracking of Prolog.

enter code here
member(X,[X|_]):- !.
member(X,[_|T]) :- member(X,T).

set([],[]).
set([H|T],[H|Out]) :-
   not(member(H,T)),
   !,
set(T,Out).
set([H|T],Out) :-
   member(H,T),
   set(T,Out).

Answer 7

Using the support function mymember of Tim, you can do this if the order of elements in the set isn't important:

mymember(X,[X|_]).
mymember(X,[_|T]) :- mymember(X,T).

mkset([],[]).
mkset([T|C], S) :- mymember(T,C),!, mkset(C,S).
mkset([T|C], S) :- mkset(C,Z), S=[T|Z].

So, for example ?- mkset([1,4,1,1,3,4],S) give you as output:

S = [1, 3, 4]

but, if you want a set with the elements ordered like in the list you can use:

mkset2([],[], _).
mkset2([T|C], S, D) :- mkset2(C,Z,[T|D]), ((mymember(T,D), S=Z,!) ; S=[T|Z]).
mkset(L, S) :- mkset2(L,S,[]).

This solution, with the same input of the previous example, give to you:

S = [1, 4, 3]

This time the elements are in the same order as they appear in the input list.

Answer 8

/* Remove duplicates from a list without accumulator */
our_member(A,[A|Rest]).
our_member(A, [_|Rest]):-
    our_member(A, Rest).

remove_dup([],[]):-!.
remove_dup([X|Rest],L):-
    our_member(X,Rest),!,
    remove_dup(Rest,L).
remove_dup([X|Rest],[X|L]):-
    remove_dup(Rest,L).

Answer 9

This works without cut, but it needs more lines and another argument. If I change the [H2|T2] to S on line three, it will produce multiple results. I don't understand why.

setb([],[],_).
setb([H|T],[H|T2],A) :- not(member(H,A)),setb(T,T2,[H|A]).
setb([H|T],[H2|T2],A) :- member(H,A),setb(T,[H2|T2],A).
setb([H|T],[],A) :- member(H,A),setb(T,[],A).
set(L,S) :- setb(L,S,[]).