如何实现所有参数模式的列表项删除？

Question

以下 Prolog 程序定义了一个谓词，deleted/3用于从第二个参数中传递的列表中删除第一个参数中传递的所有出现的项目，并生成第三个参数中传递的列表：

\n

deleted(_, [], []).\ndeleted(X, [X|Y], Z) :-\n  deleted(X, Y, Z).\ndeleted(U, [V|W], [V|X]) :-\n  deleted(U, W, X),\n  U \\= V.\n

\n

\n
1. 它适用于此参数模式下的查询：
\n

\n

?- deleted(a, [a, b, a], [b]).\n   true\n;  false.\n

\n

\n
2. 它也适用于此参数模式下的查询：
\n

\n

?- deleted(X, [a, b, a], [b]).\n   X = a\n;  false.\n

\n

\n
3. 它也适用于此参数模式下的查询：
\n

\n

?- deleted(a, [a, b, a], Z).\n   Z = [b]\n;  false.\n

\n

\n
4. 它也适用于此参数模式下的查询：
\n

\n

?- deleted(X, [a, b, a], Z).\n   X = a, Z = [b]\n;  X = b, Z = [a, a]\n;  false.\n

\n

\n
5. 它也适用于此参数模式下的查询：
\n

\n

?- deleted(a, Y, Z).\n   Y = Z, Z = []\n;  Y = [a], Z = []\n;  Y = [a, a], Z = []\n;  Y = [a, a, a], Z = []\n;  Y = [a, a, a, a], Z = []\n;  \xe2\x80\xa6\n

\n

\n
6. 它也适用于此参数模式下的查询：
\n

\n

?- deleted(X, Y, Z).\n   Y = Z, Z = []\n;  Y = [X], Z = []\n;  Y = [X, X], Z = []\n;  Y = [X, X, X], Z = []\n;  Y = [X, X, X, X], Z = []\n;  \xe2\x80\xa6\n

\n

\n
7. 但在这种参数模式下查询会耗尽资源：
\n

\n

?- deleted(a, Y, [b]).\nStack limit (0.2Gb) exceeded\n  Stack sizes: local: 0.2Gb, global: 28.1Mb, trail: 9.3Mb\n  Stack depth: 1,225,203, last-call: 0%, Choice points: 1,225,183\n  Possible non-terminating recursion:\n    [1,225,203] deleted(a, _1542, [length:1])\n    [1,225,202] deleted(a, [length:1|_1584], [length:1])\n

\n

\n
8. 在这种参数模式下，它还会耗尽资源：
\n

\n

?- deleted(X, Y, [b]).\nStack limit (0.2Gb) exceeded\n  Stack sizes: local: 0.2Gb, global: 28.1Mb, trail: 9.3Mb\n  Stack depth: 1,225,179, last-call: 0%, Choice points: 1,225,159\n  Possible non-terminating recursion:\n    [1,225,179] deleted(_1562, _1564, [length:1])\n    [1,225,178] deleted(_1596, [length:1|_1606], [length:1])\n

\n

如何实现所有参数模式的列表项删除？

\n

Answer 1

介绍

\n

事实上，纯 Prolog 的合取和析取是可交换的和结合的。

\n

这允许我们忽略子句和目标顺序，前提是所有答案序列都是有限的。

\n

当查询具有无限解集时，Prolog 可能需要系统地枚举无限答案序列。

\n

修复

\n

为了帮助 Prolog 找到上述 \xe2\x80\x9cproblematic\xe2\x80\x9d 查询的答案，请交换两个递归规则：

\n

\ndeleted(_,[],[]).\ndeleted(U,[V|W],[V|X]) :- % 该子句最后\n diff(U,V),\n 已删除(U ,W,X)。\n删除(X,[X|Y],Z) :-\n 删除(X,Y,Z)。\n

\n

演示

\n

让\xe2\x80\x99s使用上述代码更改再次运行您的查询！

\n

有限的工作方式与之前¹一样：

\n

\n？- 已删除（a，[a，b，a]，[b]）。% Q1\n 正确\n; false。\n\n？- 已删除(X,[a,b,a],[b])。% Q2\n X = a\n; false。\n\n？- 已删除(a,[a,b,a],Z)。% Q3\n Z = [b]\n; false。\n\n？- 已删除(X,[a,b,a],Z)。% Q4\n Z = [a,b,a], dif(X,a), dif(X,b)\n; Z = [a, a], X=b\n; Z = [ b ], X=a\n; 错误。\n

\n

一些无限的在\xe2\x80\x94之前是可以的，但它们仍然是：

