Reverse List without duplicates ( convert it into Set ) -> Prolog-CodePudding

I need to delete all duplicates from a list and then show it in reverse order.

So far I have this:

reverseInSet([], Y,R):-
 R=Y.

reverseInSet([H|T], Y, R):- 
 removeElement(H,T,T1), 
 reverseInSet(T1, [H|Y], R).


removeElement(_,[],[]).    

removeElement(X,[X|T],L):-    
 removeElement(X,T,L).

removeElement(X,[Y|T],L):-   
 removeElement(X,T,L1),
 L=[Y|L1].

And the output is this:

reverseInSet([1,2,3,3,9,3],[],P).
P = [9, 3, 2, 1]
P = [3, 9, 3, 2, 1]
P = [9, 3, 3, 2, 1]
P = [9, 3, 3, 2, 1]
P = [3, 9, 3, 3, 2, 1]

Any ideas?

CodePudding user response：

Using reif library, to be both pure and reasonably deterministic:

:- use_module(library(reif)).

reverse_without_duplicates(Lst, LstRevDeDup) :-
    reverse_without_duplicates_(Lst, [], LstRevDeDup).


reverse_without_duplicates_([], Lst, Lst).

reverse_without_duplicates_([H|T], Upto, LstRevDeDup) :-
    list_elem_matches(T, H, Bool),
    reverse_without_duplicates_bool_(Bool, T, H, Upto, LstRevDeDup).

reverse_without_duplicates_bool_(true, T, _H, Upto, LstRevDeDup) :-
    reverse_without_duplicates_(T, Upto, LstRevDeDup).
reverse_without_duplicates_bool_(false, T, H, Upto, LstRevDeDup) :-
    % Include head
    reverse_without_duplicates_(T, [H|Upto], LstRevDeDup).


list_elem_matches([], _Elem, false).
list_elem_matches([H|T], Elem, Bool) :-
    % From reif library
    =(H, Elem, BoolHead),
    list_elem_matches_bool_(BoolHead, T, H, Elem, Bool).

list_elem_matches_bool_(false, T, _H, Elem, Bool) :-
    % No match found so far
    list_elem_matches(T, Elem, Bool).
list_elem_matches_bool_(true, _T, _H, _Elem, true).

Result in swi-prolog:

?- time(reverse_without_duplicates([1, 2, 3, 3, 9, 3], X)).
% 68 inferences, 0.000 CPU in 0.000 seconds (89% CPU, 1189497 Lips)
X = [3,9,2,1].

CodePudding user response：

This is about the simplest way to do it. In the case of duplicate entries in the source list, the last such entry is kept and the ones preceding it are discarded.

list_to_set_reverse( Xs, Ys ) :- list_to_set( Xs, Zs ) , reverse(Zs,Ys) .

list_to_set( []     , []     ) .
list_to_set( [X|Xs] , Ys     ) :- member(X,Xs), !, list_to_set(Xs,Ys) .
list_to_set( [X|Xs] , [X|Ys] ) :-                  list_to_set(Xs,Ys) .

You could also do it in a single pass, too. You just need to use an accumulator to build the result list in reverse order:

list_to_set_reverse( Xs, Ys ) :- list_to_set( Xs, [], Ys ) .

list_to_set( []     , Ys , Ys ) .
list_to_set( [X|Xs] , Ts , Ys ) :- member(X,Xs), !, list_to_set(Xs,Ts,Ys) .
list_to_set( [X|Xs] , Ts , Ys ) :-                  list_to_set(Xs,[X|Ts],Ys) .