Return a list that only includes duplicate elements-CodePudding

I am not allowed to use any built-in ProLog list predicates. I am just starting out with ProLog and was given the following exercise:

Write a predicate repeated(L,D) where D is a list of all values that have duplicates in the list L.

?- repeated([a,b,a,d,a,d],D).
D = [a,d].

Please help, I've been stuck on this for a pretty long time now :// THANK YOU!!

CodePudding user response：

Seems like the answer suggested by Nicholas Carey's answer does not output exactly [a, d], but [b, a, d].

However, inspired by him, I updated the logic and here is the working code:

repeated( []     , []     ) .
repeated( [X|Xs] , [X|Ds] ) :- 
    repeated(Xs, Ds), 
    contains(X, Xs), negate(contains(X, Ds)), !.      % <--- New logic here
repeated( [_|Xs] ,    Ds  ) :- repeated(Xs, Ds).

contains(X, [X|_] ).
contains(X, [_|Xs] ) :- contains(X,Xs).
negate(X) :- \  X.

The logic of the modified version is to ensure that the first element X has a duplicate in the list Xs. And also ensure that it is not already in the "return" list Ds.

Example of working queries:

?- repeated([a,b,a,23,1432,5,25,23,23,24,23,25,25,21,d,a,d], D).
D = [a, 23, 25, d]
?- repeated([a, b, b, b, b], D).
D = [b]

contains/2 is just a custom implementation of member/2.

negate/1 is just a custom implementation of not/1.

CodePudding user response：

Break it down. Most recursive problems have 1 or 2 special, terminating cases and the general case.

So...

The special, terminating case is the empty list. It contains no duplicate items:

repeated( [] , [] ) .

The general case is this:

The head of the list is a duplicate, iff...

it can be found in the tail of the list.

So, we need a way to identify the dupe:

is_duplicate(X,Xs) :- \  contains(X,Xs) .

contains(X, [X|Xs] ).
contains(X, [_|Xs] ) :- contains(X,Xs).

[Incidentally, contains/2 is essentially the implementation of the built-in member/2.]

Once we have that, implementing the general recursive case is easy. We just traverse the list and find the duplicates:

repeated( [X|Xs] , [X|Ds] ) :- is_duplicate(X,Xs), !, repeated(Xs,Ds) .
repeated( [_|Xs] ,    Ds  ) :- repeated(Xs,Ds).

The cut (!/0) is there to eliminate the choice point: If X is a duplicate, we don't want to try the 3rd/last alternative on backtracking.

If you put that together, you get this:

repeated( []     , []     ) .
repeated( [X|Xs] , [X|Ds] ) :- is_duplicate(X,Xs), !, repeated(Xs,Ds) .
repeated( [_|Xs] ,    Ds  ) :- repeated(Xs,Ds).

is_duplicate(X,Xs) :- \  contains(X,Xs) .

contains(X, [X|Xs] ).
contains(X, [_|Xs] ) :- contains(X,Xs).