CODEWITHSUNDEEP
listduplicatesprologlogicpredicate
John Lee
John Lee

Reputation: 35

Removing Duplicates while maintaining order in Prolog

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]

Upvotes: 2

Views: 642

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477503

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.

Upvotes: 2

Related Questions