如何为所有参数模式实现列表项删除？
How to implement list item deletion for all argument modes?
以下 Prolog 程序定义了一个谓词 deleted/3，用于从第二个参数传递的列表中删除第一个参数传递的项目的所有出现，并在第三个参数传递的列表中产生结果：
deleted(_, [], []).
deleted(X, [X|Y], Z) :-
deleted(X, Y, Z).
deleted(U, [V|W], [V|X]) :-
deleted(U, W, X),
U \= V.
- 它适用于此参数模式下的查询：
?- deleted(a, [a, b, a], [b]).
true
; false.
- 它也适用于此参数模式下的查询：
?- deleted(X, [a, b, a], [b]).
X = a
; false.
- 它也适用于此参数模式下的查询：
?- deleted(a, [a, b, a], Z).
Z = [b]
; false.
- 它也适用于此参数模式下的查询：
?- deleted(X, [a, b, a], Z).
X = a, Z = [b]
; X = b, Z = [a, a]
; false.
- 它也适用于此参数模式下的查询：
?- deleted(a, Y, Z).
Y = Z, Z = []
; Y = [a], Z = []
; Y = [a, a], Z = []
; Y = [a, a, a], Z = []
; Y = [a, a, a, a], Z = []
; …
- 它也适用于此参数模式下的查询：
?- deleted(X, Y, Z).
Y = Z, Z = []
; Y = [X], Z = []
; Y = [X, X], Z = []
; Y = [X, X, X], Z = []
; Y = [X, X, X, X], Z = []
; …
- 但是在这种参数模式下查询会耗尽资源:
?- deleted(a, Y, [b]).
Stack limit (0.2Gb) exceeded
Stack sizes: local: 0.2Gb, global: 28.1Mb, trail: 9.3Mb
Stack depth: 1,225,203, last-call: 0%, Choice points: 1,225,183
Possible non-terminating recursion:
[1,225,203] deleted(a, _1542, [length:1])
[1,225,202] deleted(a, [length:1|_1584], [length:1])
- 它还会用这种参数模式的查询耗尽资源：
?- deleted(X, Y, [b]).
Stack limit (0.2Gb) exceeded
Stack sizes: local: 0.2Gb, global: 28.1Mb, trail: 9.3Mb
Stack depth: 1,225,179, last-call: 0%, Choice points: 1,225,159
Possible non-terminating recursion:
[1,225,179] deleted(_1562, _1564, [length:1])
[1,225,178] deleted(_1596, [length:1|_1606], [length:1])
如何实现所有参数模式的列表项删除？
简介
纯 Prolog 的合取和析取 是 ，实际上是交换和结合的。
这允许我们忽略子句和目标顺序，前提是 所有 答案序列是 有限.
当查询有无限的解集时，Prolog 可能需要系统地枚举 个无限的答案序列。
修复
为了帮助 Prolog 找到上述“有问题的”查询的答案，交换两个递归规则：
deleted(_,[],[]).
deleted(U,[V|W],[V|X]) :- % this clause was last
dif(U,V),
deleted(U,W,X).
deleted(X,[X|Y],Z) :-
deleted(X,Y,Z).
演示
让我们 运行 您的查询 再次 并更改上述代码！
finite 和以前一样工作1:
?- deleted(a,[a,b,a],[b]). % Q1
true
; false.
?- deleted(X,[a,b,a],[b]). % Q2
X = a
; false.
?- deleted(a,[a,b,a],Z). % Q3
Z = [b]
; false.
?- deleted(X,[a,b,a],Z). % Q4
Z = [a,b,a], dif(X,a), dif(X,b)
; Z = [a, a], X=b
; Z = [ b ], X=a
; false.
一些 infinite 以前没问题——他们 仍然 是：
?- deleted(a,Y,Z). % Q5
Y = Z, Z = []
; Y = Z, Z = [_A], dif(_A,a)
; Y = Z, Z = [_A,_B], dif(_A,a), dif(_B,a)
; Y = Z, Z = [_A,_B,_C], dif(_A,a), dif(_B,a), dif(_C,a)
; …
?- deleted(X,Y,Z). % Q6
Y = Z, Z = []
; Y = Z, Z = [_A], dif(X,_A)
; Y = Z, Z = [_A,_B], dif(X,_A), dif(X,_B)
; Y = Z, Z = [_A,_B,_C], dif(X,_A), dif(X,_B), dif(X,_C)
; …
一些 infinite 曾经是“有问题的”——现在不是了：
?- deleted(a,Y,[b]). % Q7
Y = [b]
; Y = [b,a]
; Y = [b,a,a]
; Y = [b,a,a,a]
; …
?- deleted(X,Y,[b]). % Q8
Y = [b], dif(X,b)
; Y = [b,X], dif(X,b)
; Y = [b,X,X], dif(X,b)
; Y = [b,X,X,X], dif(X,b)
; Y = [b,X,X,X,X], dif(X,b)
; …
分析
现在，?- deleted(X,Y,[b]). 让 Prolog 给我们答案。
但为什么我们运行 out-of-memory？
怎么没用？
为了解释这一点，让我们退后一步：许多2 Prolog系统的默认/香草/开箱即用prolog-toplevel最初运行s 每个查询，直到它发现或者 (0) finite failure or (1) 第一个回答3.
在修复之前，我们观察到两者都没有。为什么不呢？
为什么没有有限失败？
deleted(a,[a,b,a],[b])成立。
所以更一般 删除了(<b>X</b>,<b>Y</b> ,[b]) 绝不能失败。
为什么没有（第一个）回答？
Prolog 进行深度优先、自上而下、从左到右。
所以当……
?- deleted(X,Y,[b]).
…“遇见”…
deleted(X,[X|Y],Z) :-
deleted(X,Y,Z).
... 在 Prolog 机器内部，发生以下情况：
A choicepoint 被创建用于保存信息——回溯时使用——另一个子句可能有已被选中。
接下来，Prolog 继续执行递归目标，这与最初的目标一样：我们离答案还差得远，因为第三个论点—— 仅实例化了一个——保持完全相同。
最终，此循环 运行 内存不足 — 这正是您观察到的行为。
如果我们交换两个递归子句，以下子句将成为我们最顶层的递归子句：
deleted(U,[V|W],[V|X]) :-
dif(U,V),
deleted(U,W,X).
现在，是第三个参数：Prolog 递归遍历单链表，直到到达 []（或自由逻辑变量） .只有这样 Prolog 才能利用事实 deleted(_,[],[]). 给我们一个答案。
脚注:
实际上更好，因为我们通过使用dif/2来表达句法术语不等式来保留logical-purity。
关于 dif/2 的更多信息：prolog-dif
我使用过的所有基于 command-line-interface 的 Prolog 系统。
Not 在第一个答案处停止对于代码质量来说更好——特别是在通用终止属性方面。
GUPU, an excellent environment specialized for Prolog and constraint programming courses，做正确的事——默认！
以下 Prolog 程序定义了一个谓词 deleted/3，用于从第二个参数传递的列表中删除第一个参数传递的项目的所有出现，并在第三个参数传递的列表中产生结果：
deleted(_, [], []).
deleted(X, [X|Y], Z) :-
deleted(X, Y, Z).
deleted(U, [V|W], [V|X]) :-
deleted(U, W, X),
U \= V.
- 它适用于此参数模式下的查询：
?- deleted(a, [a, b, a], [b]).
true
; false.
- 它也适用于此参数模式下的查询：
?- deleted(X, [a, b, a], [b]).
X = a
; false.
- 它也适用于此参数模式下的查询：
?- deleted(a, [a, b, a], Z).
Z = [b]
; false.
- 它也适用于此参数模式下的查询：
?- deleted(X, [a, b, a], Z).
X = a, Z = [b]
; X = b, Z = [a, a]
; false.
- 它也适用于此参数模式下的查询：
?- deleted(a, Y, Z).
Y = Z, Z = []
; Y = [a], Z = []
; Y = [a, a], Z = []
; Y = [a, a, a], Z = []
; Y = [a, a, a, a], Z = []
; …
- 它也适用于此参数模式下的查询：
?- deleted(X, Y, Z).
Y = Z, Z = []
; Y = [X], Z = []
; Y = [X, X], Z = []
; Y = [X, X, X], Z = []
; Y = [X, X, X, X], Z = []
; …
- 但是在这种参数模式下查询会耗尽资源:
?- deleted(a, Y, [b]).
Stack limit (0.2Gb) exceeded
Stack sizes: local: 0.2Gb, global: 28.1Mb, trail: 9.3Mb
Stack depth: 1,225,203, last-call: 0%, Choice points: 1,225,183
Possible non-terminating recursion:
[1,225,203] deleted(a, _1542, [length:1])
[1,225,202] deleted(a, [length:1|_1584], [length:1])
- 它还会用这种参数模式的查询耗尽资源：
?- deleted(X, Y, [b]).
Stack limit (0.2Gb) exceeded
Stack sizes: local: 0.2Gb, global: 28.1Mb, trail: 9.3Mb
Stack depth: 1,225,179, last-call: 0%, Choice points: 1,225,159
Possible non-terminating recursion:
[1,225,179] deleted(_1562, _1564, [length:1])
[1,225,178] deleted(_1596, [length:1|_1606], [length:1])
如何实现所有参数模式的列表项删除？
简介
纯 Prolog 的合取和析取 是 ，实际上是交换和结合的。
这允许我们忽略子句和目标顺序，前提是 所有 答案序列是 有限.
当查询有无限的解集时，Prolog 可能需要系统地枚举 个无限的答案序列。
修复
为了帮助 Prolog 找到上述“有问题的”查询的答案，交换两个递归规则：
deleted(_,[],[]). deleted(U,[V|W],[V|X]) :- % this clause was last dif(U,V), deleted(U,W,X). deleted(X,[X|Y],Z) :- deleted(X,Y,Z).
演示
让我们 运行 您的查询 再次 并更改上述代码！
finite 和以前一样工作1:
?- deleted(a,[a,b,a],[b]). % Q1 true ; false. ?- deleted(X,[a,b,a],[b]). % Q2 X = a ; false. ?- deleted(a,[a,b,a],Z). % Q3 Z = [b] ; false. ?- deleted(X,[a,b,a],Z). % Q4 Z = [a,b,a], dif(X,a), dif(X,b) ; Z = [a, a], X=b ; Z = [ b ], X=a ; false.
一些 infinite 以前没问题——他们 仍然 是：
?- deleted(a,Y,Z). % Q5 Y = Z, Z = [] ; Y = Z, Z = [_A], dif(_A,a) ; Y = Z, Z = [_A,_B], dif(_A,a), dif(_B,a) ; Y = Z, Z = [_A,_B,_C], dif(_A,a), dif(_B,a), dif(_C,a) ; … ?- deleted(X,Y,Z). % Q6 Y = Z, Z = [] ; Y = Z, Z = [_A], dif(X,_A) ; Y = Z, Z = [_A,_B], dif(X,_A), dif(X,_B) ; Y = Z, Z = [_A,_B,_C], dif(X,_A), dif(X,_B), dif(X,_C) ; …
一些 infinite 曾经是“有问题的”——现在不是了：
?- deleted(a,Y,[b]). % Q7 Y = [b] ; Y = [b,a] ; Y = [b,a,a] ; Y = [b,a,a,a] ; … ?- deleted(X,Y,[b]). % Q8 Y = [b], dif(X,b) ; Y = [b,X], dif(X,b) ; Y = [b,X,X], dif(X,b) ; Y = [b,X,X,X], dif(X,b) ; Y = [b,X,X,X,X], dif(X,b) ; …
分析
现在，?- deleted(X,Y,[b]). 让 Prolog 给我们答案。
但为什么我们运行 out-of-memory？ 怎么没用？
为了解释这一点，让我们退后一步：许多2 Prolog系统的默认/香草/开箱即用prolog-toplevel最初运行s 每个查询，直到它发现或者 (0) finite failure or (1) 第一个回答3.
在修复之前，我们观察到两者都没有。为什么不呢？
为什么没有有限失败？
deleted(a,[a,b,a],[b])成立。所以更一般
删除了(<b>X</b>,<b>Y</b> ,[b])绝不能失败。为什么没有（第一个）回答？
Prolog 进行深度优先、自上而下、从左到右。
所以当……
?- deleted(X,Y,[b]).
…“遇见”…
deleted(X,[X|Y],Z) :- deleted(X,Y,Z).... 在 Prolog 机器内部，发生以下情况：
A choicepoint 被创建用于保存信息——回溯时使用——另一个子句可能有已被选中。
接下来，Prolog 继续执行递归目标，这与最初的目标一样：我们离答案还差得远，因为第三个论点—— 仅实例化了一个——保持完全相同。
最终，此循环 运行 内存不足 — 这正是您观察到的行为。
如果我们交换两个递归子句，以下子句将成为我们最顶层的递归子句：
deleted(U,[V|W],[V|X]) :- dif(U,V), deleted(U,W,X).
现在，是第三个参数：Prolog 递归遍历单链表，直到到达 []（或自由逻辑变量） .只有这样 Prolog 才能利用事实 deleted(_,[],[]). 给我们一个答案。
脚注:
实际上更好，因为我们通过使用
dif/2来表达句法术语不等式来保留logical-purity。关于
dif/2的更多信息：prolog-dif我使用过的所有基于 command-line-interface 的 Prolog 系统。
Not 在第一个答案处停止对于代码质量来说更好——特别是在通用终止属性方面。
GUPU, an excellent environment specialized for Prolog and constraint programming courses，做正确的事——默认！