Remove duplicates from a list while keeping the rightmost occurrences

Question

I am trying to remove duplicates from a list while keeping the rightmost occurrences. E.g.: [1,2,3,1,2] is transformed in [3,1,2] It's one of my first tries in Prolog and I don't understand what am I doing wrong. It always returns false. This is my code:

%nrap(L:list,E:element,S:integer)
%L - the initial list, list of integers
%E - the element, integer
%S - the result, nrap of E in L, S integer
%flow model: (i,i,o),(i,i,i)

nrap([],_,0).
nrap([H|T],E,S):-
    H=E,
    nrap(T,E,S1),
    S is S1+1.
nrap([H|T],E,S):-
    H\=E,
    nrap(T,E,S).

%transform(L:list,L2:list,R:list)
%L - the initial list, list of integers
%L2 - copy of the initial list
%R - the resulted list, without duplicates, list of integers
%flow model: (i,i,o),(i,i,i)

transform([],[],[]).
transform([H|T],L2,[H|R]):-
    nrap(L2,H,S),
    S=1,
    transform(T,L2,R).
transform([H|T],L2,R):-
    nrap(L2,H,S),
    S>1,
    transform(T,L2,R).

Answer 1

Shall I be pure or impure? Why even consider sacrificing logical-purity if we can save it easily!
Using memberd_t/3 and if_/3, we define list_rset/2 and its left "twin" list_lset/2:

list_rset([], []).                     % keep rightmost occurrences
list_rset([E|Es], Rs0) :-
   if_(memberd_t(E, Es),
       Rs0 = Rs,
       Rs0 = [E|Rs]),
   list_rset(Es, Rs).

list_lset([], []).                     % keep leftmost occurrences
list_lset([E|Es], Ls) :-
   post_pre_lset(Es, [E], Ls).         % uses internal auxilary predicate

post_pre_lset([], _, []).            
post_pre_lset([E|Es], Pre, Ls0) :-     % 2nd arg: look-behind accumulator
   if_(memberd_t(E, Pre),
       Ls0 = Ls,
       Ls0 = [E|Ls]),
   post_pre_lset(Es, [E|Pre], Ls).

Let's run some queries!

?- _Es = [1,2,3,1,2], list_lset(_Es, Ls), list_rset(_Es, Rs).
Ls = [1,2,3], Rs = [3,1,2].           % succeeds deterministically

In above query 1 precedes 2 both at the beginning and at the end of the list [1,2,3,1,2].
What if 1 precedes 2 at the beginning but follows it at the end (e.g., [1,2,3,2,1])?

?-  _Es = [1,2,3,2,1], list_lset(_Es, Ls), list_rset(_Es, Rs).
Ls = [1,2,3], Rs = [3,2,1].          % succeeds deterministically

Next, we look at a more general list_rset/2 goal that uses a list containing variables only.
Thanks to @PauloMoura for his suggestion!

?- Es = [A,B,C,A,B], list_rset(Es,Rs).
   Es = [C,C,C,C,C], Rs = [    C],     A=B ,               B=C
;  Es = [B,B,C,B,B], Rs = [C,  B],     A=B ,           dif(B,C)
;  Es = [C,B,C,C,B], Rs = [  C,B],               A=C , dif(B,C)
;  Es = [A,C,C,A,C], Rs = [  A,C],           dif(A,C),     B=C
;  Es = [A,B,C,A,B], Rs = [C,A,B], dif(A,B), dif(A,C), dif(B,C).

What's up with the residual goals (above)? Without sufficient instantiation, dif/2 is not decidable.
To save logical soundness, the execution of the prolog-dif constraints is delayed.

Last, one more use-case: an "input" list Xs that has both variables and ground terms.

?- Es = [A,B,z], list_rset(Es,Rs).
   Es = [z,z,z], Rs = [    z],     A=B ,               B=z 
;  Es = [B,B,z], Rs = [B,  z],     A=B ,           dif(B,z)
;  Es = [z,B,z], Rs = [  B,z],               A=z , dif(B,z)
;  Es = [A,z,z], Rs = [A,  z],           dif(A,z),     B=z 
;  Es = [A,B,z], Rs = [A,B,z], dif(A,B), dif(A,z), dif(B,z).

Answer 2

This is a follow-up to this previous answer... In this answer we use dcg!

We build lset//1 upon memberd_t/3 and if_//3—the dcg analogue of if_/3:

lset([]) -->
   [].
lset([X|Xs]) -->
   [X],
   lset_pre(Xs,[X]).

lset_pre([],_) -->
   [].
lset_pre([X|Xs],Pre) -->
   if_(memberd_t(X,Pre), [], [X]),
   lset_pre(Xs,[X|Pre]).

Same for rset//1:

rset([]) -->
   [].
rset([X|Xs]) -->
   if_(memberd_t(X,Xs), [], [X]),
   rset(Xs).

Some sample queries:

?- _Es = [1,2,3,1,2], phrase(lset(_Es),Ls), phrase(rset(_Es),Rs).
Ls = [1,2,3], Rs = [3,1,2].               % succeeds deterministically

?- _Es = [1,2,3,2,1], phrase(lset(_Es),Ls), phrase(rset(_Es),Rs).
Ls = [1,2,3], Rs = [3,2,1].               % succeeds deterministically

Answer 3

This is easier than you are making it. Since the elements in the "set" have to be in the order of last appearance, you don't need to keep a copy of the list at all: just compare to the remainder of the list (the tail).

If you know that the first list is always going to be ground (all elements are integers, for example), you could write:

list_set([], []).
list_set([X|Xs], Ys0) :-
    (   memberchk(X, Xs)
    ->  Ys0 = Ys
    ;   Ys0 = [X|Ys]
    ),
    list_set(Xs, Ys).

memberchk/2 can be used to check if a ground term is in a list of ground terms. It will succeed or fail exactly once.

A more general solution is to pose a constraint that an element should be in the set if it is different from all the elements following it, and be dropped otherwise:

list_set([], []).
list_set([X|Xs], [X|Ys]) :-
    maplist(dif(X), Xs),
    list_set(Xs, Ys).
list_set([X|Xs], Ys) :-
    \+ maplist(dif(X), Xs),
    list_set(Xs, Ys).

Here, maplist(dif(X), Xs) means:

X is different from every element in the list Xs (the tail).

and \+ Goal succeeds then Goal does not succeed.

With this defintion:

?- list_set([1,2,3,1,2], S).
S = [3, 1, 2] ;
false.

?- list_set([1,2,3,3,1,1,2], S).
S = [3, 1, 2] ;
false.

?- list_set([A,B,C,A,B],Xs).
Xs = [C, A, B],
dif(A, B),
dif(C, B),
dif(C, A) ;
false.