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.
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
Here's yet another approach, which works because sort/2
removes duplicates:
no_duplicates(L) :-
length(L, N),
sort(L, LS),
length(LS, N).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With