list - 删除重复的解决方案

Question

我的代码按以下方式逐项合并两个列表列表:

mergeL([[a,b],[c,d]], [[1,2],[3,4]], Result). Result = [[a,b,1,2],[c,d,3,4]]

这是我使用的代码:

mergeL([],[],[]).
mergeL(List, [], List).
mergeL([], List, List).
mergeL([X|Rest],[Y|Rest2], [XY|Res2]) :-
   mergeL(Rest, Rest2, Res2),
   append(X,Y,XY).

这似乎可行，但如果我用两个相同大小的列表调用它，我会得到三个重复的结果。示例(两个列表只包含一个元素):

?- mergeL([[a,b]],[[1,2,3]],Q).
Q = [[a, b, 1, 2, 3]] ;
Q = [[a, b, 1, 2, 3]] ;
Q = [[a, b, 1, 2, 3]].

有没有一种干净的方法可以使这个输出只有一个解决方案？

Answer 1

已经有 3 个 SO-answers，但我不能同意一个!它们都不正确。

如何消除冗余方案

考虑您定义中的三个事实:

mergeL([],[],[]).
mergeL(List, [], List).
mergeL([], List, List).

mergeL([],[],[]) 它们都成功了，这是冗余的来源。第二和第三个事实是 List 是一个非空列表。因此，让我们将其添加到定义中:

mergeL([],[],[]).
mergeL(List, [], List) :- List = [_|_].
mergeL([], List, List) :- List = [_|_].

这消除了冗余的解决方案。无需削减以删除冗余解决方案。 other SO-answer中引入的削减但是，可能会隐藏解决方案。对于查询mergeL(Xs,YS,Zs)，剪切版本只有一个解，但应该有无限多个。

如何消除剩余的选择点

不过，使用剪切有一些意义:他们能够删除一个选择点。但是这样的切割需要像这样适本地保护:

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

我不确定这是否值得付出努力……实现可能会更有效地提供这一点。有关此的更多详细信息，请参阅 this , 和 this .

尾递归

对您来说更有趣的可能是对最后一条规则的更改。它应该是:

mergeL([X|Rest],[Y|Rest2], [XY|Res2]) :-
   append(X,Y,XY),
   mergeL(Rest, Rest2, Res2).

这样就避免了局部栈空间的临时分配。所以这绝对是一个优化。但不会损害谓词的逻辑阅读的优化。

在我的 2009 32 位笔记本电脑(几乎是 Steam 驱动的)和 SWI 6.3.3-40-g064f37b 上:

原始版本:

?- N is 2^20, length(L,N), maplist(=([]),L), time(mergeL(L,L,J)).
% 2,097,206 inferences, 5.232 CPU in 5.250 seconds (100% CPU, 400851 Lips)

尾递归版本:

?- N is 2^20, length(L,N), maplist(=([]),L), time(mergeL(L,L,J)).
% 2,097,152 inferences, 0.525 CPU in 0.526 seconds (100% CPU, 3997337 Lips)

这是 10 的因数。

现在有了更长的列表: 尾递归版本:

?- N is 2^22, length(L,N), maplist(=([]),L), time(mergeL(L,L,J)).
% 8,388,608 inferences, 4.228 CPU in 4.237 seconds (100% CPU, 1984272 Lips)

与原始顺序:

?- N is 2^22, length(L,N), maplist(=([]),L), time(mergeL(L,L,J)).
% 1,765,930 inferences, 1.029 CPU in 1.033 seconds (100% CPU, 1716119 Lips)
ERROR: Out of local stack

所以只执行了 1.7Mi 来填充本地堆栈。这主要是空间问题!如果你的内存比我多，只需增加 N is 2^22!