列表上的成对关系 [英] 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?

我使用这个名字的最初动机是在 clpfd，通常有一个约束 all_different/1 被描述为真，如果元素是成对不同.事实上，更喜欢说元素都不同，但我经常被纠正(由 Prolog 程序员)使用成对不同.事实上，这个约束现在可以最自然地表示为 pairwise(#\=, Zs).

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

正如@aBathologist 所观察到的，pairwise 不是正确的词，因为它对于非反身 Rel 也可能有意义.

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

另外，关系 Rel 不是全关系，因为 call(Rel, X, X) 可能会失败，但是 pairwise(Rel, Xs) 仍然可以成功.

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

我什至为 (a->a->Bool)->[a]->Bool.但是 Hayoo 找到它:与 pointwise 相比，命名 pairwise.

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

看了MO和数学:

• 谁发明的成对不同

成对独特和独特的区别

推荐答案

我非常喜欢你的问题.我翻遍了维基百科，试图找到一个合适的术语.我将列表视为一个集合，从某种意义上说，每个成员都是一个不同且可微的元素，因此即使同一原子有两个实例，也会是不同的元素，因为它们的位置或其他什么.我认为您所描述的谓词将是 [connex] 二元关系 (https://en.wikipedia.org/wiki/Total_relation):

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

如果对于 X 中的所有 a 和 b 使得 a ≠ b，a 与 b 相关或 b 与 a(或两者)相关，则 X 上的二元关系 R 称为连接

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)

另一方面，如果该关系也意味着自反，那么它将描述一个总二元关系(在与 connex 相同的页面上讨论).

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

但是，我认为您的谓词 pairwise/2 实际上并不符合您给出的描述，或者(更有可能)我不太明白.

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

您说谓词应该成功如果列表的所有元素对对于给定关系都为真".但是 pairwise(>, [1,2,3]) 为假而 pairwise(<, [1,2,3]) 为真，而 pairwise(>, [3,2,1]) 为真，但 pairwise(<, [3,2,1]) 为假.但是在这些列表的每一对元素中，一个大于另一个.

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.

以下是我误解的结果，结果与问题无关.

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

我提供了以下定义，认为这可能是对@false 所描述内容的更准确定义，但他指出它并没有定义我认为的关系.我保留它是为了让我们在评论中的后续交流易于理解.

添加另一个反向检查列表的子句可以解决这个问题，但是否还有其他关系无法通过反向捕获?另外，是否有更有效的方法来实现真正的连接检查?

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

@false 指出我在前面的错误后，我写了以下定义.我相信它确实描述了 S 元素的联系:

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

这篇关于列表上的成对关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！