问题 列表上的成对关系


如果给定关系的列表元素的所有对都为真,则以下高阶谓词成功。对于这种关系,是否存在共同的或更好的,更具意图的名称?

我最初的动机是这个名字 ,经常有一个约束 all_different/1 如果元素是,则被描述为真 成对不同。事实上,更倾向于说元素都是不同的,但我经常被修正(由Prolog程序员同意)使用成对不同。事实上,这种约束现在最自然地表达为 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所观察到的,成对不是正确的词,因为它可能对非反身有意义 Rel 太。

还有,关系 Rel 不是一个完全的关系,因为 call(Rel, X, X) 可能会失败,但是 pairwise(Rel, Xs) 仍然可以成功。

我甚至还在鼓励 (a->a->Bool)->[a]->Bool。但是哈尤 找到了: 名称 pairwise 与逐点相反。

看MO和数学:


950
2018-04-08 23:29


起源

你为什么定义 i_pairwise 而不是定义方法 pairwise_level? - Willem Van Onsem
@CommuSoft:这只是为了在几个Prolog系统中利用第一个参数索引 - 有些不需要绕道而行,但它没有受到伤害。 - false
@false出于好奇,为什么要指定第二个参数是Haskell签名中的列表列表? - Shon Feder
@aBathologist:修复了!但这并没有什么不同 - false
怎么样 pairwise//2?潜在用途? - repeat


答案:


我非常喜欢你的问题。我通过维基百科挖掘,试图找到一个合适的术语。我认为列表是一个集合,因为每个成员都是一个独特且可区分的元素,所以即使有两个相同原子的实例,也可能是不同的元素,它们的位置或其他。我认为你所描述的谓词将是[connex]二元关系(https://en.wikipedia.org/wiki/Total_relation):

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

另一方面,如果关系也意味着反身,那么它将描述一个  二元关系(与connex在同一页面上讨论)。

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

你说如果列表的所有元素对于给定的关系都是真的,那么谓词应该成功“。但 pairwise(>, [1,2,3]) 是假的,而 pairwise(<, [1,2,3]) 是的,同时 pairwise(>, [3,2,1]) 是的,但是 pairwise(<, [3,2,1]) 是假的。但是,从这些列表中的每对元素中,一个  比另一个更大。


编辑:

以下是我误解的结果,结果与问题无关。

我提出了以下定义,认为它可能是@false描述的更准确的定义,但他指出它没有定义我认为它做的关系。我保留它是为了让我们在评论中的后续交流可以理解。 

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

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

6
2018-04-09 12:59



我认为允许非交换关系是有用的 >。但我同意“成对”不适合它。 - false
@false你认为“connex”是否适合这种关系?我可能会忽略这一点...... - Shon Feder
@false并不意味着急于...;) - Shon Feder
你相信你实现了一个连接?我认为(目前仅仅是猜测)你的定义过于专业化:除了反向之外,可能存在另一种相互作用的连接,并且可能存在需要另一种表述的连接。毕竟,连接点是:∀a,b∈X,(a R b)∨(b R a)∨(a = b)。因此,脱节是非常局部的。 - false
这个名字来自 pairwise(#\=,Zs) 含义 all_different(Zs)。最初,我没有想到更多。但是,是的,我是的,我认为顺序应该重要。还是喜欢的东西 connex 也会很好 - 而不是以“前向 - 递归”的方式,因为它允许在约束的环境中使用。 - false


这样的高阶谓词显然非常有用(breaks/1)。

喜欢的 foldl/n 谓词族,在我看来,这应该是一个助记符号,而不是关注代数结构的出现,而是我们在这里找到的模式。例如,这种模式有点类似于 手风琴,但这显然不是一个好名字。似乎有一种概括 foldl/4 要么 scanl/4 (或某种混合物)这种模式是一种特殊情况。


4
2017-11-24 10:15