prolog - Prolog：删除谓词如何甚至在列表的开头提供

Question

我当然误解了 Prolog 的工作原理。这个问题很具体，尽管我正在寻找解释而不是编程问题的直接解决方案；“如何”问题而不是“给我代码”问题。

这是我要询问的 Prolog 删除谓词的定义。

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

我的误解是，在我看来，这样的电话

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

应该成功返回[3,b,c,d]（确实如此），但是这样的调用

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

应该无法返回解决方案。然而，后一个调用实际上确实返回了一个很好的解决方案[1,2,3,b,c,d]。

在我看来这样的原因如下。（我认为我们现在越来越接近我无法理解的关于 Prolog 的内容。）参考定义的这一部分，

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

看起来只有B头部（即）之前的单个元素（即C）将包含在响应中。这就是为什么我无法理解

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

设法返回一个答案，其中不仅包括3，还包括1，2作为解决方案列表的一部分，但它确实如此（如[1,2,3,b,c,d]）。谁能解释 Prolog 在这个非常具体的场景中如何处理列表，以说明它为什么考虑1并2作为解决方案的一部分，而不仅仅是3？非常感谢。

标签： prolog

Answer 1

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

?- 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=3D=[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.