List inequality constraint

Question

I am trying to write a Prolog (CLP) predicate that would build a constraint constraining inequality of two lists.

More formally, having two lists A=[A1,...,AN], B=[B1,...,BN] the constraint is defined as (A1 #\= B1) #\/ (A2 #\= B2) #\/ ... #\/ (AN #\= BN).

I am unsure how to build this constraint given two lists of arbitrary length. This is my attempt. I understand why it does not work, but can not fix it.

any_different([], []).
any_different([H1|T1], [H2|T2]):-
    H1 #\= H2 #\/ any_different(T1, T2).

Answer 1

You'll want to build up the disjunction and return it through a third argument:

any_different([], [], V) :-
    V #= 0.  % no differences between [] and []
any_different([H1|T1], [H2|T2], Disj) :-
    any_different(T1, T2, Disj0),
    Disj #<==> (H1 #\= H2) #\/ Disj0.

Now, calling any_different(List1, List2, AnyDiff) contrains a variable AnyDiff that you can pass to the labeling predicate along with your other variables. By stating AnyDiff #= 0 you can constrain List1 and List2 to be equal, while AnyDiff #= 1 will cause them to be unequal.

Answer 2

I think that, at least in SWI-Prolog, the predicate dif/2 and library(clpfd) could be an alternative to the reification:

?- L=[X,Y,Z], L ins 1..3, dif(L,[1,2,3]), label(L).
L = [1, 1, 1],
X = Y, Y = Z, Z = 1 ;
L = [1, 1, 2],
X = Y, Y = 1,
Z = 2 ;
...

Answer 3

Here's an implementation based on sum/3 and clpfd reification (#<==>)/2:

not_equals_reified(X, Y, B) :-
    X #\= Y #<==> B.

any_different(Xs, Ys) :-
    maplist(not_equals_reified, Xs, Ys, Bs), 
    sum(Bs, #>, 0).

By using meta-predicate maplist/4 we don't even need to write recursive code!