CODEWITHSUNDEEP
prolog
wollenS
wollenS

Reputation: 67

Prolog: find and put into the list duplicates

Good day, guys. Can't figure out, why prolog predicate is putting all duplicates into my new list. F.e. I have to pick all duplicates:

?- duplicates([a, b, a, a, d, d], R). 
R = [a, d]

I have wrote this prolog program:

duplicates([], []).
duplicates([First|Rest], NewRest) :- 
    not(member(First, Rest)), 
    duplicates(Rest, NewRest).
duplicates([First|Rest], [First|NewRest]) :- 
    member(First, Rest), 
    duplicates(Rest, NewRest).

But it returns:

R = [a, a] .

I think I need to put a (!) sign somewhere, but cannot understand, where. Any suggestions?

Upvotes: 2

Views: 87

Answers (2)

Duda
Duda

Reputation: 3736

Try this:

duplicates([], []).
duplicates([First|Rest], NewRest) :- 
    \+ member(First, Rest),
    duplicates(Rest, NewRest).
duplicates([First|Rest], NewRest) :- 
    duplicates(Rest, NewRest),
    member(First, NewRest).
duplicates([First|Rest], [First|NewRest]) :- 
    member(First, Rest), 
    duplicates(Rest, NewRest),
    \+ member(First, NewRest).

?- duplicates([a, b, a, a, d, d], R).
R = [a, d] ;
false.

I have choosen a version where you don't need cuts (the !). Also I added another rule: elements in NewRest can appear only once. Note: membership in NewRest can be testet only after unification of all of its entries.

Upvotes: 1

CapelliC
CapelliC

Reputation: 60004

library(aggregate) allows a compact solution for your problem.

duplicates(L,D) :- findall(K,(aggregate(count,member(K,L),C),C>1),D).

?- duplicates([a, b, a, a, d, d], R).
R = [a, d].

Clearly, it's less immediate to grasp than @Raubsauger' good answer, and not available in every Prolog out there.

Upvotes: 2

Related Questions