list - 如果直接插入，为什么 Prolog 会将变量与失败的结果匹配？

Question

我正在制作一个 Prolog 程序，用于查找一组列表的子集。该子集必须符合某些特定条件，其中一个方面是子集的列表不能相同。令我困惑的是，当我尝试查找变量 X 的匹配项时，如果我将它们插入查询中代替 X，它会生成返回 false 的结果。例如:

?- containsSet(2, [[3],[7],[7]], X).
X = [[3], [7]] ;
X = [[3], [7]] ;
X = [[7], [7]] ;
false.

?- containsSet(2, [[3],[7],[7]], [[7],[7]]).
false.

如果直接插入时返回 false，它怎么可能将 X 与 [[7], [7]] 匹配？

containsSet 的想法是找到一个长度为 N(在本例中为 2)的列表子集，该子集在匹配位置没有匹配元素(即子集中没有两个列表具有相同的第一个元素，或相同的第二个元素等) .在上面的例子中，[7] 和 [7] 的第一个(也是唯一一个)元素匹配，所以它返回 false。

Answer 1

首先，祝贺我在初学者的问题中看到的最具声明性和合理性的观察之一!

一方面，合取在逻辑上是可交换的，这是最基本和众所周知的性质之一。另一方面，许多 Prolog 初学者没有意识到使用非单调谓词之一，如 (\+)/1几乎总是会破坏这样的基本不变量。您注意到这里发生了一些非常出乎意料的事情，您期望 Prolog 有更正确的行为是正确的。幸运的是，这些问题的声明式解决方案现在比以往任何时候都更广泛地在 Prolog 系统中传播。

首先，考虑一下使用(\+)/1会很快出现的一些问题。在您的程序中:

?- X = d, \+ member(X, [a,b,c]).
X = d.

yet, if we simply exchange the goals by commutativity of conjunction, we get the different answer:

?-  \+ member(X, [a,b,c]), X = d.
false.

This shows that (\+)/1 is not monotonic: It can cause a more general query to fail although a more specific query yields solutions:

?-  \+ member(X, [a,b,c]).
false.

?- \+ member(d, [a,b,c]).
true.

Thus, non-monotonic predicates cause all kinds of impurities and violate declarative semantics. Declaratively, knowing that there are solutions, we certainly expect the more general query to succeed, but it fails.

In this concrete, to specify that a term is different from all other terms in a list, use the constraint dif/2. dif/2 works in all directions, and yields correct answers also if its arguments are variables. For example:

not_member(X, Ls) :- maplist(dif(X), Ls).

这个定义保留了合取的交换性，正如我们对纯逻辑关系的深切渴望和实际期望:

?- not_member(X, [a,b,c]), X = d。
X = d。

?- X = d, not_member(X, [a,b,c])。
X = d。

自 not_member/2只使用纯谓词，你已经确保 - 已经通过构造 - 它只给出声明性的正确答案。

为了对你的代码进行声明式推理，我对你的方法表示赞赏，我建议你留在 Prolog 的纯单调子集中。见 logical-purity和 prolog-dif想要查询更多的信息。