Prolog no_duplicate function

Question

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 assume you are using SWI Prolog (since you have the swi-prolog tag in the question). I tested your program with SWI 6.6.6 and it works for the case you mentioned, giving me `false`. — Jay, Sep 25 '14 at 20:25
That's weird.. I'm using 6.6.6 as well, and it gives me true. — Nathan, Sep 25 '14 at 20:39
How did you load the code? Did you put it in a file (say, "`dup.prolog`") then loaded it into SWI with `['dup.prolog'].` before asking the query? — Jay, Sep 25 '14 at 22:44

score 7 · Answer 1 · edited May 23 '17 at 12:08

To answer your questions: your solution actually fails as expected for no_duplicates([1,2,3,3]). So there is no problem.

Now take the queries:

?- A = 1, no_duplicates([A, 2]).
A = 1.
?-        no_duplicates([A, 2]), A = 1.

They both mean the same, so we should expect that Prolog will produce the same answer. (_{To be more precise we expect the same ignoring errors and non-termination}).

However, four proposed solutions differ! And the one that does not, differs for:

?- A = 2, no_duplicates([A, 2]).
false.
?-        no_duplicates([A, 2]), A = 2.

Note that it is always the second query that makes troubles. To solve this problem we need a good answer for no_duplicates([A, 2]). It cannot be false, since there are some values for A to make it true. Like A = 1. Nor can it be true, since some values do not fit, like A = 2.

Another possibility would be to issue an instantiation_error in this case. Meaning: I have not enough information so I better stop than mess around with potentially incorrect information.

Ideally, we get one answer that covers all possible solutions. This answer is dif(A, 2) which means that all A that are different to 2 are solutions.

dif/2 is one of the oldest built-in predicates, already Prolog 0 did possess it. Unfortunately, later developments discarded it in Prolog I and thus Edinburgh Prolog and thus ISO Prolog.

However, current systems including SICStus, YAP, SWI all offer it. And there is a safe way to approximate dif/2 safely in ISO-Prolog

no_duplicates(Xs) :-
   all_different(Xs). % the common name

all_different([]).
all_different([X|Xs]) :-
   maplist(dif(X),Xs).
   all_different(Xs).

See: prolog-dif

lurker · Answer 2 · 2014-09-26T02:18:40.220

3

Here's yet another approach, which works because sort/2 removes duplicates:

no_duplicates(L) :-
    length(L, N),
    sort(L, LS),
    length(LS, N).

edited Sep 26 '14 at 02:18

answered Sep 26 '14 at 02:13

lurker

56,987
9
69
103

score 2 · Answer 3 · answered Sep 25 '14 at 21:04

2

Duplicates in a list are same elements not at the same place in the list, so no_duplicates can be written :

no_duplicates(L) :-
    \+((nth0(Id1, L, V), nth0(Id2, L, V), Id1 \= Id2)).

answered Sep 25 '14 at 21:04

joel76

5,565
1
18
22

2

You can also try `append(_, [E | R], L), member(E, R)`—might be faster, as it avoids explicit comparison. – liori Sep 25 '14 at 22:48

score 2 · Accepted Answer · edited Jun 04 '19 at 05:31

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(n²)? — 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
  .

OP's solution is right. And yours gives one alternative, so it isn't false, but there aren't two altering ways of no duplicates in a list. so this isn't a good solution. I'd remove the singelton list case. — Patrick J. S., Sep 26 '14 at 12:47
This last version with `msort/2` and syntactic unification exposes even more erratic behavior than your original solution. — false, Sep 26 '14 at 20:52

score 1 · Answer 5 · answered Sep 25 '14 at 22:02

1

Jay already noted that your code is working. An alternative, slightly less verbose

no_duplicates(L) :- \+ (append(_, [X|XS], L), memberchk(X, XS)).

answered Sep 25 '14 at 22:02

CapelliC

59,646
5
47
90

Prolog no_duplicate function

5 Answers5