序言:delete谓词如何提供列表的开头

让我们看看有问题的查询会发生什么:

?- delete(a,[1,2,3,a,b,c,d], X).

自从 a 和 1 无法统一,第一条规则失败。然而,第二条规则与, A=a ,则, B=1 ,则, C=2 和 D=[3,a,b,c,d] 因此,递归目标称为:

delete(a,[2|[3,a,b,c,d]],E)

同样,第一条规则不匹配,因为 A. 不同于 2 。第二条规则再次成功,这次是 A=A ,则, B=2 ,则, C=3 和 D=[a,b,c,d] 。因此,递归调用:

delete(a,[3|[a,b,c,d]],E)

再一次,第一条规则失败了,第二条规则成功了 A=A ,则, B=3 ,则, C=a 和 D=[b,c,d] 。因此,递归调用:

delete(a,[a|[b,c,d]],E)

现在,在第一条规则中, a=a 已成功统一,因此规则成功 A=A ,则, B=[b,c,d] .返回递归,得到:

E=[b,c,d], B=3 therefore [B|E]=[3|[b,c,d]]=[3,b,c,d] 

E = [3,b,c,d], B=2 therefore [B|E]=[2|[3,b,c,d]]=[2,3,b,c,d] 

E = [2,3,b,c,d], B=1 therefore [B|E]=[1|[2,3,b,c,d]]=[1,2,3,b,c,d] 

因此,Prolog告诉您,确实有一个解决方案:

?- delete(a,[1,2,3,a,b,c,d], X).
X = [1, 2, 3, b, c, d]

现在,您可以按询问是否有其他解决方案 ;

?- delete(a,[1,2,3,a,b,c,d], X).
X = [1, 2, 3, b, c, d] ;

Prolog返回到开放选择点并遵循递归规则,直到 D=[] 。第一条规则的下一个递归调用失败,因为 []=[A|B] 无法统一。第二条规则也失败了,因为 []=[B,C|D] 也不能统一。因此,Prolog尽职尽责地报告,没有更多的解决方案:

?- delete(a,[1,2,3,a,b,c,d], X).
X = [1, 2, 3, b, c, d] ;
false.

作为一个小背景,我们可以考虑一个单链接列表由两个“构造函数”组成: [] ,空列表,以及 [H|T] 哪里 H 列表的开头是否存在某种值,以及 T ,尾部,H之后剩下的内容列表。

这里有两个条款。第一个是:

delete(A, [A|B], B).

我可能会用不同的方式来描述它 delete(Head, [Head|Tail], Tail) .这是实现统一的条款,例如:

?- delete(3, [3,a,b,c,d], X).
X = [a, b, c, d] 

这是因为 [H|T]=[3,a,b,c,d] 将统一 H=3 和 T=[a,b,c,d] .试试看。

现在,让我们花点时间思考一下Prolog如何选择子句。在每一步中,Prolog本质上都在尝试统一。因此,当呈现 delete(a, [1,2,3,a,b,c,d], X) ,Prolog继续尝试统一 delete(H, [H|T], T) 具有 删除(a,[1,2,3,a,b,c,d],X) 。这不会成功,因为a!=1、Prolog再次尝试第二条,我们发现自己:

delete(A, [B, C|D], [B|E]) :-  
    delete(A, [C|D], E).  

现在,通过这个示例,Prolog将尝试将子句的开头统一为 delete(A=a, [B=1,C=2|D=[3,a,b,c,d]], [B=1|E]) 。这成功了,因为没有特别的原因 A 不能等于a, B 不能等于1, C 不能等于2,并且 D 不能等于 [3,a,b,c,d] .所以现在Prolog前进到 delete(A, [C|D], E) 它将尝试调用 delete(a, [2,3,a,b,c,d], E) 。如果启用 trace 在您的REPL中,您将看到以下内容:

?- trace.
true.

[trace]  ?- delete(a, [1,2,3,a,b,c,d], X).
   Call: (8) delete(a, [1, 2, 3, a, b, c, d], _3240) ? creep
   Call: (9) delete(a, [2, 3, a, b, c, d], _3498) ? creep

通过第二次调用,您可以看到Prolog现在对查找 delete(a, [2,3,a,b,c,d], _4120) 这是一个新变量,不是前一个调用中的变量。我可以向你保证,在新的事情发生之前,同样的事情还会发生多次。

   Call: (9) delete(a, [2, 3, a, b, c, d], _3498) ? creep
   Call: (10) delete(a, [3, a, b, c, d], _3510) ? creep

但是,在下一次调用时,可以激活第一个子句:

   Call: (11) delete(a, [a, b, c, d], _3522) ? creep
   Exit: (11) delete(a, [a, b, c, d], [b, c, d]) ? creep

这一次,变量与一些东西统一了。这是因为您的第一个子句是基本情况。现在回顾一下你的定义,你可以看到第二个子句中的第三个参数是 [B|E] ,这意味着当 B 和 E 已经和某些东西结合在一起了。因此,跟踪的其余部分是该子句的出口,该变量已与某些内容统一。每一次,所发生的只是 B 在对结果进行递归调用之前,已从列表中删除:

   Exit: (10) delete(a, [3, a, b, c, d], [3, b, c, d]) ? creep
   Exit: (9) delete(a, [2, 3, a, b, c, d], [2, 3, b, c, d]) ? creep
   Exit: (8) delete(a, [1, 2, 3, a, b, c, d], [1, 2, 3, b, c, d]) ? creep
X = [1, 2, 3, b, c, d] .

就在这里。