11

如果列表元素的所有对对于给定关系都为真，则以下高阶谓词成功。这种关系有一个共同的或更好的、更能揭示意图的名称吗？

我取这个名字的最初动机是，在中，通常存在一个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 观察到的，pairwise 不是正确的词，因为它也可能对非反身有意义Rel。

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

我什至为(a->a->Bool)->[a]->Bool. 但是 Hayoo发现了它：namepairwise与 pointwise 不同。

看了MO和数学：

4

2 回答 2

6

我非常喜欢你的问题。我通过维基百科四处挖掘，试图找到一个合适的术语。我将列表视为一个集合，因为每个成员都是一个独特且可区分的元素，因此即使有同一个原子的两个实例，也会是不同的元素，在它们的位置或其他方面。我认为您所描述的谓词将是 [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) )
          ).
于 2014-04-09T12:59:34.160 回答
4

这样的高阶谓词显然非常有用（例如：）breaks/1。

就像foldl/n谓词族一样，在我看来，它的助记名称应该较少关注产生的代数结构，而应该关注我们在这里找到的模式。例如，这种模式有点像手风琴，但这显然还不是一个好名字。似乎有一种概括foldl/4或scanl/4（或某种混合）在范围内，这种模式是一种特殊情况。

于 2014-11-24T10:15:09.823 回答