錯誤：全局堆棧與追加/ 3

Question

我遇到問題。我想實現一個替換（E1，L1，E2，L2）謂詞。 當L1和L2是相同的列表時，這是成立的，除了在L1具有值E1，L2具有E2的地方。另外，只有一個事件被替換，它必須以任何模式工作。

例如：

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,X,5,[1,5,3,5,1])應回溯解決方案X = [1,2,3,5,1]和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(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。它只返回前兩個結果，並且false沒有出現。該方案最終以ERROR: Out of global stack。

Answer 1

This question已被問及它有兩個答案：one you used和better one。但是，我會回答這個問題：「爲什麼這個解決方案不起作用以及如何解決？」。

當第三個參數append/3是一個變量或部分列表，它提供了無限多的解決方案：

?- 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的列表更長，等等。這就是爲什麼你陷入無限循環並最終會耗盡內存（當列表太長時）。

避免這種情況的一種便宜方法是確保兩個列表都是相同長度的正確列表，然後再將它們提供給兩個append s。例如：

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

如果您正在使用SWI-Prolog的，你可以用MAPLIST做到這一點，一個yall拉姆達：

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.