让我们重新措辞一下:由于您想在多个实例化模式中使用谓词“一个给定值和列表的过程,它会删除列表中该值的所有出现”并没有定义它应该如何表现在其他情况下。因此,我们可能想要类似“如果第二个和第三个参数是列表 L1、L2 和 L1 与 L2 相同的列表,如果我们忽略第一个参数的所有出现,则谓词为真”
现在,有两种方法可以编写具有多个可能实例化的谓词;您可以使用元逻辑谓词,例如var/1
andground/1
并为每个谓词编写代码(这可能允许您编写针对特定实例优化的代码)或编写逻辑定义属性的代码(这可能更具挑战性)。
在这种情况下,我们可以这样做:
del(_, [], []).
del(X, [X|L1], L2):-
del(X,L1,L2).
del(X, [H|L1], [H|L2]):-
X\==H,
del(X,L1,L2).
它具有以下行为:
19 ?- del(1, [1,2,3], X).
X = [2, 3] ;
false.
1,2,3,
20 ?- del(1, [1,2,3], [2,3]).
true ;
false.
21 ?- del(X, [1,2,3], [2,3]).
X = 1 ;
false.
22 ?- del(X, [1,2,3], Y).
X = 1,
Y = [2, 3] ;
X = 2,
Y = [1, 3] ;
X = 3,
Y = [1, 2] ;
Y = [1, 2, 3] ;
false.
23 ?- del(X, P, Y).
P = Y, Y = [] ;
P = [X],
Y = [] ;
P = [X, X],
Y = [] ;
P = [X, X, X],
Y = [] ;
P = [X, X, X, X],
Y = [] ;
P = [X, X, X, X, X],
Y = [] ;
P = [X, X, X, X, X, X],
Y = [] .
关于最后一次通话;prolog 返回一个由于使用深度优先算法而增长的 X 列表;通过使用length/2
我们可以得到广度优先的结果(_G 表示变量没有被实例化(它可以是任何东西)):
24 ?- length(P,N), del(X, P, Y).
P = [],
N = 0,
Y = [] ;
P = [X],
N = 1,
Y = [] ;
P = [_G548],
N = 1,
Y = [_G548] ;
P = [X, X],
N = 2,
Y = [] ;
P = [X, _G551],
N = 2,
Y = [_G551] ;
P = [_G548, X],
N = 2,
Y = [_G548] ;
P = [_G548, _G551],
N = 2,
Y = [_G548, _G551] ;
P = [X, X, X],
编辑:正如@chac 指出的那样,如果第一个列表(至少)有一个重复元素,则上述谓词的行为不正确:
?- del(X,[1,2,1],Y).
X = 1,
Y = [2] ;
X = 2,
Y = [1, 1] ;
X = 1,
Y = [1, 2] ; <----- wrong
Y = [1, 2, 1].
这是因为实际上\==/2
并\=/2
没有对变量施加限制。这可以通过切换第三条中的规则顺序来解决:
del(_, [], []).
del(X, [X|L1], L2):-
del(X,L1,L2).
del(X, [H|L1], [H|L2]):-
del(X,L1,L2),
X\==H.
4 ?- del(X,[1,2,1],Y).
X = 1,
Y = [2] ;
X = 2,
Y = [1, 1] ;
Y = [1, 2, 1] ;
false.
然而,这意味着谓词不再是尾递归的。为了解决这个问题,我们可以保留 X 不应该是的值的列表:
del(X,L1,L2):-
del(X,L1,L2,[]).
del(X, [], [], NotX):-
\+ member(X,NotX).
del(X, [X|L1], L2, NotX):-
del(X,L1,L2,NotX).
del(X, [H|L1], [H|L2], NotX):-
X\==H, % <--- optional; stops the execution earlier (saving time)
del(X,L1,L2,[H|NotX]).
但是,根据以下内容,尾递归版本实际上更慢:
?-time(forall((between(1,50,N),length(X,N),del2(1,X,[2,3,2,3])),true)).
% 25,600,793 inferences, 5.468 CPU in 5.548 seconds (99% CPU, 4682134 Lips)
true.
?- time(forall((between(1,50,N),length(X,N),del_tr(1,X,[2,3,2,3])),true)).
% 37,346,143 inferences, 6.426 CPU in 6.428 seconds (100% CPU, 5811563 Lips)
true.
仍然, + - + 不起作用(它陷入无限循环)。但为什么?问题在于子句的顺序:del(1, L1, [2]) 将首先应用将 X “添加”到 L1 头部的规则,然后永远应用相同的规则。这可以通过使用 (again) 来解决length/2
:
?- length(X,2), del(1,X,[2]).
X = [1, 2] ;
X = [2, 1] ;
false.
或者,我们可以更改子句的顺序:
del(_, [], []).
del(X, [H|L1], [H|L2]):-
X\==H,
del(X,L1,L2),
X\==H.
del(X, [X|L1], L2):-
del(X,L1,L2).
但length/2
可能再次有用,因为没有它 prolog 会进行深度优先搜索:
?- del(1,X,[2]).
X = [2] ;
X = [2, 1] ;
X = [2, 1, 1] ;
X = [2, 1, 1, 1] ;
X = [2, 1, 1, 1, 1] ;
X = [2, 1, 1, 1, 1, 1] ;
X = [2, 1, 1, 1, 1, 1, 1]
当然length/2
可以合并到包装谓词中,因为它不会影响其他实例化模式。