避免在Prolog中追加/ 3的線性成本

假設我們正在從標準輸入讀取並構建所有已讀取行的列表。最後，我們需要顯示那些以逗號分隔的行。避免在Prolog中追加/ 3的線性成本

go:- 
    prompt(_, ''), 
    processInput([ ], Lines), 
    findall(_, (member(L, Lines), write(L), write(',')), _), 
    nl. 

processInput(LinesSoFar, Lines):- 
    read_line_to_codes(current_input, Codes), 
    processInput(Codes, LinesSoFar, Lines). 

processInput(Codes, LinesSoFar, Lines):- 
    (Codes \= end_of_file 
    -> 
     atom_codes(Line, Codes), 
     append(LinesSoFar, [ Line ], LinesSoFar1), % <---- append/3 - O(n) 
     processInput(LinesSoFar1, Lines) 
    ; 
     Lines = LinesSoFar).

問題瓦特/此代碼是，append呼叫processInput/3成本我們爲O（n）。我們怎樣才能避免這個代價&仍然讓我們的謂詞是尾遞歸的（因爲我們可能從標準輸入中讀取很多行）？

我想到我們可以用以下代替append。

LinesSoFar1 = [ Line | LinesSoFar ],

而且我們可以在顯示它之前將列表反轉。但這似乎很難。有沒有更好的辦法？

來源

2011-06-08 Ashley

你知道這可能看起來很詭異，但它是這樣做的Prolog方式。如果你做得對，它會保留邏輯語義。 – 2011-06-09 09:31:46

我不認爲你提出（在前面加上列表元素，然後在最後扭轉列表）「哈克」的解決方案。具有顯式差異列表的gusbro解決方案也可以。我覺得最優雅的方式是採用DCG符號（隱式接口差異表），即使用DCG描述行列表：

read_lines --> 
     { read_line_to_codes(current_input, Codes) }, 
     ( { Codes == end_of_file } -> [] 
     ; { atom_codes(Line, Codes) }, 
      [Line], 
      read_lines 
     ).

用法：phrase(read_lines, Lines)。

來源

2011-06-08 17:42:49 mat

一個非常優雅的解決方案 – Sebastian 2012-12-29 21:53:14

你可以使用半實例化的結構來實現它。檢查這個代碼：

append_init(Marker-Marker). 

append_end(L-[I|NMarker], I, L-NMarker). 

append_finish(L-[], L).

你開始通過 '初始化' 半實例化結構通過調用append_init（L）。然後，您可以通過調用append_end（L，Item，NewList）在列表末尾添加元素。添加完元素後，您可以調用append_finish（L，List）以獲取最終的完全實例化列表。

例子：

example(NL):- 
    append_init(L), 
    append_end(L, a, L1), 
    append_end(L1, b, L2), 
    append_end(L2, c, L3), 
    append_finish(L3, NL). 

?- example(L). 
L = [a, b, c].

來源

2011-06-08 14:30:43 gusbro

對於初學者來說，你可以做到這一點真的很棒！ – Ashley 2011-06-09 12:57:46

避免在Prolog中追加/ 3的線性成本

回答

相關問題