CODEWITHSUNDEEP
prolog
rnso
rnso

Reputation: 24535

Removing consecutive duplicates from a list in Prolog

I have list like following : 

[a,b,b,e,e,f,f,g]

The first and last entries are single, while all others are repeated. How can I remove these extra entries. I should not disturb the order.

I tried following but it gets an empty list: 

removeDups([], []).
removeDups([H1,H2|T], Newlist) :- 
    (H1 == H2 -> removeDups([H2|T],Newlist) 
    ; removeDups(T,Newlist)).

?- removeDups([a,b,b,c,c,d,d,e],L).
L = [].

Edit: I have already checked many similar question on stackoverflow. But in my list the duplicates are consecutive and therefore a simpler solution may be possible. I could not find a question on removing consecutive duplicate entries.

Upvotes: 2

Views: 4077

Answers (4)

SQB
SQB

Reputation: 4078

An empty list with its duplicates removed is, of course, still an empty list.

If the tail does not start with the head, we should keep the head. The de-duplicated tail is the tail with its duplicates removed.
This includes the case where the tail is empty (and so it is a single-element list).

If the list does start with its head repeated, we keep the head. Then we include the head when removing the other duplicates, since the head may be repeated more than once. If we don't include the head, we can't check the tail against it.

remove_dups([],[]).
    
remove_dups([H|T], [H|T1]) :-
    T \= [H|_],
    remove_dups(T, T1).
    
remove_dups([H,H|T], L) :-
    remove_dups([H|T], L).

And here's an example using SWISh.

Upvotes: 1

Ch3steR
Ch3steR

Reputation: 20669

The simplest way in which you can do this is by using takeout function and member function

takeout(X,[X|R],R).
takeout(X,[F|Fs],[F|S]):- takeout(X,Fs,S).
/*takeout function used to remove
 delete given element from the list*/


rem([X],[X]).
rem([H|T],Z):- member(H,T) , takeout(H,[H|T],L) ,!, rem(L,Z).
rem([H|T],[H|Z]):- \+member(H,T) , rem(T,Z).

/* I used cut to stop backtracking of takeout function
 rem([X],[X]). when only one elem present return the same list
 rem([H|T],Z):-member(H,T) , takeout(H,[H|T],L) ,!, rem(L,Z).
 used to takeout the duplicate element from the list.
 rem([H|T],[H|Z]):- \+member(H,T) , rem(T,Z).
 if Head is not present in the tail , do nothing and check for the same in tail.
 */

Upvotes: 0

mat
mat

Reputation: 40768

Why resort to solutions that can only be used in very specific cases, and yield wrong results in other cases? Imperative programming is so 1980... The 80s were cool, I know, but a bit limited too, no?

Try thinking in terms of relations that can be used in all directions!

Here is a solution that uses if_/3 for generality:

no_consecutive_duplicates([], []).
no_consecutive_duplicates([L|Ls0], Ls) :-
        no_dups(Ls0, L, Ls).

no_dups([], E, [E]).
no_dups([L|Ls0], E, Ls) :-
        if_(L=E, Ls=Ls1, Ls=[E|Ls1]),
        no_dups(Ls0, L, Ls1).

It works also in the most general case:

?- no_consecutive_duplicates(Ls0, Ls).
Ls = Ls0, Ls0 = []
Ls = Ls0, Ls0 = [_G501] ;
Ls = [_G501],
Ls0 = [_G501, _G501] ;
Ls = [_G501],
Ls0 = [_G501, _G501, _G501] .

For fair enumeration, use for example:

?- length(Ls0, _), no_consecutive_duplicates(Ls0, Ls).
Ls = Ls0, Ls0 = [] ;
Ls = Ls0, Ls0 = [_G501] ;
Ls = [_G501],
Ls0 = [_G501, _G501] ;
Ls = [_G775, _G775],
Ls0 = [_G787, _G775],
dif(_G775, _G787) .

Note the use of to declaratively state that two terms are different.

And by the way, "normal" cases work too:

?- no_consecutive_duplicates([a,b,c], Ls). 
Ls = [a,b,c].

?- no_consecutive_duplicates([a,a,b,c,c], Ls).
Ls = [a,b,c].

Note that both queries succeed deterministically.

And isn't it nice that we can generalize this and inspect also slightly more complex cases?

?- no_consecutive_duplicates([a,b,X], Ls).
Ls = [a, b],
X = b ;
Ls = [a, b, X],
dif(X, b).

Stay pure folks!

Upvotes: 5

lurker
lurker

Reputation: 58224

In your predicate, the second argument should always represent the result of duplicates being removed from the first argument. That leads to the following clauses when broken down into each case:

remove_dups([], []).   % Empty list is empty list with dups removed
remove_dups([X], [X]). % Single element list is itself with dups removed

% The result of removing duplicates from `[X,X|T]` should be the same
%   as the result of removing duplicates from `[X|T]`
remove_dups([X,X|T], [X|R]) :-
    remove_dups([X|T], [X|R]).

% The result of removing duplicates from `[X,Y|T]` where X and Y are different
%   should be the result [X|R] where R is the result of removing duplicates
%   from [Y|T]
remove_dups([X,Y|T], [X|R]) :-
    X \== Y,
    remove_dups([Y|T], R).

The 3rd and 4th clauses could be replaced with:

remove_dups([X,Y|T], [X|R]) :-
    (   X == Y
    ->  remove_dups([Y|T], [X|R])
    ;   remove_dups([Y|T], R)
    ).

But then it will limit solutions where the first argument is variable.

Upvotes: 2

Related Questions