4

我正在制作一个 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。

4

1 回答 1

3

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

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

(\+)/1首先，考虑一下如果你在你的程序中使用很快就会出现的一些问题：

?- X = d, \+ 成员(X, [a,b,c])。
X = d。

然而，如果我们简单地通过合取的交换性来交换目标，我们会得到不同的答案：

?- \+ 成员(X, [a,b,c]), X = d。
假的。

这表明这不是(\+)/1单调的：它可能导致更一般的查询失败，尽管更具体的查询会产生解决方案：

?- \+ 成员（X，[a，b，c]）。
假的。

?- \+ 成员（d，[a，b，c]）。
真的。

因此，非单调谓词会导致各种杂质并违反声明性语义。声明式地，知道有解决方案，我们当然希望更一般的查询成功，但它失败了。

具体而言，要指定一个术语与列表中的所有其他术语不同，请使用约束 dif/2。dif/2在所有方向上都有效，并且如果它的参数是变量，也会产生正确的答案。例如：

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 的纯单调子集中。有关详细信息，请参阅和。

于 2015-10-17T08:25:45.967 回答