12

当我们将 append 与 cut 运算符一起使用时会出现什么问题？

   append2([],L,L):-!.
   append2([H|T],L,[H|TL]):-append2(T,L,TL).

我尝试了几种不同的输入，但总是成功。

?- append2([1,2],[5],L).
L = [1, 2, 5].

?- append2([1,2],[1,2],L).
L = [1, 2, 1, 2].

?- append2([],[1,2],L).
L = [1, 2].

?- append2([1,2],[],L).
L = [1, 2].
4

4 回答 4

8

有时引入绿色切割确实很有意义 - 甚至引入append/3，但必须注意这样的切割仍然是绿色切割。也就是说，确实提高了效率（在一定程度上）并且不影响答案的削减。

引入绿色切割有一个非常简单的经验法则：如果你在一个没有任何保护的纯单调程序中添加一个切割，你可以很确定这将是一个破坏你程序意义的红色切割。

这个经验法则很少有例外。例如，如果没有进一步的规则等，您可以在可变的自由目标之后添加一个削减。尝试找出受削减影响的案例绝对是一个很好的培训。

但回到你的程序append2/3。目前，即使替代规则确实适用，剪切总是会剪切，在这种情况下，剪切会删除我们想要避免的答案。

那么第一个子句什么时候才是唯一相关的呢？

如果第一个参数是[]，那么append2([], Xs, Ys).- 而且如果最后一个参数是[]（还有更多更复杂的情况）。让我们用原始的无切割定义尝试这两种情况：

?- 附加（[]，Ys，Zs）。
Ys = Zs。

?- 附加（Xs，Ys，[]）。
Xs = Ys, Ys = [] ;
错误的。

因此，在第一种情况下，系统能够立即确定存在单一解决方案，同时产生答案。然而，在第二种情况下，Prolog 系统不确定是否需要另一个答案——可以说它“留下了一个选择点”。很遗憾，因为确定在这种情况下也只存在一个答案是相当简单的。削减将是理想的帮助。但是，毫无防备的切割弊大于利。

如果第三个参数是 a ，则剪切可能会剪切[]：

append3(Xs, Ys, Zs) :-
   (  Zs == [] -> ! ; true ),
   Xs = [],
   Ys = Zs.
append3([X|Xs], Ys, [X|Zs]) :-
   append3(Xs, Ys, Zs).

这个程序现在更有效，因为它不会打开选择点，如果只知道第三个参数。

?- 附加（Xs，Ys，[1]）。
Xs = [],
Ys = [1] ;
Xs = [1]，
是 = [] ;
错误的。

?- append3(Xs,Ys,[1])。
Xs = [],
Ys = [1] ;
Xs = [1]，
是 = []。

该程序不一定更快，因为测试本身可能很昂贵。理想情况下，Prolog 系统将能够在内部执行此类操作，但有时程序员必须提供一些帮助。

于 2012-10-03T14:46:52.913 回答
6

有两种切割方式；绿色切割和红色切割。插入绿色切割只是为了提高效率并且不改变程序的语义。另一方面，红色切割可以。根据定义，绿色削减不会造成任何问题。

那么，如果没有削减，有没有办法改变行为？

让我们来看看; 对于要匹配的第一个子句，L1 应该与 [] 一致，L2 与 L 和 L3 与 L 一致，或者换句话说，L2 与 L3 一致。

当 L1 为 [] 时，第二个子句不能匹配；所以切割没有任何效果

当 L1 未实例化时：如果此时 L2 和 L3 的长度已知，则它们必须相等，否则第一个子句将不匹配；因此，第二个子句无法匹配，因为在每一步 L3 的长度都会减少 1，并且终止的唯一方法需要 L2=L3

如果 L3 或 L2 的长度未知：那么我们有一个问题，因为第二个子句可能会产生解决方案。

确实：

    3 ?- append2(L1,L2,[1,2,3]).
    L1 = [],
    L2 = [1, 2, 3].

    4 ?- append2(L1,[1,2,3],L3).
    L1 = [],
    L3 = [1, 2, 3].

    5 ?- append2(L1,L2,L3).
    L1 = [],
    L2 = L3.

    6 ?- append2(L1,[E1,E2],L3).
    L1 = [],
    L2 = [E1, E2].

    7 ?- append2(L1,L2,[E1,E2]).
    L1 = [],
    L2 = [E1, E2].

虽然我们期望：

8 ?- append(L1,L2,[1,2,3]).
L1 = [],
L2 = [1, 2, 3] ;
L1 = [1],
L2 = [2, 3] ;
L1 = [1, 2],
L2 = [3] ;
L1 = [1, 2, 3],
L2 = [] ;
false.

9 ?- append(L1,[1,2,3],L3).
L1 = [],
L3 = [1, 2, 3] ;
L1 = [_G24],
L3 = [_G24, 1, 2, 3] ;
L1 = [_G24, _G30],
L3 = [_G24, _G30, 1, 2, 3] ;
L1 = [_G24, _G30, _G36],
L3 = [_G24, _G30, _G36, 1, 2, 3] ;
L1 = [_G24, _G30, _G36, _G42],
L3 = [_G24, _G30, _G36, _G42, 1, 2, 3] ;
...

10 ?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;
L1 = [_G22],
L3 = [_G22|L2] ;
L1 = [_G22, _G28],
L3 = [_G22, _G28|L2] ;
....

11 ?- append(L1,[E1,E2],L3).
L1 = [],
L3 = [E1, E2] ;
L1 = [_G78],
L3 = [_G78, E1, E2] ;
L1 = [_G78, _G84],
L3 = [_G78, _G84, E1, E2] ;
L1 = [_G78, _G84, _G90],
L3 = [_G78, _G84, _G90, E1, E2] ;
...

12 ?- append(L1,L2,[E1,E2]).
L1 = [],
L2 = [E1, E2] ;
L1 = [E1],
L2 = [E2] ;
L1 = [E1, E2],
L2 = [] ;
false.
于 2012-07-06T10:40:33.240 回答
5

尝试例如最一般的查询：

?- append2(X, Y, Z).
于 2012-07-06T11:49:53.487 回答
3

当前两个参数是可变的时，它将不起作用：

?- append(X, Y, [1, 2, 3]).
X = [],
Y = [1, 2, 3] ;
X = [1],
Y = [2, 3] ;
X = [1, 2],
Y = [3] ;
X = [1, 2, 3],
Y = [] ;
false.

?- append2(X, Y, [1, 2, 3]).
X = [],
Y = [1, 2, 3].
于 2012-07-06T10:18:12.403 回答