19

memberchk/2是一个通常定义的谓词，其定义member/2如下：

memberchk(X, Xs) :-
   once(member(X, Xs)).

因此，它仅对 的第一个答案成功member/2。它的完整程序意义不适合纯粹的关系。作为其非关系行为的示例，请考虑

?- memberchk(b, [X,b]), X = a.
false.

?- X = a, memberchk(b, [X,b]).
X = a.

另一方面，在许多情况下，memberchk/2将使用充分实例化的参数来调用，在这种情况下，它可以被视为纯关系的有效近似。

背后的一个这样的纯关系是memberd/2（使用if_/3）：

memberd(E, [X|Xs]) :-
   if_(E = X, true, memberd(E, Xs) ).

memberchk/2对于充分实例化的情况，是否有任何其他纯关系可以近似？

换句话说：是memberd/2一个完整的、声明性的替换memberchk/2还是仍然存在memberchk/2不能被替换的合法情况memberd/2？

4

3 回答 3

5

这是一个众所周知的例子，member/2它不能用 来表示memberd/2：bridge.plPascal Van Hentenryck 给出的桥调度问题。

在设置阶段member/2使用：

setup(K,Ende,Disj):-
    jobs(L),
    make_vars(L,K),
    member([stop,_,Ende],K),
    ....

因此，在这里，三元素列表中的第一个元素实际上用于选择特定任务，而memberd/2使用整个元素进行比较。因此，这setup/3留下了很多选择点（实际上是 219 个）。一些（如 SICStus）memberchk/2在这种情况下使用，从而冒着非单调性的风险。

使用以下纯替换，可以避免所有选择点。

member3l([N,D,A], Plan) :-
   tmember(l3_t(N,D,A),  Plan).

l3_t(N,D,A, X, T) :-
   X = [Ni|_],
   if_(N = Ni, ( X=[N,D,A], T = true ), T = false ).

tmember(P_2, [X|Xs]) :-
   if_( call(P_2, X), true, tmember(P_2, Xs) ).

或者使用library(lambda)：

member3li([N,Nd,Na], Plan) :-
   tmember([N,Nd,Na]+\X^T^
       (  X=[Nk|_],
          if_( Nk = N, ( X=[N,Nd,Na], T = true ), T = false ) ),
      Plan).

其他用途tmember/2：

old_member(X, Xs) :-
   tmember( X+\E^T^( X = E, T = true ; T = false ), Xs).

old_memberd(X, Xs) :-
   tmember(=(X), Xs).

这是一个更紧凑的表示：

member3l([N,D,A], Plan) :-
   tmember({N,D,A}+\[Ni,Di,Ai]^cond_t(N = Ni, [D,A] = [Di,Ai] ), Plan).

使用library(lambda)和cond_t/3：

cond_t(If_1, Then_0, T) :-
   if_(If_1, ( Then_0, T = true ), T = false ).
于 2015-10-31T20:58:07.630 回答
3

memberb/2 是建设性否定的典型例子。您可以颠倒要求，例如要求：

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

其中 ~ 将是建设性的否定。有关建设性否定如何与 if_ 相关的讨论，请参见此处的示例。

对于 memberd/2 或类似的完全声明性归纳定义的缺点是 Prolog 析取 (;)/2 不能简化约束，并且 Prolog 没有一个 forall 也可以简化约束，例如 diff/2 .

因此，最终，当您使用 limited (;)/2 和 missig forall 正确执行此操作时，当您查看解释器将生成的完整解决方案集时，您会在最佳情况下获得包含大量冗余约束的完整解决方案。

这是 Jekejeke Prolog 中的一个示例，它需要 Minlog 扩展才能使谓词 dif/2 可用：

:- use_module(library(term/herbrand)).
:- use_module(library(basic/lists)).
test(Y) :- dif(X, a), member(Y, [a,X]).

?- test(X).
X = a,
dif(_A, a) ;
dif(X, a)

上述两个答案基本上说X = a或~(X = a)在大多数逻辑中与单个答案相同true。

你需要一个 Prolog 解释器，它在某些时候是面向集合的。可能还有一些运营商会强制进行面向集合的处理。但它可能会破坏传统的 Prolog 代码。您可能不能只是将完全声明性定义潜入基于非声明性定义的代码中。

再见

于 2015-10-31T21:07:50.273 回答
3

以下答案与有关的原始问题没有直接关系memberchk/2；相反，它是定义先前答案的后续。 tmember/2

我们建议像这样概括成语tmember/2：

t_non_empty_suffix(P_3, [X|Xs]) :-
   if_(call(P_3,Xs,X), true, t_non_empty_suffix(P_3,Xs)).

在Prolog lambdast_non_empty_suffix/2的基础上，我们可以这样定义：tmemberX/2

:- 使用模块（库（lambda））。

tmemberX(P_2, Xs) :-
   t_non_empty_suffix(P_2+\_^call(P_2), Xs)。

以下old_memberX/2并old_memberdX/2使用tmemberX/2代替tmember/2：

old_memberX(X, Xs) :-
   tmemberX(X+\E^T^( X = E, T = true ; T = false ), Xs).

old_memberdX(X, Xs) :-
   tmemberX(=(X), Xs).

old_member/2让我们比较old_memberX/2...

?- old_member(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 2 ; X = 3 ; X = 4 ; X = 3 ; X = 4 ; X = 5 ; false.

?- old_memberX(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 2 ; X = 3 ; X = 4 ; X = 3 ; X = 4 ; X = 5 ; false.

……然后old_memberd/2到old_memberdX/2！

?- old_memberd(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5 ; false.

?- old_memberdX(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5 ; false.

好的！如何定义old_member/old_memberd直接基于t_non_empty_suffix/2？

old_memberSFX(X, Xs) :-
   t_non_empty_suffix(X+\_^E^T^( X = E, T = true ; T = false ), Xs).

old_memberdSFX(X, Xs) :-
   t_non_empty_suffix(X+\_^E^( X = E ), Xs).

使用这些谓词运行上面的查询，我们得到：

?- old_memberSFX(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 2 ; X = 3 ; X = 4 ; X = 3 ; X = 4 ; X = 5 ; false.

?- old_memberdSFX(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5 ; false.

好吧！结果和以前一样。

让我们深入一点！作为t_non_empty_suffix/2考虑的展示案例duplicate_in/2。
使用t_non_empty_suffix/2, Prolog lambdas , (=)/3,memberd_t/3我们定义：

','(P_1, Q_1, T) :-
   if_(P_1, call(Q_1,T), T = false).

duplicate_in(X, Xs) :-
   t_non_empty_suffix(X+\Es^E^( X = E, memberd_t(E, Es) ), Xs).

示例查询：

?- 重复输入（X，[1,2,3,2,3,4,3,4,5]）。
  X = 2 % [1, 2 ,3, 2 ,3,4,3,4,5]（2 出现两次）
; X = 3 % [1,2, 3 ,2, 3 ,4, 3 ,4,5]（3 出现三次）
; X = 4 % [1,2,3,2,3, 4 ,3, 4 ,5]（4 出现两次）
; 错误的。
于 2015-11-02T11:34:38.720 回答