CODEWITHSUNDEEP
listprolog
Mow1993
Mow1993

Reputation: 89

Leave only one copy of the repeated elements

I'm trying to create a predicate in Prolog that takes a list and returns only one copy of the adjacent duplicates of the list. for example:

?- adj_dups([a,b,a,a,a,c,c],R).
R=[a,c]

I think I need two base cases:

adj_dups([],[]). % if list is empty, return empty list
adj_dups([X],[]). % if list contains only one element, return empty list (no duplicates).

then for the recursive part, I need to compare the head with the head of the tail, and then go recursively on the tail of the list. This is what I came up with so far, but it doesn't work!

adj_dups([X,X|T],[X|R]):- adj_dups([X|T],R). % if the list starts with duplicates
adj_dups([X,Y|T],R):- X \= Y, adj_dups([X|T],R). % if the list doesn't start wih duplicates

How can I fix it so I can get the right result?

Edit: I'll list some examples to help you all understand my problem. How the code supposed to behave: 

?- adj_dups([a,c,c,c,b],R).
R = [c]
?- adj_dups([a,b,b,a,a],R).
R = [b,a]
?- adj_dups([a,b,b,a],R).
R = [b]

How my code is behaving: 

?- adj_dups([a,c,c,c,b],R).
R = []
?- adj_dups([a,b,b,a,a],R).
R = [a,a]
?- adj_dups([a,b,b,a],R).
R = [a]

Thank you.

Upvotes: 3

Views: 211

Answers (2)

CapelliC
CapelliC

Reputation: 60014

I find ambiguous this specification

only one copy of the adjacent duplicates of the list

as it doesn't clarify what happens when we have multiple occurrences of the same duplicate symbol.

adj_dups([],[]).
adj_dups([X,X|T],[X|R]) :-
    skip(X,T,S),
    adj_dups(S,R),
    \+ memberchk(X,R),
    !.
adj_dups([_|T],R) :- adj_dups(T,R).

skip(X,[X|T],S) :- !, skip(X,T,S).
skip(_,T,T).

This yields

?- adj_dups([a,a,c,c,a,a],R).
R = [c, a].

Comment the + memberchk line to get instead

?- adj_dups([a,a,c,c,a,a],R).
R = [a, c, a].

Upvotes: 1

S.L. Barth is on codidact.com
S.L. Barth is on codidact.com

Reputation: 8245

Let's look at what happens when you try a simpler case:

adj_dups([a,b,b,a],R).

The first three predicates don't match, so we get:

adj_dups([X,Y|T],R):- X \= Y, adj_dups([X|T],R).

This is the problematic case: X is bound to a, Y is bound to b.
It will then call adj_dups([a,b,a],R), binding T to [b,a], which only has a single b. Effectively, you have now removed the duplicate b from the list before it could be processed.

Let's create a few auxiliary predicates first - especially a predicate that filters an element from a list. Then, in the recursive part, there are two cases:

If the first element occurs in the tail of the list being processed, it is duplicated; we need to return that first element followed by the processed tail. Processing the tail consists of removing that first element from it, then check the tail for duplicates.

The second case is much simpler: if the first element does not occur in the tail, we simply apply adj_dups to the tail and return that. The first element was never duplicated, so we forget about it.

% Filter the element X from a list.
filter(X,[],[]).
filter(X,[X|T],R)     :- filter(X,T,R).
filter(X,[Y|T],[Y|R]) :- X \= Y, filter(X,T,R).

% Return "true" if H is NOT a member of the list.
not_member(H,[]).
not_member(H,[H|T]):-fail.
not_member(H,[Y|T]):-H \= Y, not_member(H,T).


% Base cases for finding duplicated values.
adj_dups([],[]).  % if list is empty, return empty list
adj_dups([X],[]). % if list contains only one element, return empty list (no duplicates).

% if H1 is in T1 then return the H1 followed by the adj_dups of (T1 minus H1).
% if H1 is not in T1 then return the adj_dups of T1.
adj_dups([H1|T1],[H1|T3]):-member(H1,T1), filter(H1,T1,T2), adj_dups(T2,T3).
adj_dups([H1|T1],T3):-not_member(H1, T1), adj_dups(T1,T3).

This gives R=[a,b] for the input [a,b,b,a], and R=[a,c] for your example input [a,b,a,a,a,c,c].

Upvotes: 0

Related Questions