Leave only one copy of the repeated elements

Question

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.

`adj-dups` is not a valid name for a Prolog predicate. Try `adj_dups`. — Daniel Lyons, Dec 11 '15 at 18:52
What do you mean, *but it doesn't work*? What result did you get versus what you expect? — lurker, Dec 11 '15 at 19:39
Please be a bit more specific! In particular, please state which answers are you expecting to get for the query `?- adj_dups([a,a,b,a,a,a,c,c],R).`? `R = [a,c]` or rather `R = [a,a,c]`? — repeat, Dec 12 '15 at 00:20
When I try `?- adj_dups([a,b,a,a,a,c,c],R).` I get this result `R = [a,a,a]` It is supposed to return `R = [a,c]` but for your example `?- adj_dups([a,a,b,a,a,a,c,c],R).` it should return `R = [a,a,c]` (leave only one copy of the adjacent repeated elements). — Mow1993, Dec 12 '15 at 08:44

score 1 · Accepted Answer · answered Dec 12 '15 at 08:53

1

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].

answered Dec 12 '15 at 08:53

CapelliC

59,646
5
47
90

When we have multiple occurrences of the same symbol, it should skip all of them and copy the last one, or maybe copy the first one and skip the others! what is the function "skip" doing here? can you give a brief explanation please? – Mow1993 Dec 12 '15 at 09:14
it does exactly that: skip each (consecutive) occurrences of X – CapelliC Dec 12 '15 at 09:24
perfect! Thank you :) – Mow1993 Dec 12 '15 at 09:32

score 0 · Answer 2 · answered Dec 11 '15 at 21:40

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].

for the input `?- adj_dups([a,b,b,a],R).` it shouldn't return `R = [a,b]` it should rather return `R = [b]` The first 'a' and the last 'a' are treated as different elements, I only need to get one copy of the adjacent repeated elements. — Mow1993, Dec 12 '15 at 08:50
@Mow1993 You're welcome. Turns out I had misunderstood the question. I'll see about changing my answer, but you've already got another answer that did answer the question. — S.L. Barth is on codidact.com, Dec 12 '15 at 09:38

Leave only one copy of the repeated elements

2 Answers2