Searching a list for (same) two elements in Prolog

Question

How can I search a list in Prolog for a specific element that appears more than once?

For example, if we are searching the list [1,2,3,4,1] for the element 1, Prolog should return true, but otherwise false for all other numbers.

This is what I have so far:

duplicate([], _) :-
   false,
   !.
duplicate([X|_], X) :-
   true,
   !.
duplicate([H|T], X) :-
   T = [_|T1],
   duplicate(T, X),
   duplicate(T1, X).

My basic idea is to search the list until I find the element I am looking for, then search the tail of the list for the item again. I do not want to use the member() function provided by Prolog.

Prolog should also return the elements that appear more than once if asked by the query: duplicate([1,2,3,4,1], X), should print X = 1.

Answer 1

And here the obvious version using grammars. In a sense, we are describing the structure of a list containing a duplicate. That structure is as follows:

• First, there is anything (...),
• then there is the element ([V]),
• again anything (...)
• and again the element ([V])
• followed by anything.

duplicate(L, V) :-
   phrase(( ..., [V], ..., [V], ... ), L).

... --> [] | [_], ... .

As a downside, this version will produce redundant answers for a query like

?- duplicate([a,a,a],a).

This can be overcome by using dif/2:

duplicate(L, V) :-
   phrase(( all(dif(V)), [V], all(dif(V)), [V], ... ), L).

The definition for non-terminal all//1.

Answer 2

What I was saying in my comment was : I want two items from the list L wich are not in the same place so

duplicate(L, V) :-

   % nth0 gives the index (from 0) of an element in a list
   % element V is at the place Id1 in L
   nth0(Id1, L, V),
   % element V is at the place Id2 in L
   nth0(Id2, L, V),
   % Id1 is different from Id2
   % It is more usefull to say that Id1 < Id2
   % Thanks **false** for the improvement
   Id1 < Id2.

Another way to do this is to say : I remove the element of the list (this is done in SWI-Prolog by select/3) and I check if it's in the rest of the list :

duplicate(L, V) :-
    select(V, L, L1),
    member(V, L1).

Answer 3

Pure and simple! Use meta-predicate tcount/3 with reified term equality (=)/3 like so:

?- tcount(=(X), [1,2,3,4,1], 2).
X = 1 ;                              % succeeds, but leaves choicepoint
false.

?- tcount(=(1), [1,2,3,4,1], 2).
true.                                % succeeds deterministically

?- tcount(=(X), [b,c,d,a,b,a,c], 2).
X = b ;
X = c ;
X = a ;
false.

?- tcount(=(a), [b,c,d,a,b,a,c], 2).   
true.                                % succeeds deterministically

Last, let's run the following quite general query:

?- tcount(=(a), Ls, 2).
Ls = [a,a]                                           ;
Ls = [a,a,_X],       dif(_X,a)                       ;
Ls = [a,a,_X,_Y],    dif(_X,a), dif(_Y,a)            ;
Ls = [a,a,_X,_Y,_Z], dif(_X,a), dif(_Y,a), dif(_Z,a) ...

Answer 4

The solution by @false is as clean as it will get. Here is a more verbose solution that states the problem in simpler terms. One thing to remember is that a "duplicated" element might mean that an element occurs exactly twice -- this is how this predicate interprets it -- or it might mean that an element occurs more than once -- this is what you probably mean (so the name duplicate is in fact misleading)

%% duplicate(List, Element) is true for every matching pair of _Element_ in _List_
duplicate([First|Rest], Element) :-
    duplicate_1(Rest, First, Element).

% First occurrence
duplicate_1([This|Rest], X, X) :- % first occurrence
    duplicate_2(Rest, This, X).
duplicate_1([This|Rest], _, X) :- % look further for first occurrence
    duplicate_1(Rest, This, X).

% Second occurrence
duplicate_2(_, X, X). % second occurrence
duplicate_2([This|Rest], _, X) :- % look further for second occurrence
    duplicate_2(Rest, This, X).

This can now be used in all directions:

?- duplicate([b,c,d,a,b,a,c], X).
X = b ;
X = c ;
X = a ;
false.

?- duplicate([b,c,d,a,b,a,c], a).
true ;
false.

?- duplicate(L, a).
L = [a, a|_G274] ;
L = [a, _G273, a|_G277] ;
L = [a, _G273, _G276, a|_G280] .

You will have to use cuts, or dif/2, or once/1 to get rid of the multiple answers, if they are a problem. How exactly depends on how you want to use the predicate.

Answer 5

for the first part of your problem I have found a simple solution:

duplicated([H|T], Item) :- H == Item, second_stage(T, Item).  %first occurence found
duplicated([H|T], Item) :- duplicated(T, Item).
second_stage([H|T], Item) :- H == Item.   %second occurence found -> match!
second_stage([H|T], Item) :- second_stage(T, Item).

This will give true f.e. with duplicated([1,2,3,1,5], 1).

For the second part (query with Variable) I will try to find a way...but I dont know if this is possible in Prolog.

:)