Prolog: Removing Duplicates

Question

I am trying to remove duplicate entries from a list in prolog. So a list [a,b,a,c,b,a] would return [a,b,c]. I can not use any built in functions. I searched here and found this code.

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

But that would take my list and return [c,b,a] not [a,b,c]

I have remove code that will take an element and a list and return a list with occurrences of that element in the list removed. So I tried to incorporate that into my remove duplicate method but I don't really understand prolog very well so it is not working. Logically I want to take a list cons the head with the recursive call on the new list minus all occurrences of the head. This is what the code would look like in sml.

fun remv(_,nil) = nil
|   remv(a,x::xs) = if x=a then remv(a,xs) else x::remv(a,xs);
fun remvdub (nil) = nil
|   remvdub(x::xs) = x::remvdub(remv(x,xs)); 

So this is what I tried in prolog

remv(_,[],[]).
remv(X,[X|T],Ans) :- remv(X,T,Ans).
remv(X,[H|T],[H|K]) :- remv(X,T,K). 

remvdub([],[]).
remvdub([H|T],[H|Ans]) :- remvdub(Ans1,Ans), remv(H,T,Ans1).

What am I missing?

Answer 1

% An empty list is a set.
set([], []).

% Put the head in the result,
% remove all occurrences of the head from the tail,
% make a set out of that.
set([H|T], [H|T1]) :- 
    remv(H, T, T2),
    set(T2, T1).

% Removing anything from an empty list yields an empty list.
remv(_, [], []).

% If the head is the element we want to remove,
% do not keep the head and
% remove the element from the tail to get the new list.
remv(X, [X|T], T1) :- remv(X, T, T1).

% If the head is NOT the element we want to remove,
% keep the head and
% remove the element from the tail to get the new tail.
remv(X, [H|T], [H|T1]) :-
    X \= H,
    remv(X, T, T1).

Answer 2

The snippet of Prolog code that you posted is logically correct. If you would like to keep the first, as opposed to the last, copy of each duplicated item, you can change your code as follows:

member(X,[X|_]) :- !.
member(X,[_|T]) :- member(X,T).
set(A,B) :- set(A, B, []).
set([],[],_).
set([H|T],[H|Out],Seen) :- not(member(H,Seen)), set(T,Out, [H|Seen]).
set([H|T],Out, Seen) :- member(H,Seen), set(T,Out,Seen).

The idea is to add a third parameter, which represents the list of items that you have seen so far, and check the membership against it, rather than checking the membership against the remaining list. Note that set/2 is added to hide this third argument from the users of your predicate.

Demo on ideone.