谓词 '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 ? ;
no

| ?- 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 享有许多其他属性 - 特别是减轻此问题的逻辑变量的 "single assignment" 属性。同样的技术也经常用于差异列表和 DCG。如果您始终如一且明智地使用它，它将提高性能和终止属性。

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

How does the predicate 'append/3' work with an anonymous variable in Prolog?

prolog

prolog-anonymous-variable

答案与解决方案