不会留下选择点的纯 append/3 模式 (-,+,+)

Question

通常的append/3是纯粹的，但是它给mode(-,+,+)留了一个选择点：

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

在上面的结果中你是一个选择点可以看出，例如 SWI-Prolog 提供了提示，然后是“;”提供虚假。我想出了这个解决方案来避免选择点：

append2(X, Y, Z) :-
   reverse(Z, H),
   reverse(Y, J),
   append(J, K, H),
   reverse(K, X).

这个新的append2/3不留选择点了:

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

但是有比reverse/2 cludge 更好的解决方案吗？请注意，有一个谓词 last/3 可用于仅从末尾删除一个元素的示例。但是模式 (-,+,+) 应该适用于第二个参数中的任意长列表。

Answer 1

您的 append2 没有为 (-, +, +) 模式留下选择点，而是为其他模式引入它们。我不知道是否可以在不使用 var/1 或其他东西检查操作模式的情况下编写它。

这是 mercury library 手册中关于相关模式的评论。

% The following mode is semidet in the sense that it doesn't
% succeed more than once - but it does create a choice-point,
% which means it's inefficient and that the compiler can't deduce
% that it is semidet. Use remove_suffix instead.
% :- mode append(out, in, in) is semidet.

remove_suffix谓词在mercury中实现如下：

remove_suffix(List, Suffix, Prefix) :-
    list.length(List, ListLength),
    list.length(Suffix, SuffixLength),
    PrefixLength = ListLength - SuffixLength,
    list.split_list(PrefixLength, List, Prefix, Suffix).

Answer 2

But are there better solutions than the reverse/2 kludge?

有更好的解决方案，但不是最佳解决方案：

:- use_module(library(reif)).

append2u(Xs, Ys, Zs) :-
   if_(Ys = Zs,
      Xs = [],
      ( Xs = [X|Xs1], Zs = [X|Zs1], append2u(Xs1, Ys, Zs1) )
   ).

?- append2u(Xs, [3], [1,2,3]).
   Xs = [1,2].

库 reif 内置于 Scryer 中，也可用于 SICStus and SWI。

连查询...

?- append2u(Xs, Ys, Ys).
   Xs = [].

...现在可以使用了！

请注意，与 append/3 等价需要启用发生检查。在有理树的系统中（因此没有发生检查）我们得到比单一解决方案更多的答案：

?- append(Xs, Ys, Ys).
   Xs = []
;  Xs = [_A], Ys = [_A|Ys]        % infinite list Ys = [_A,_A,_A, ...]
;  Xs = [_A,_B], Ys = [_A,_B|Ys]  % infinite list Ys = [_A,_B,_A,_B,_A,_B, ...]
;  ...

尽管如此，

?- append2u([], Ys, Zs).
   Ys = Zs
;  false.

这通常是确定的。

不过，终止属性仍然完好无损！事实上，append2u/3 比常见的 append/3 终止得更好，如上面的第一种情况所示。

Answer 3

刚刚通过 reverse/3、
进一步解决消除内部 append/3.

append3(X, Y, Z) :-
   reverse(Z, H),
   reverse(Y, K, H),
   reverse(K, X).

reverse(X, Y) :-
  reverse(X, [], Y).

reverse([], X, X).
reverse([X|Y], Z, T) :- 
   reverse(Y, [X|Z], T).

似乎可行，没有选择点。
并且比 :

更高效

?- append3(X, [3], [1,2,3]).
X = [1, 2]

?- length(P,100), length(Q,200), 
   time((between(1,40,_),append3(X, P, Q), fail; true)).
% Up 9 ms, GC 0 ms, Threads 8 ms (Current 12/19/20 08:57:49)
Yes

?- length(P,100), length(Q,200), 
   time((between(1,40,_),append2u(X, P, Q), fail; true)).
% Up 875 ms, GC 9 ms, Threads 862 ms (Current 12/19/20 08:57:45)
Yes

但也有点危险：

?- append3([1], [2,3], X).
X = [1, 2, 3] ;
%%% hangs

不会留下选择点的纯 append/3 模式 (-,+,+)

Pure append/3 for mode (-,+,+) that wouldn't leave a Choice Point

append

prolog