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.