different/2 - 是否存在一个纯粹的、确定的定义？

Question

different(Xs, Ys) :-
   member(X, Xs),
   non_member(X, Ys).
different(Xs, Ys) :-
   member(Y, Ys),
   non_member(Y, Xs).

虽然这个使用 member/2 and non_member/2 的定义从声明的角度来看几乎¹ 完美，但它会为某些查询产生冗余解决方案并在周围留下选择点。

什么是对此进行改进的定义（可能以纯粹的方式使用 if_/3 and (=)/3），使得 different/2 描述了完全相同的一组解决方案，但至少对于地面查询是确定的（因此不会留下任何无用的选择点）并省略（如果可能）任何多余的答案？

¹_{实际上，different([a|nonlist],[]), different([],[b|nonlist]) 成功了。它同样可能失败。因此，两者都失败的解决方案很好（甚至更好）。}

Answer 1

第一次尝试！

以下代码基于元谓词tfilter/3 and tpartition/4, the monotone if-then-else control construct if_/3, the reified unary logical connective not_t/3, and the reified term equality predicate (=)/3:

different([],[_|_]).
different([X|Xs0],Ys0) :-
   tpartition(=(X),Ys0,Es,Ys1),
   if_(Es=[], true, (tfilter(not_t(=(X)),Xs0,Xs1),different(Xs1,Ys1))).

示例查询：

?- different([A,B],[X,Y]).
                A=Y ,           dif(B,Y),     X=Y
;     A=X           ,     B=X           , dif(X,Y)
;     A=X           , dif(B,X), dif(B,Y), dif(X,Y)
;               A=Y ,               B=Y , dif(X,Y)
;               A=Y , dif(B,X), dif(B,Y), dif(X,Y)
; dif(A,X), dif(A,Y).

让我们在处理地面数据时观察确定性：

?- different([5,4],[1,2]).
true.

上述方法感觉像是朝着正确方向迈出的一步……但是，就目前的情况而言，我不会称之为完美。

Answer 2

再试一次！我们利用单调的 if-then-else 控制结构 if_/3, in combination with the reified list membership predicate memberd_t/3 和第一个参数索引来避免创建无用的选择点。

different(Xs,Ys) :-
   different_aux(Xs,Ys,Xs,Ys).

different_aux([],[_|_],Xs0,Ys0) :-
   different_aux(Ys0,[],Ys0,Xs0).     % swap Xs/Ys pair
different_aux([X|Xs],Ys,Xs0,Ys0) :-
   if_(memberd_t(X,Ys0),
       different_aux(Ys,Xs,Ys0,Xs0),  % variant: different_aux(Xs,Ys,Xs0,Ys0)
       true).

首先，我们运行一个我们预计会失败的查询:

?- different([1,2,3],[2,3,1]).
false.

以下查询与上面给出的失败查询类似；每个人都有一个 "different" 项目 x 放置在第一个 [1,2,3] 或第二个列表 [2,3,1]:

中的不同索引处

?- different([4,2,3],[2,3,1]), different([1,2,3],[4,3,1]),
   different([1,4,3],[2,3,1]), different([1,2,3],[2,4,1]),
   different([1,2,4],[2,3,1]), different([1,2,3],[2,3,4]).
true.                                 % all subgoals succeed deterministically

OK！ 让我们运行另一个（非常一般的）查询，我在我的 :

?- different([A,B],[X,Y]).
      A=X ,               B=X , dif(Y,X)
;     A=X ,           dif(B,X), dif(Y,B)
;               A=Y , dif(B,X), dif(Y,X)
; dif(A,X), dif(A,Y).

紧凑！比我介绍的有很大改进 !

Answer 3

返璞归真！此变体 非常接近 OP 在问题中给出的代码。

以下内容基于if_/3 and memberd_t/3.

different(Xs,Ys) :-
   if_(some_absent_t(Xs,Ys),
       true,
       some_absent_t(Ys,Xs,true)).

some_absent_t([]    ,_ ,false).
some_absent_t([X|Xs],Ys,Truth) :-
   if_(memberd_t(X,Ys), some_absent_t(Xs,Ys,Truth), Truth=true).

这是一个地面查询：

?- different([4,2,3],[2,3,1]), different([1,2,3],[4,3,1]),
   different([1,4,3],[2,3,1]), different([1,2,3],[2,4,1]),
   different([1,2,4],[2,3,1]), different([1,2,3],[2,3,4]).
