Pairwise relation over list

Question

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:

Why do you define `i_pairwise` instead of defining the method at the `pairwise_level`? — Willem Van Onsem, Apr 09 '14 at 00:41
@CommuSoft: This is only to exploit 1st argument indexing in several Prolog systems - some do not need that detour, but it does not hurt. — false, Apr 09 '14 at 12:29
@false Out of curiosity, why do you specify that the second argument be a list of lists in the Haskell signature? — Shon, Apr 09 '14 at 13:01

Shon · Answer 1 · 2014-04-10T17:05:43.257

6

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) )
          ).

edited Apr 10 '14 at 17:05

answered Apr 09 '14 at 12:59

Shon

3,989
1
22
35

1

I believe it is useful to permit non-commutative relations like `>`. But I agree that "pairwise" is not the right word for it. – false Apr 09 '14 at 13:05
@false Do you think that "connex" is the right fit for the relation? I may be missing the point... – Shon Apr 09 '14 at 13:08
@false didn't mean to rush... ;) – Shon Apr 09 '14 at 13:13
1

Do you believe that you implemented a connex? I think (by mere speculation for the moment) that your definition is too specialized: There might be a connex wth another permutation other than reverse, and there might a connex that requires another formulation. After all, a connex is: ∀ a, b ∈ X, (a R b) ∨ (b R a) ∨ (a=b). The disjunction is thus very local. – false Apr 09 '14 at 18:16
Consider: `connex_over(>,[1,3,2])` Clearly, this is a connex, but your predicate fails. – false Apr 09 '14 at 18:23
@false In my sleep-deprived state when posting the comment, I did entertain the idea that my definition might work. I knew that it sufficed to solve the one counter example I outlined in my answer, but I suspected it was too simplistic (thus my questions and uncertainty)---in the light of more sleep and your remarks, it is obvious that my predicate doesn't define connex. I think I was able to define this in the new predicate I added to my answer, but I doubt it is the most efficient solution. – Shon Apr 09 '14 at 23:10
@false More importantly, I gather from your replies and the edits to your answer that the order of the elements is supposed to matter, so that your predicate is more accurate than your prose description? (Unless I'm misreading the prose. I'll flag my merely amateur/enthusiast status, here lest my remarks be over-valued). – Shon Apr 09 '14 at 23:16
2

The name came from `pairwise(#\=,Zs)` meaning `all_different(Zs)`. I had not thought more about it than that, originally. But yes, I yes, I think the order should matter. Still something like `connex` would be fine, too - rather in a "forward-recursive" manner, for it would permit to be used in the context of constraints. – false Apr 10 '14 at 12:09
Meta-remark: If you have a different answer, you might also write it here in a separate answer! – false Apr 10 '14 at 17:59
In any case, +1 for finding "connex" at all! – mat Feb 08 '15 at 14:47

score 4 · Answer 2 · edited May 23 '17 at 12:32

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.

Pairwise relation over list

2 Answers2

Linked