Prolog no_duplicate function

I'm trying to write a simple procedure that checks if a list has any duplicates. This is what I have tried so far:

% returns true if the list has no duplicate items.
no_duplicates([X|XS]) :- member(X,XS) -> false ; no_duplicates(XS).
no_duplicates([]) :- true. 

If I try no_duplicates([1,2,3,3]). It says true. Why is this? I'm probably misunderstanding Prolog here, but any help is appreciated.


  • I'd go at the problem more descriptively:

    no_duplicates( []     ) .  % the empty list is unique
    no_duplicates( [X|Xs] ) :- % a list of length 1+ is unique
      \+ member(X,Xs) ,        % - if its head is not found in the tail,
      no_duplicates(Xs)        % - and its tail is itself unique.
      .                        %

    Thinking on this, since this is a somewhat expensive operation — O(n2)? — it might be more efficient to use sort/2 and take advantage of the fact that it produces an ordered set, removing duplicates. You could say something like

    no_duplicates( L ) :-
      sort(L,R)   , % sort the source list, removing duplicates
      length(L,N) , % determine the length of the source list
      length(R,N) . % check that against the result list

    Or you could use msort/3 (which doesn't remove duplicates), might be a bit faster, too:

    no_duplicates( L ) :-
      msort(L,R),            % order the list
      \+ append(_,[X,X|_],R) % see if we can find two consecutive identical members