为什么使用 [H|T] 作为参数而不是普通变量会导致我的谓词失败？

Question

我正在创建一个谓词以从列表中删除指定的元素，因此如果 Ys 是删除所有出现的结果，则 remove(Xs,X,Ys) 应该成立来自 Xs 的 X。我最初的失败谓词如下所示：

remove([],_,[]).
remove([H1|T1],H1,[H2|T2]) :- % e.g. [2,3] , 2, [3]
   remove(T1,H1,[H2|T2]).     % remove first head -> [3], 2, [3]
remove([H1|T1],Y,[H1|T2]) :-  % heads match e.g. [1,2,3], 2, [1,3]
   H1\==Y,
   remove(T1,Y,T2).           % remove heads -> [2,3], 2, [3]

这是失败的，但后来我注意到我有一个多余的 [H2|Y2]，我可以在其中使用一个变量，例如Ys。我进行此更改时认为它仍然会失败，但它开始工作了。工作代码如下所示：

remove([],_,[]).
remove([H1|T1],H1,Ys) :-      % e.g. [2,3] , 2, [3]
   remove(T1,H1,Ys).          % remove first head -> [3], 2, [3]
remove([H1|T1],Y,[H1|T2]) :-  % heads match e.g. [1,2,3], 2, [1,3]
   H1\==Y,
   remove(T1,Y,T2).           % remove heads -> [2,3], 2, [3]

有人可以解释一下为什么将 [H2|T2] 更改为 Ys 会成功吗？

Answer 1

在查询进程的某处，模式 remove([H|T], H, []) 即将出现，它将与第二个版本的第二个子句 remove([H1|T1], H1, Ys) 的头部相匹配，但不会与头部相匹配您的第一个版本的第二个子句 remove([H1|T1], H1, [H2|T2]).

如果您运行跟踪查询，remove([1, 2, 3, 2], 2, [1, 3]) 使用您的第一个程序版本，您会得到：

   Call: (6) remove([1, 2, 3, 2], 2, [1, 3]) ? creep
   Call: (7) 1\==2 ? creep
   Exit: (7) 1\==2 ? creep
   Call: (7) remove([2, 3, 2], 2, [3]) ? creep
   Call: (8) remove([3, 2], 2, [3]) ? creep
   Call: (9) 3\==2 ? creep
   Exit: (9) 3\==2 ? creep
   Call: (9) remove([2], 2, []) ? creep
   Fail: (9) remove([2], 2, []) ? creep   <---- NOTE THIS FAILURE! (no clause match)
   Fail: (8) remove([3, 2], 2, [3]) ? creep
   Redo: (7) remove([2, 3, 2], 2, [3]) ? creep
   Fail: (7) remove([2, 3, 2], 2, [3]) ? creep
   Fail: (6) remove([1, 2, 3, 2], 2, [1, 3]) ? creep

大小写 remove([2], 2, []) 与您的第一个实现的第二个子句不匹配：

remove([H1|T1], H1, [H2|T2])...

所以H1 = 2，T1 = []，但是[H2|T2]不能和[]统一。

但它会匹配你的第二个实现的第二个子句：

remove([H1|T1], H1, Ys).

给你，H1 = 2、T1 = [] 和 Ys = []。这是第二个版本的跟踪：

[trace]  ?- remove([1,2,3,2],2,[1,3]).
   Call: (6) remove([1, 2, 3, 2], 2, [1, 3]) ? creep
   Call: (7) 1\==2 ? creep
   Exit: (7) 1\==2 ? creep
   Call: (7) remove([2, 3, 2], 2, [3]) ? creep
   Call: (8) remove([3, 2], 2, [3]) ? creep
   Call: (9) 3\==2 ? creep
   Exit: (9) 3\==2 ? creep
   Call: (9) remove([2], 2, []) ? creep   <---- SUCCESS! (2nd clause match)
   Call: (10) remove([], 2, []) ? creep   <---- SUCCESS!
   Exit: (10) remove([], 2, []) ? creep
   Exit: (9) remove([2], 2, []) ? creep
   Exit: (8) remove([3, 2], 2, [3]) ? creep
   Exit: (7) remove([2, 3, 2], 2, [3]) ? creep
   Exit: (6) remove([1, 2, 3, 2], 2, [1, 3]) ? creep

为什么使用 [H|T] 作为参数而不是普通变量会导致我的谓词失败？

Why does using [H|T] as a parameter instead of a normal variable cause my predicate to fail?

list

prolog