Prolog: Pairwise compatible on multiple lists using recursion

Question

So I have a predicate:

compatible([],_).
compatible(_,[]).
compatible([HA|TA],[HB|TB]) :-
    HA \= HB,
    compatible(TA,TB).

It currently takes two lists and determines if they are pairwise compatible returning true if so and false if not.

For example:

?- compatible([8,2,6,3,67],[7,4,7,4,3]).
true 

?- compatible([8,2,6,3,3],[7,4,7,4,3]).
false.

The 2nd call returned false because a 3 was in the 5th position of both lists.

My question is how can I modify this predicate so it recursively checks more than 2 lists. Potentially, the predicate could check a list of lists that contains 1,2,3,4,5 or perhaps even infinite lists. It would return false if any of the lists weren't compatible with one another.

Therefore I could check 3 lists like so:

let Y = [[8,2,6,3,67],[7,4,7,4,3],[1,3,42,1,52]]
then...

?- compatible(Y).
true 

let Z = [[8,2,6,3,67],[7,4,7,4,3],[1,3,6,1,52]]
then...

?- compatible(Z).
false.

where the 2nd call fails because a 6 was in the 3rd position of list 1 and 3.

Answer 1

If all the sublists are of the same length, and if the elements are always integers, you can define your problem in terms of two predicates provided by library(clpfd):

compatible(Ls) :-
    transpose(Ls, T),
    maplist(all_different, T).

With this definition, your examples:

?- compatible([[8,2,6,3,67],[7,4,7,4,3],[1,3,42,1,52]]).
true.

?- compatible([[8,2,6,3,67],[7,4,7,4,3],[1,3,6,1,52]]).
false.

If the sublists can have different lengths, you should first find the shortest, and cut the rest to that length.

If the elements of the lists can be arbitrary Prolog terms, take a look at this question. In short:

all_different_terms([]).
all_different_terms([H|T]) :-
    maplist(dif(H), T),
    all_different_terms(T).

Note the use of dif/2 instead of \=/2.

?- compatible_terms([[a,b,c],[d,e,f],[g,h,i]]).
true.

?- compatible_terms([[a,b,c],[d,e,f],[a,h,i]]).
false.

The definition of all_different_terms/1 should also give you an idea how to implement your initial suggestion, reusing the predicate compatible/2 that you have already defined:

all_compatible([]).
all_compatible([H|T]) :-
    maplist(compatible(H), T),
    all_compatible(T).

Answer 2

Writing recursive Prolog code can be a good exercise, a lot of fun, a rewarding activity, but getting the nitty-gritty details of recursion right can be hard, particularly for novices!

Luckily, there's another way; one that can lift you up to a higher-level, to a more idiomatic way of logic programming, which immediately enables you to do lots of things.

For your "pairwise compatibility" problem, consider using meta-predicate pairwise/2 in combination with that compatible/1 predicate you already have! Here's how:

?- pairwise(compatible, [[8,2,6,3,67],[7,4,7,4,3],[1,3, 6,1,52]]).
false.                               % finite failure, as expected

?- pairwise(compatible, [[8,2,6,3,67],[7,4,7,4,3],[1,3,42,1,52]]).
  true                               % succeeds, as expected
; true                               % (1st redundant answer)
; true                               % (2nd redundant answer)
; true                               % (3rd redundant answer)
; true                               % (4th redundant answer)
; true                               % (5th redundant answer)
; true                               % (6th redundant answer)
; true.                              % (7th redundant answer)

---

Edit

Good news first: Both above answers are correct! So what does "redundant answers" mean? Are they good? Bad? If so, how bad? How come? And, how can we cope? Let's find out!

1. Redundant answers are bad and should be disposed of. They are quite common, too.

2. Redundant answers are not as bad as, say, "losing declarative semantics".

3. Redundant answers are worse than "useless choicepoints left behind after all answers have been found". For details on that issue look at the explanations given in this answer.

4. How come? To answer that question, we consider the definition of compatible/1:

   compatible([],_).
   compatible(_,[]).
   compatible([HA|TA],[HB|TB]) :-
       dif(HA,HB),                  % unlike `(\=)/2`, `dif/2` is sound
       compatible(TA,TB).
   

   The two culprit clauses are highlighted. With common-place first argument indexing (and above definition), Prolog is not able to infer that some goals can succeed deterministically.

5. Can we cope? And, if so, how? Procedural problem—procedural solution, right?! Yes, but we need to choose the wise path lest we trade in declarative semantics for some mere finite speedup—like many quick fixes based on meta-logical Prolog predicates would.

   As luck would have it, we can call first argument indexing to the rescue!

   compatible([],_).
   compatible([X|Xs],Ys) :-
      compatible_(Ys,X,Xs).
   
   compatible_([],_,_).
   compatible_([Y|Ys],X,Xs) :-
      dif(X,Y),
      compatible(Xs,Ys).
   

6. Better now? Let's run above queries with the improved definition of compatible/1:

   ?- pairwise(compatible, [[8,2,6,3,67],[7,4,7,4,3],[1,3, 6,1,52]]).
   false.                           %  SAME : finitely fails
   
   ?- pairwise(compatible, [[8,2,6,3,67],[7,4,7,4,3],[1,3,42,1,52]]).
   true.                            % BETTER: succeeds deterministically