alldifferent/1 predicate in Prolog

Question

allsame([]).
allsame([X]).
allsame([X,X|Z]) :-
   allsame([X|Z]).

How do I change to get the result below?

alldifferent(L): The elements in L are all different.

?- alldifferent([a, b, b, c, d]).
false
?- alldifferent([a, b, c, d, e]).
true

Answer 1

First, lets look at your definition of allsame/1 first. For a given list, you are establishing equalities like so:

[ A,      B,      C,      D ... ]
    A = B,  B = C,  C = D,   ...      chain pattern

So you are establishing a chain of equalities. There is another way of expressing this, by referring to a common variable instead:

[ A,      B,      C,      D ... ]
  A = V,  B = V,  C = V,  D = V,  ... star pattern

This is most idiomatically expressed by:

allsame_bis(L) :-
   maplist(=(_), L).

Or, more prolix, without using the frequently defined maplist/2:

allsame_ter(L) :-
   allsame_with(L, _).

allsame_with([], _).
allsame_with([X|Xs], V) :-
   X = V,                      % could be moved into the head
   allsame_with(Xs, V).

Now, you say, you "want to relate" this to alldifferent/1, which makes the situation even more complex. Note that alldifferent/1 is not a direct negation of your property. That would be:

notallsame(L) :-
   phrase((..., [A,B], {dif(A,B)}, ...), L),

There are two directly consecutive elements that are different.

For completeness, here is a version that avoids redundant answers for queries like notallsame([1,2,3]):

notallsame_bis(L) :-
   phrase((all(=(A)),[A,B], {dif(A,B)}, ...), L).

There is first a sequence of identical elements, followed by an element that is different.

all//1 and ... //1 are defined elsewhere.

But back to alldifferent/2. The equality-relation is transitive, which permitted us to do some shortcuts, either doing a chain or a star. But being different is not transitive. So we have now to establish the difference relation dif/2 between all possible pairs. In total, we need n2-n/2 many dif/2 goals. Hey, let's be happy that we still can exploit commutativity, otherwise we would have to pay more than twice.

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

This relation establishes dif/2 like so:

 [ A,      B,        C,        D,        E ... ]
       dif(B,A), dif(C,A), dif(D,A), dif(E,A), ... maplist(dif(A),[B,C,D,E ...])
                 dif(C,B), dif(D,B), dif(E,B), ... maplist(dif(B),  [C,D,E ...])
                           dif(D,C), dif(E,C), ... maplist(dif(C),    [D,E ...])
                                     dif(E,D), ... maplist(dif(D),      [E ...])

Here is another version, which might look seductively simpler. In fact, it has a certain resemblance to your original program. Has it not?

alldifferent_bis([]).
alldifferent_bis([_]).
alldifferent_bis([A,B|Xs]) :-
   dif(A,B),
   alldifferent_bis([A|Xs]),
   alldifferent_bis([B|Xs]).

So finally, we might use the following definitions using a higher order definition:

alldifferent_ter(L) :-
   pairwise(dif,L).

allsame_quater(L) :-
   pairwise(=,L).

---

Should you, for whatever reason, not be able to use dif/2, use the safe ISO Prolog approximation iso_dif/2 instead. It will succeed as often as (safely) possible, it might produce an error, when safe failure is possible, though. Think of alldifferent_bis([_,a,a]).

Answer 2

Here's one way:

all_different( Xs ) :-
  all_different(Xs,[])
  .

all_different( []     , _ ) .  % if the source list is exhausted, success!
all_different( [X|_]  , S ) :- % if the list is non-empty
  member(X,S ) ,               % - if we've already seen X
  ! ,                          % - we cut and fail:
  fail                         % The list has duplicates
  .                            %
all_different( [X|Xs] , S ) :- % otherwise, we simply recurse down,
  all_different( Xs , [X|S] )  % prepending X to the "already seen" list.
  .                            % Easy!

Another way:

all_different( Xs ) :- setof( X , member(X,Xs), Xs ) .

A third way:

all_different( Xs ) :-
  msort(Xs,S) ,
  check_uniqueness(S)
  .

check_uniqueness([]) .
check_uniqueness([X,X|_]) :- !, fail .
check_uniqueness([_|Xs])  :- check_uniqueness(Xs) .

A fourth way:

all_different( Xs ) :-
  findall( X , (append(Pfx,[X|Sfx],Xs),(member(X,Pfx);member(X,Sfx))) , [] )
  .

There's more than one way to do it...some more efficient than others.

Answer 3

One more way to do it:

all_different(Xs) :-
    sort(Xs, Sorted),
    msort(Xs, Sorted).

SWI-Prolog-style mode declaration:

%! all_different(+Xs:list) is semidet.