錯誤：在處理序言對列表時出現「Out of global stack」

在SWI-Prolog中，我有一個列表，其元素是Key-ValuesList形式的對。例如，一個這樣的列表可以看起來像：錯誤：在處理序言對列表時出現「Out of global stack」

[1-[a,b],2-[],3-[c]]

我想此列表轉換爲對形式密鑰 - [value]，其中值是在ValuesList中的元素的的嵌套列表。上面的例子將被轉換成：

[[1-[a],2-[],3-[c]], [1-[b],2-[],3-[c]]]

我的當前的解決方案如下：

% all_pairs_lists(+InputList, -OutputLists). 
all_pairs_lists([], [[]]). 
all_pairs_lists([Key-[]|Values], CP) :- 
    !, 
    findall([Key-[]|R], (all_pairs_lists(Values,RCP), member(R,RCP)), CP). 
all_pairs_lists([Key-Value|Values], CP) :- 
    findall([Key-[V]|R], (all_pairs_lists(Values,RCP), member(V,Value), member(R,RCP)), CP).

使用該謂詞，以下形式的呼叫

all_pairs_lists([1-[a,b],2-[],3-[c]],OutputLists).

綁定變量OutputLists到上面提到的期望結果。雖然看起來是正確的，但是當InputList具有非常長的列表作爲值時，此實現會導致「全局堆棧外」錯誤。

有沒有一個更少的堆棧消耗方法來做到這一點？對於這種類型的數據結構來說，這看起來很常見。

來源

2012-08-07 Epicurus

那麼，總結一下，你做錯了。在Prolog中，當我們想要表達一個關係而不是一個函數（幾個可能的結果而不是一個）時，我們並不直接使用findall/3和member/2。我們寧願說出關係是什麼，然後可能一旦完成，如果我們需要一個我們使用的結果列表findall/3。

這裏它的意思是，我們想表達以下關係：

Take a list of Key-Values and return a list of Key-[Value] where Value is a member of the Values list.

我們可以採取以下方式：

% The base case: handle the empty list 
a_pair_list([], []). 

% The case where the Values list is empty, then the resulting [Value] is [] 
a_pair_list([Key-[]|List], [Key-[]|Result]) :- 
    a_pair_list(List, Result). 
% The case where the Values list is not empty, then Value is a member of Values. 
a_pair_list([Key-[Not|Empty]|List], [Key-[Value]|Result]) :- 
    member(Value, [Not|Empty]), 
    a_pair_list(List, Result).

一旦這種關係表示，我們已經可以獲取所有我們希望的信息：

?- a_pair_list([1-[a, b], 2-[], 3-[c]], Result). 
Result = [1-[a], 2-[], 3-[c]] ; 
Result = [1-[b], 2-[], 3-[c]] ; 
false.

想要的列表現在只是一個相當直接的findall/3，服務到家：

all_pairs_lists(Input, Output) :- 
    findall(Result, a_pair_list(Input, Result), Output).

要記住的重要一點是，它的方式更好地從額外邏輯的東西敬而遠之：!/0，findall/3，等...因爲它常常導致更少的一般程序和/或更少正確那些。在這裏，我們應該以純潔的方式表達上述關係。這樣我們就可以嚴格限制findall/3的使用。

來源

2012-08-07 10:38:54 m09

謝謝這真的讓事情變得清晰。但是，它仍然會爲大型輸入列表生成相同的堆棧溢出錯誤。五個鍵每個具有50個值列表導致堆棧溢出。 – Epicurus 2012-08-07 13:04:36

但根據您的具體需要，可能無法立即返回列表。你也可以看看，並完全跳過findall。 – m09 2012-08-07 13:20:57

btw 5個鍵每個都有50個值，是312M列表，它有很多列表。我猜，即使擴展堆棧也會導致其他問題。你需要參考我以前的評論我認爲 – m09 2012-08-07 13:30:10

由於@Mog已經清楚地說明了問題可能是什麼，在這裏一個版本使用基本 '功能' 爲內置列表處理的（AB）：

all_pairs_lists(I, O) :- 
    findall(U, maplist(pairs_lists, I, U), O). 

pairs_lists(K-[], K-[]) :- !. 
pairs_lists(K-L, K-[R]) :- member(R, L).

測試：

?- all_pairs_lists([1-[a,b],2-[],3-[c]],OutputLists). 
OutputLists = [[1-[a], 2-[], 3-[c]], [1-[b], 2-[], 3-[c]]].

來源

2012-08-07 11:03:08 CapelliC

這個版本很好看。儘管如此，就像Mog的版本一樣，它會導致堆棧溢出，其中包含5個鍵和一個大約50個值的列表。 – Epicurus 2012-08-07 13:07:18

是的，所有3個版本應該等同於每個堆棧的使用。 – CapelliC 2012-08-07 14:25:15

錯誤：在處理序言對列表時出現「Out of global stack」

回答

相關問題