append/3
如何处理匿名变量,例如以下示例中的变量:
append(_,[b(F,ND,P)|Rest],Visited).
难道我们不能只用append/2
吗?
谢谢你的回答!
目标
..., append(_,[b(F,ND,P)|Rest],Visited).
读:
在
Visited
节点列表中的某个地方,有一个b(F, ND, P)
,后续节点Rest
。
请注意,可能有多个这样的节点,因此很可能在某个地方或once/1
处有切口。
我们实际上不能只使用 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).
事实如下:
附加任何东西的空列表,真的任何东西(包括所有波兰国王),就是这样。
显然,这个事实说明得有点过分了。但正是这种过度概括有助于改善端接性能!而且,如果我们稍微小心一点,这种过度概括永远不会表现出来。((有点阴暗的交易?
但是,Prolog拥有许多其他属性 - 特别是缓解此问题的逻辑变量的"单赋值"属性。相同的技术也经常用于差异列表和DCG。如果您始终如一地明智地使用它,它将提高性能和端接性能。