true.                                 % all subgoals succeed deterministically

这是我在之前的回答中使用的（更一般的）查询：

?- different([A,B],[X,Y]).
      A=X ,               B=X ,           dif(Y,X)
;     A=X ,           dif(B,X), dif(B,Y)
;               A=Y ,               B=Y , dif(Y,X), dif(Y,X)
;               A=Y , dif(B,X), dif(B,Y), dif(Y,X)
; dif(A,X), dif(A,Y).

Answer 4

(受@repeat的[=11=启发很大，名字还是太笨拙了)

different(Xs, Ys) :-
   if_(tnotexists_inlist_t(list_memberd_t(Ys), Xs),
      true,
      tnotexists_inlist_t(list_memberd_t(Xs), Ys)).

tnotexists_inlist_t(_P_2, [], false).
tnotexists_inlist_t(P_2, [E|Es], T) :-
   if_(call(P_2, E),
      tnotexists_inlist_t(P_2, Es, T),
      T = true).

Answer 5

下一位代码选美选手！-)

此答案显示了代码的重构变体。它使用具体化的合取和析取：

and_(P_1,Q_1) :-
   and_t(P_1,Q_1,true).

or_(P_1,Q_1) :-
   or_t(P_1,Q_1,true).

and_t(P_1,Q_1,Truth) :-
   if_(P_1, call(Q_1,Truth), Truth=false).

or_t(P_1,Q_1,Truth) :-
   if_(P_1, Truth=true, call(Q_1,Truth)).

注意 "and" 和 "or" 的两个版本；后缀 _t 的有一个额外的真值参数，没有后缀的没有并假设 Truth=true 应该成立。

基于and_t/3和具体化的不等式谓词dif/3，我们定义nonmember_t/3:

nonmember_t(X,Ys,Truth) :-
   list_nonmember_t(Ys,X,Truth).

list_nonmember_t([]    ,_, true).
list_nonmember_t([Y|Ys],X,Truth) :-
   and_t(dif(X,Y), list_nonmember_t(Ys,X), Truth).

现在，让我们定义 some_absent_t/3、different_t/3 和 different/2，如下所示：

some_absent_t([]    ,_ ,false).
some_absent_t([X|Xs],Ys,Truth) :-
   or_t(nonmember_t(X,Ys), some_absent_t(Xs,Ys), Truth).

different_t(Xs,Ys,Truth) :-
   or_t(some_absent_t(Xs,Ys),
        some_absent_t(Ys,Xs),
        Truth).

different(Xs,Ys) :-
   different_t(Xs,Ys,true).

还运行吗?

?- different([A,B],[X,Y]).
      A=X ,               B=X ,           dif(Y,X)
;     A=X ,           dif(B,X), dif(B,Y)
;               A=Y ,               B=Y , dif(Y,X), dif(Y,X)
;               A=Y , dif(B,X), dif(B,Y), dif(Y,X)
; dif(A,X), dif(A,Y).                     % same result as before

?- different([4,2,3],[2,3,1]), different([1,2,3],[4,3,1]),
   different([1,4,3],[2,3,1]), different([1,2,3],[2,4,1]),
   different([1,2,4],[2,3,1]), different([1,2,3],[2,3,4]).
true.                                    % same result as before

看起来还好！

总而言之，与现有答案相比并没有太大的改进，但 IMO 的代码更具可读性，并且 different/2 的具体化版本作为额外奖励！

Answer 6

在, exists_in_t/3的帮助下，让我们把它发挥到极致---和 !

some_absent_t(Xs,Ys,Truth) :-
   exists_in_t(list_nonmember_t(Ys),Xs,Truth).

different(Xs,Ys) :-
   or_(some_absent_t(Xs,Ys),
       some_absent_t(Ys,Xs)).

Answer 7

不久前提供了以下大胆赏金 (+500)：

^{An idiomatic answer is still missing here. For example, or_t/3 should rather be (;)/3. There is more to it.}

已接受挑战！ 此答案是 .

的跟进

我们使用具体化的逻辑连接词(;)/<b>3</b>，可以这样定义：
```
';'(P_1,Q_1,T) :- if_(P_1, T=true, call(Q_1,T)).
```
接下来，我们定义meta-predicatecall_/1。它对于此答案中使用的具体化谓词很有用。 call_/1 的名称和语义遵循 if_/3、and_/2 和 or_/2!
```
call_(P_1) :- call(P_1,true).
```

