Prolog: check against duplicates in a list

Question

1. Write a predicate allDistinct/1 whose parameter is a list (of symbols) and which succeeds if all symbols in the list are different.

   notin(A,[]).
   notin(A,[B|C]) :-
      A\=B,
      notin(A,C).
   
   allDistinct([]).
   allDistinct([_]).
   allDistinct([A|B]) :-
      notin(A,B), 
      allDistinct(B).
   

Answer 1

Following up on the previous sketch by @whd we can proceed like this.

Based on iwhen/2 we can succinctly define distinct/1 like so:

:- use_module(library(lists), [same_length/2]).

distinct(Es) :-
   iwhen(ground(Es), (sort(Es,Fs),same_length(Es,Fs))).

Sample queries using SICStus Prolog 4.5.0:

| ?- distinct([1,2,3]).
yes
| ?- distinct([1,2,3.0]).
yes
| ?- distinct([1,2,3.0,2]).
no
| ?- distinct([1,2,3.0,X]).
! error(instantiation_error,_283)

Answer 2

Predicate sort/2 sorts and remove duplicates from list. You can use it, compare length(length/2 predicate) of new sorted list with old one if they differs there were some duplicated values.

Answer 3

This is one of those questions with a fair number of alternative, reasonable solutions. Assuming that common library predicates can be used, here is another one:

all_distinct(List) :-
    \+ (
        select(Element, List, Tail),
        select(Element, Tail, _)
    ).

A performance advantage of this solution is that it stops scanning the list as soon as it finds a duplicated element. But is it faster than solutions based on the standard sort/2 predicate? Unclear as sort/2 is an highly optimized predicate in most Prolog systems. Plus, let's no forget that, unless we're sure that all list elements are bound, we should be safe and check it (see @repeat answer).