I am trying to create a predicate that removes duplicates from a list while maintaining its relative order. For example a list that is [1,2,2,3,4,5,5,2] should return [1,2,3,4,5]. However, my code is only able to remove consecutive duplicates and for instance, not the 2 at the end.
remove_duplicates([],[]).
remove_duplicates([H],[H]).
remove_duplicates([H,H|T],[H|List]) :- remove_duplicates(T,List).
remove_duplicates([H,X|T],[H|T1]):- X\=H, remove_duplicates([X|T],T1).
Another approach I was thinking of was to use member to see if the Tail contains the Head. However, the only way I can think of solving it that way is where I would remove the head, if head is a member of tail. This would however keep the last instance of the number only and break the relative order of the numbers in the list.
For instance:
[1,2,2,3,4,5,5,2]
[1,3,4,5,2]
When I actually want
[1,2,3,4,5]
You can make use of an accumulator: an extra parameter, here a list that is initially empty and when new elements arise will grow. Each recursive call the list is passed (or an updated copy).
For example:
remove_duplicates(LA, LB) :-
remove_duplicates(LA, LB, []).
remove_duplicates([], [], _).
remove_duplicates([H|T], R, Seen) :-
( member(H, Seen)
-> (R = S, Seen1 = Seen)
; (R = [H|S], Seen1 = [H|Seen])
),
remove_duplicates(T, S, Seen1).This then gives us:
?- remove_duplicates([1,2,2,3,4,5,5,2], L).
L = [1, 2, 3, 4, 5].
Of course you can make use of more effective datastructures than a list. I leave that as an exercise.