错误:使用 append/3 超出全局堆栈 [英] ERROR: Out of global stack with append/3

问题描述

我有问题.我想实现一个 replace(E1, L1, E2, L2) 谓词.这适用于 L1 和 L2 是相同列表时，除了在 L1 具有值 E1 的地方，L2 具有 E2.此外，只替换一个事件，并且它必须在任何模式下工作.

I have a problem. I want to implement a replace(E1, L1, E2, L2) predicate. This holds when L1 and L2 are the same lists,except that in one place where L1 has the value E1, L2 has E2. In addition, only one occurrence is replaced and it must work in any mode.

例如:

replace(2,[1,2,3,4],5,X) 应该只有解 X = [1,5,3,4].

replace(2,[1,2,3,2,1],5,X) 应该回溯解决方案 X =[1,5,3,2,1] 和 X = [1,2,3,5,1].

replace(2,[1,2,3,2,1],5,X) should backtrack over the solutions X = [1,5,3,2,1] and X = [1,2,3,5,1].

replace(2,X,5,[1,5,3,5,1]) 应该回溯解决方案 X =[1,2,3,5,1] 和 X = [1,5,3,2,1].

replace(2,X,5,[1,5,3,5,1]) should backtrack over the solutions X = [1,2,3,5,1] and X = [1,5,3,2,1].

replace(X,[a,b,c,d],Y,[a,e,c,d]) 应该只有解 X = b,Y = e.

replace(X,[1,2,3,2,1],Y,[1,5,3,5,1]) 应该没有解(它应该失败).

replace(X,[1,2,3,2,1],Y,[1,5,3,5,1]) should have no solutions (it should fail).

我的实现:

 replace(E1, L1, E2, L2) :- 
    append(X, [E1|L_Tail], L1),
    append(X, [E2|L_Tail], L2).

这段代码没问题.但是当replace(2,X,5,[1,5,3,5,1])时，它应该返回X = [1,2,3,5,1] 和 X = [1,5,3,2,1] 和 false.它只返回前 2 个结果，false 没有出现.程序以 ERROR: Out of global stack 结束.

This code is fine. However when replace(2,X,5,[1,5,3,5,1]), it should return X = [1,2,3,5,1] and X = [1,5,3,2,1] and false. It only return the first 2 results, and the false didn't came up. The program end up with ERROR: Out of global stack.

推荐答案

This问题已被提出，它有两个答案:您使用过的一个和一个更好的.但是，我会回答为什么这个解决方案不起作用以及如何解决它?"的问题.

This question has been asked and it has two answers: the one you used and a better one. However, I will answer the question "why does this solution not work and how to fix it?".

当 append/3 的第三个参数是一个变量或部分列表时，它给出了无限多个解:

When the third argument to append/3 is a variable or a partial list, it gives infinitely many solutions:

?- append(X, Y, [a|Z]).
X = [],
Y = [a|Z] ;
X = [a],
Y = Z ;
X = [a, _1860],
Z = [_1860|Y] ;
X = [a, _1860, _1872],
Z = [_1860, _1872|Y] ;
X = [a, _1860, _1872, _1884],
Z = [_1860, _1872, _1884|Y] . % and so on

因此，当第一个列表 L1 是部分列表时，对 append(X, [E1|Y], L1) 的调用将保持幻觉"的时间更长和更长的列表.对 append/3 的第二次调用每次都会失败，Prolog 将回溯，使用第一个 append/3 生成更长的列表，依此类推.这就是为什么您会陷入无限循环并最终耗尽内存(当列表变得太长时).

So, when the first list L1 is a partial list, the call to append(X, [E1|Y], L1) will keep "hallucinating" longer and longer lists. The second call to append/3 will fail every time, Prolog will backtrack, make an even longer list with the first append/3, and so on. This is why you are caught in an infinite loop and will eventually run out of memory (when the lists get too long).

避免这种情况的一种廉价方法是在将它们提供给两个 append 之前确保两个列表都是相同长度的正确列表.例如:

One cheap way to avoid this is to make sure that both lists are proper lists of the same length before giving them to the two appends. For example:

same_length([], []).
same_length([_|A], [_|B]) :- same_length(A, B).

如果您使用的是 SWI-Prolog，您可以使用 maplist 和 yall lambda 来做到这一点:

If you are using SWI-Prolog you could do this with maplist and a yall lambda:

maplist([_,_]>>true, L1, L2)

示例查询:

?- L2 = [1,5,3,5,1],
   maplist([_,_]>>true, L1, L2),
   append(X, [2|Y], L1),
   append(X, [5|Y], L2).
L2 = [1, 5, 3, 5, 1],
L1 = [1, 2, 3, 5, 1],
X = [1],
Y = [3, 5, 1] ;
L2 = [1, 5, 3, 5, 1],
L1 = [1, 5, 3, 2, 1],
X = [1, 5, 3],
Y = [1] ;
false.

这篇关于错误:使用 append/3 超出全局堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！