\n

\n？- 删除（a，Y，Z）。% Q5\n Y = Z, Z = []\n; Y = Z，Z = [_A]，dif(_A,a)\n; Y = Z, Z = [_A,_B], dif(_A,a), dif(_B,a)\n; Y = Z, Z = [_A,_B,_C], dif(_A,a), dif(_B,a), dif(_C,a)\n; \xe2\x80\xa6\n\n？- 已删除（X，Y，Z）。% Q6\n Y = Z, Z = []\n; Y = Z，Z = [_A]，dif(X,_A)\n; Y = Z, Z = [_A,_B], dif(X,_A), dif(X,_B) \n; Y = Z, Z = [_A,_B,_C], dif(X,_A), dif(X,_B), dif(X,_C)\n; \xe2\x80\xa6\n

\n

一些无限的曾经是 \xe2\x80\x9cproblematic\xe2\x80\x9d\xe2\x80\x94 不再是：

\n

\n？- 已删除（a，Y，[b]）。% Q7\n Y = [b]\n; Y = [b,a]\n; Y = [b,a,a]\n; Y = [b,a,a,a]\n; \xe2\x80\xa6\n\n？- 已删除（X，Y，[b]）。% Q8\n Y = [b], dif(X,b)\n; Y = [b,X], dif(X,b)\n; Y = [b,X,X], dif(X,b)\n; Y = [b,X,X,X], dif(X,b)\n; Y = [b,X,X,X,X], dif(X,b)\n; \xe2\x80\xa6\n

\n

分析

\n

现在，?- deleted(X,Y,[b]).让Prolog给我们答案。

\n

但为什么我们会出现内存不足的情况？\n为什么它不起作用？

\n

为了解释这一点，让\xe2\x80\x99s 退后一步：许多² Prolog 系统的默认/普通/开箱即用的prolog-toplevel最初运行每个查询，直到发现(0)有限故障或(1)第一个答案³ .

\n

在修复之前，我们没有观察到任何情况。为什么不？

\n

\n

0. 为什么没有有限失败？

   \n

   deleted(a,[a,b,a],[b])确实如此。

   \n

   所以，越通用 一定不能失败。deleted(X,Y,[b])

   \n
\n

1. 为什么没有（第一个）答案？

   \n

   Prolog 按照深度优先、自上而下、从左到右的顺序进行。

   \n

   所以当\xe2\x80\xa6

   \n

       ?- 删除(X,Y, [b] )。

   \n

   \xe2\x80\xa6 \xe2\x80\x9cmeets\xe2\x80\x9d \xe2\x80\xa6

   \n

       已删除(X,[X|Y], Z ) :-\n 已删除(X,Y, Z )。

   \n

   \xe2\x80\xa6 在 Prolog 机器内，会发生以下情况：

   \n
   \n

   • 创建选择点用于保存信息\xe2\x80\x94，以便在回溯\xe2\x80\x94 时使用另一个子句可能已被选择的信息。

     \n
   \n

   • 接下来，Prolog 继续执行一个与原始目标一样的递归目标：我们距离答案还很远，因为第三个参数\xe2\x80\x94 （唯一实例化的一个\xe2\x80\x94）保持完全相同。

     \n
   \n
   \n

   最终，这个循环耗尽了内存\xe2\x80\x94，这正是您观察到的行为。

   \n
\n

\n

如果我们交换两个递归子句，则以下子句将成为最顶层的递归子句：

\n

\n已删除(U,[V|W], [V|X] ) :-\n dif(U, V ),\n 已删除(U,W, X )。\n

\n

现在，第三个参数发生了一些事情： Prolog 递归地沿着单链表走下去，直到[]到达（或一个自由逻辑变量）。只有这样，Prolog 才能利用这一事实deleted(_,[],[]).，给我们一个答案。

\n\n

脚注：

\n

\n

1. 事实上更好，因为我们通过使用表达句法术语不等式来保持逻辑纯度。dif/2

   \n

   更多关于dif/2：prolog-dif

   \n
\n

2. 我用过的所有基于命令行界面的 Prolog 系统。

   \n
\n

3. 不停止在第一个答案对于代码质量\xe2\x80\x94 特别是在通用终止属性方面要好得多。

   \n

   GUPU是一个专门用于 Prolog 和约束编程课程的优秀环境，默认情况下会做正确的事情\xe2\x80\x94 ！

   \n

   \xe2\x80\x9c答案替换以五个 为一组显示。\xe2\x80\x9d

   \n
\n

\n