prolog - 谓词 'append/3' 如何与 Prolog 中的匿名变量一起使用？

Question

append/3 究竟如何处理匿名变量(如下例中的变量):

append(_,[b(F,ND,P)|Rest],Visited).

我们实际上不能只使用 append/2 ？

谢谢您的回答!

Answer 1

目标

..., append(_,[b(F,ND,P)|Rest],Visited).

内容为:

Somewhere in the list of Visited nodes, there is a b(F, ND, P) with subsequent nodes Rest.

请注意，可能有多个这样的节点，因此很可能在某个地方存在剪切或 once/1。

Couldn't we in fact just use append/2?

你从哪里挖出那个骨架 - 呃 - 库谓词？但事实上，这可能允许我们实现 append/3:

myappend(Xs, Ys, Zs) :-
   append([Xs,Ys], Zs).

所以背后的直觉是列表Xs与列表Ys连接是列表Zs。从这个声明的角度来看，显然没有任何区别。或者他们是吗？

至少在程序上，存在差异!对于...

?- append([], Ys, Zs), false.
   false.

...终止，但是...

?- append([[], Ys], Zs), false.
   loops.

...循环! (在 SWI 和 SICStus 中)让我们看看生成的具体答案(我将使用 SICStus，因为它打印变量更紧凑，SWI 使用难以读取的变量，如 _G1376):

?- append([], Ys, Zs).
   Zs = Ys.
?- append([[], Ys], Zs).
   Ys = [], Zs = []
;  Ys = [_A], Zs = [_A]
;  Ys = [_A,_B], Zs = [_A,_B]
;  Ys = [_A,_B,_C], Zs = [_A,_B,_C]
; ... .

因此 append/3 产生了一个答案，而 append/2 似乎产生了无限多个答案。它们如何在声明上是等价的，或者不是？

答案与解决方案

首先指出上面的Ys = [], Zs = []是一个具体的解决方案。接下来是答案Ys = [_A], Zs = [_A]，其中包含无限多个解决方案。 _A 在这里代表无限多个基本术语。因此，有一种方法可以将无限多个解决方案折叠(或提升)为一个单一、优雅且有限的答案。

现在，append([], Ys, Zs) 更进一步，它将所有答案折叠成一个:Ys = Zs。但是，这是对的吗？这个答案意味着任何术语都可以是Ys。特别是，non_list 它肯定不是一个列表。想一想:

?- append([a],nonlist,Zs).
   Zs = [a|nonlist].

因此，append/3 实际上所做的是过度概括或提升事物太过分。其实它的定义是:

append([], Zs, Zs).
append([X|Xs], Ys, [X|Zs]) :-
   append(Xs, Ys, Zs).

事实如下:

The empty list appended with anything, really anything (including all Polish kings), is just that anything.

显然这个事实说得有点太多了。但正是这种过度概括有助于提高终止特性!而且，如果我们稍微小心一点，这种过度概括就永远不会显现出来。 ((^{_{有点不正当交易？}}))

但是，Prolog 具有许多其他属性 - 特别是逻辑变量的“单一赋值”属性，可以缓解这个问题。同样的技术也经常用于差异列表和 DCG。如果您一致且明智地使用它，它将提高性能和终止属性。