Adventures in Prolog - Computations with lists III

This week's post is concerned with another operation on lists, i.e. how to compute a set given a list. This means that given a list containing any values, we wish to remove duplicates from this list to obtain a set containing unique members. The predicate rem_dups/2 does exactly this.

rem_dups([X[]], [X]).

rem_dups([HT], X) :-
member(H, T),
!,
remove(H, T, Y),
rem_dup([HY], X);
rem_dup(T, Y),
append([H], Y, X).

The problem forumulation basically says that if the head of a list is contained within the tail of the list it is a duplicate. Consequently, this duplicate (and any further duplicate of H) is removed from T. Since we want to retain H, we need to connect it with the list that does not contain any instance of H, i.e. X. This procedure is followed for all elements of the list. If a list element does not have a duplicate it is not removed from the list.

rem_dup makes use of auxiliary predicates like remove/3, append/3 and member/2. member/2 checks whether some X is element of some list L. remove/3 removes some X from list L1 yielding the result list L2. append/3 does the opposite it appends some X to an existing list L1 yielding L2.