0

I have written some code that removes all duplicates from a list, so that remove_duplicates([1,2,3,4,5,3,4,5], L). gets L = [1, 2, 3, 4, 5].

member1(X,[H|_]) :- 
    X==H,!.
member1(X,[_|T]) :- 
    member1(X,T).

remove_duplicates([],[]).       
remove_duplicates([H|T],X) :- 
    member1(H,T),                
    !,                          
    remove_duplicates(T,X).     

remove_duplicates([H|T],[H|X]) :- 
    remove_duplicates(T,X).

What I want to do is remove the duplicate and remove the original so that remove_duplicates([1,2,3,4,5,3,4,5], L). gets L = [1, 2]. where 3, 4 and, 5 would be removed.

JaAnTr
  • 896
  • 3
  • 16
  • 28

3 Answers3

1

Here is a way to remove_duplicates, but it's not tail recursive.

remove_duplicates([],[]).

remove_duplicates([H|T], X) :-
    remove_duplicates(T,X1),
    (   member(H, X1)
    ->  select(H, X1, X)
    ;   X = [H |X1]).

Yes, my first code est incorrect, because I don't memorise dups. Here is a correct solution :

remove_duplicates(In, Out) :-
    remove_duplicates(In, _, Out).

remove_duplicates([],[], []).

remove_duplicates([H|T], Dup, X) :-
    remove_duplicates(T,Dup1, X1),
    (   member(H, Dup1)
    ->  X = X1,
    Dup = Dup1
    ;   (   member(H, X1)
    ->  select(H, X1, X),
        Dup = [H | Dup1]
    ;   X = [H | X1],
        Dup = Dup1)).

And we get 

 ?- remove_duplicates([1,2,3,2,1,2,3,4,5], L).
L = [4, 5] ;
false.
joel76
  • 5,565
  • 1
  • 18
  • 22
  • That doesn't work for me, `remove_duplicates([1,2,3,4,5,3,4,5], L).` gets `L = [1, 2, 3, 4, 5].` – JaAnTr Mar 15 '15 at 17:57
  • 1
    I tested with SWI-Prolog 7.1.31, it works, are you sure you copy exactly my code ? EDIT I use **member**, not **member1** in my code ! – joel76 Mar 15 '15 at 18:13
  • Got it working now. Is it possible to do it without the `-> select`? The assignment I've got does not allow the use of a lot of built ins and I'm not sure I'm allowed to use it. That's why I've written my own member function. – JaAnTr Mar 15 '15 at 18:31
  • Actually, it does provide an incorrect result for `remove_duplicates([1,2,3,2,1,2,3,4,5], L).`, which yields, `L = [2,4,5]` – lurker Mar 15 '15 at 18:44
  • Oh yeah you're right, it's not working properly. – JaAnTr Mar 15 '15 at 19:00
0

instead of member1/2 you can use select/3, so the element gets removed, and trickle the remaining parameters:

remove_duplicates([],[]).       
remove_duplicates([H|T],X) :- 
    select(H,T,R),                
    !,                          
    remove_duplicates([H|R],[H|X]).
remove_duplicates([H|T],[H|X]) :- 
    remove_duplicates(T,X).

edit it turns out that the code is buggy, it fails - for instance - on ?- remove_duplicates([2,2,2],X).: here a correction

remove_duplicates([],[]).       
remove_duplicates([H|T],X) :- 
    select(H,T,R),                
    !, findall(X, (member(X, R), X\=H), NotH),
    remove_duplicates(NotH, X).
remove_duplicates([H|T],[H|X]) :- 
    remove_duplicates(T,X).
CapelliC
  • 59,646
  • 5
  • 47
  • 90
0

I have this:

remove_duplicates(List, NewList):-
 once(remove_duplicates(List,[],[],NewList)).


remove_duplicates([],_ACALL,Ac,Ac).

remove_duplicates(List,ACALL,Ac,NewList):-
 List= [H|T],
 member(H,ACALL),
 select(H,Ac,NewAc),
 remove_duplicates(T,ACALL,NewAc,NewList).

remove_duplicates(List,ACALL,Ac,NewList):-
 List= [H|T],
 member(H,ACALL),
 remove_duplicates(T,ACALL,Ac,NewList).


remove_duplicates(List,ACALL, Ac,NewList):-
 List =[H|T],
 not(member(H,ACALL)),
 remove_duplicates(T,[H|ACALL],[H|Ac],NewList).

I use two accumulators, one which records all seen items (ACALL) and a second one which has the current list to return.. is this a good way to do this?

user27815
  • 4,767
  • 14
  • 28
  • Yes, it's the idea I used to did it (EDIT of my post), but I use only one accumulator (for dups). – joel76 Mar 16 '15 at 15:46