使用 (;)/3、call_/1 和我们实现 different/2:

different(As,Bs) :- call_((some_absent_t(As,Bs) ; some_absent_t(Bs,As))).

完成！就是这样。

让我们重新[=64=]我们在之前答案中使用的查询！

^{?- different([5,4],[1,2]).
true.

?- different([1,2,3],[2,3,1]).
false.

?- different([4,2,3],[2,3,1]), different([1,4,3],[2,3,1]), different([1,2,4],[2,3,1]),
   different([1,2,3],[4,3,1]), different([1,2,3],[2,4,1]), different([1,2,3],[2,3,4]).
true.}

相同的查询，相同的答案...在我看来[=44=]还好！

Answer 8

使用 if_, I would say an alternative approach would be to use constructive negation from the beginning. Constructive negation 的 Conerning 解决方案早在 80 年代就已被研究出来，先驱是 David Chan，现在仍然时有出现。

假设我们有一个具有建设性否定的 Prolog 解释器 (~)/2。这个建设性的否定 (~)/2 可以用来定义一个声明式的 if-then-else 如下，我们称这个运算符为 (~->)/2:

  (A ~-> B; C) :- (A, B); (~A, C).

如果 Prolog 解释器除了建设性否定之外还嵌入了蕴涵 (=>)/2，那么也可以定义一个声明性的 if-then-else，如下所示，我们称此运算符为 (~=>)/2:

  (A ~=> B; C) :- (A => B), (~A => C).

注意从析取 (;)/2 到合取 (,)/2 的转换。问二元决策图 (BDD) 的人为什么他们在逻辑上是等价的。程序上有细微差别，但通过某些 A 的嵌入蕴涵后门，第二个 if-then-else 变体也会引入非确定性。

但是我们将如何着手并在 Prolog 解释器中引入例如建设性否定。一种直接的方法是将建设性否定委托给约束求解器。如果约束求解器具有具体化否定，则可以按如下方式完成：

 ~ A :- #\ A.

但是周围没有那么多约束求解器，可以合理地使用 member/2 等示例。因为它们通常只为有限整数、有理数等域提供具体化的否定。 . 但是对于像 member/2 这样的谓词，我们需要对 Herbrand 宇宙进行具体化否定。

另请注意，建设性否定的常用方法还假设普通规则蕴涵得到另一种解读。这意味着通常在建设性否定下，我们可以选择普通的 member/2 定义，并得到查询结果，例如：

?- ~ member(X, [a,b,c]).
dif(X, a),
dif(X, b),
dif(X, c).

但是具体化的否定很难与定义的谓词一起工作，所以下面的查询可能不会工作：

?- #\ member(X, [a,b,c]).
/* typically won't work */

如果上述成功，则任何声明性的 if-then-else（例如 (~->)/2 或 (~=>)/2 的使用频率都会降低，因为普通的谓词定义已经通过 Prolog 提供了声明性解释口译员。但为什么建设性的否定没有广泛传播？一个原因可能是这种 Prolog 解释器的大型设计 space。我注意到我们会有以下选项：

后向链接： 我们基本上会将原始解释器 solve/1 分解为两个谓词 solvep/1 和 solven/1。 solvep/1负责解决正目标，solven/1负责解决负目标。当我们尝试这个时，我们迟早会发现我们需要更仔细地处理量词，并且可能最终会采用 Herbrand 域的量词消除方法。

正向链接：我们还会注意到，在反向链接中，我们将运行转化为头部带有析取或存在量词的子句建模问题。这与适用于 Prolog 的后续演算在右侧只有一个公式这一事实有关。因此，要么我们在右侧使用多公式并会松散副一致性，要么我们使用前向链接。

魔法集： 但是正向链接会以不受控制的方式污染解决方案 spaces。所以我们可能需要某种形式的前向和后向链接的组合。我的意思不仅如此，我们应该能够在解决方案过程中在两者之间动态切换，但我的意思是我们还需要一种方法来生成指导前向链接过程的集合。

此答案中还指出了更多问题 here。这并不意味着迟早会找到一个公式来将所有这些问题和解决方案配对在一起，但这可能需要更多时间。

再见

different/2 - 是否存在一个纯粹的、确定的定义？

different/2 - does a pure, determinate definition exist?

prolog

prolog-dif

logical-purity