Pairwise relation over list

问题:

The following higher order predicate succeeds if all pairs of the list's elements are true for a given relation. Is there a common or better, more intention revealing name for this relation?

My original motivation for this name was that in clpfd, there is often a constraint all_different/1 which is described as being true, iff the elements are pairwise different. In fact, rather preferred to say the elements are all different, but I have been frequently corrected (by fellow Prolog programmers) to use pairwise different. In fact, this constraint can now most naturally be expressed as pairwise(#\=, Zs).

pairwise(Rel_2, Xs) :-
   i_pairwise(Xs, Rel_2).

i_pairwise([], _).
i_pairwise([X|Xs], Rel_2) :-
   maplist(call(Rel_2,X),Xs),
   i_pairwise(Xs, Rel_2).

As @aBathologist observed, pairwise is not the right word, because it might make sense for non-reflexive Rel too.

Also, the relation Rel is not a total relation, because call(Rel, X, X) might fail, but pairwise(Rel, Xs) could still succeed.

I even hoogled for (a->a->Bool)->[a]->Bool. But Hayoo found it: name pairwise in contrast to pointwise.

Looked at MO and mathematics:

• Who invented pairwise different

• Difference between pairwise distinct and unique

回答1:

I like your question very much. I went digging around through wikipedia to try and find a fitting term. I'm thinking of the list as a set, in the sense that each member is a distinct and differentiable element, so that even if there were two instances of the same atom, would be different elements, qua their position or whatever. I think that the predicate you've described would, then, be a [connex] binary relation (https://en.wikipedia.org/wiki/Total_relation):

A binary relation R over X is called connex if for all a and b in X such that a ≠ b, a is related to b or b is related to a (or both)

On the other hand, if the relation is also meant to be reflexive, then it would describe a total binary relation (dicussed on the same page as connex).

However, I think that your predicate pairwise/2 doesn't actually fit the description you give, or (more likely) I don't quite understand.

You say that the predicate should succeed "if all pairs of the list's elements are true for a given relation". But pairwise(>, [1,2,3]) is false whereas pairwise(<, [1,2,3]) is true, while pairwise(>, [3,2,1]) is true but pairwise(<, [3,2,1]) is false. But out of each pair of elements from these lists, one is greater than the other.

---

Edits:

The following is the result of my misunderstanding, and turned out not to be relevant to the question.

I offered the following definition, thinking it might be a more accurate definition of what @false was describing, but he pointed out that it doesn't define the relation I thought it did. I have kept it for the sake of making our subsequent exchange in the comments intelligible.

Adding another clause that checks the list in reverse would solve this problem, but might there be other relations which can't be caught by reversing? Also, is there a more efficient way of implementing a genuine connex check?

connex_over(Rel, Xs) :-
   i_connex_over(Xs, Rel), !.
connex_over(Rel, Xs) :-
   reverse(Xs, Sx),
   i_connex_over(Sx, Rel).

i_connex_over([], _).
i_connex_over([X|Xs], Rel) :-
   maplist(call(Rel,X),Xs),
   i_connex_over(Xs, Rel).

After @false pointed out my error in the preceding, I wrote the following definition. I believe it does describe a connex over the elements of S:

actual_connex_over(Rel, S) :-
   foreach( ( select(X, S, T), member(Y, T) ),
            ( call(Rel, X, Y) ; call(Rel, Y, X) )
          ).

回答2:

Such a higher-order predicate would clearly be very useful (example: breaks/1).

Like for the foldl/n family of predicates, a mnemonic name for this should in my opinion focus less on the arising algebraic structure, but on the pattern that we find here. For example, this pattern somewhat resembles an accordion, but this is clearly not yet a good name. There seems to be a generalisation of foldl/4 or scanl/4 (or some mixture) within reach of which this pattern is a special case.