序言：替換指定索引處列表中的元素

Question

我想要一個Prolog謂詞，它可以替換指定索引處列表中的元素。

例子：

% replace(+List,+Index,+Value,-NewList). 
?- L=[a,b,c,d], replace(L,1,z,L2). 
L2 = [a,z,c,d] 

我不知道如何做到這一點。謝謝你的幫助！盧瓦克。

Answer 1

我給你的基本情況，我想你應該能夠輕鬆地做遞歸情況：

replace([_|T], 0, X, [X|T]). 

編輯：

現在運已經解決了這個問題，我將添加遞歸情況：

replace([H|T], I, X, [H|R]):- I > 0, I1 is I-1, replace(T, I1, X, R). 

EDIT2：

這應當交回原名單中的越界情況作爲@GeorgeConstanza要求在評論：

replace([_|T], 0, X, [X|T]). 
replace([H|T], I, X, [H|R]):- I > -1, NI is I-1, replace(T, NI, X, R), !. 
replace(L, _, _, L). 

它基本上走的是切割操作的優勢，不會升到第三個後備條款，如果有一個很好的入境更換。

Answer 2

很清楚，使用@fortran遞歸進行替換是最好的選擇。但是這太瘋狂了/實際使用速度很慢？

replace(List, Idx, With, ListOut) :- 
    length(Idx, Before), 
    append(Before, After, List), 
    ( After=[_Discard|Rest] 
    -> true 
    ; Rest=[] 
    ), 
    append(Before, [With|Rest], ListOut). 

基本上你做一個大小爲Idx的空白數組並將其綁定到輸入列表。然後丟棄該項目，並將兩個列表綁定在一起，替換元素夾在中。

如果您嘗試設置N個元素列表的idx N（從0索引），那麼可以進一步簡化該操作。

replace(List, Idx, With, ListOut) :- 
    length(Idx, Before), 
    append(Before, [_Discard|Rest], List), 
    append(Before, [With|Rest], ListOut). 

Answer 3

從FORTRAN答案是好的，但在SWI-Prolog的結構有無限的元數，所以這應該工作：

replace([_|T], 0, X, [X|T]). 
replace([H|T], I, X, [H|R]) :- 
    I > 0, 
    I1 is I - 1, 
    replace(T, I1, X, R). 

replace1(L, I, X, R) :- 
    Dummy =.. [dummy|L], 
    J is I + 1, 
    nb_setarg(J, Dummy, X), 
    Dummy =.. [dummy|R]. 

tr(Method, K) :- 
    length(L, K), 
    K1 is K - 1, 
    time(call(Method, L, K1, test, R)), 
    assertion(nth1(K, R, test)). 

但是，出乎我的意料：

?- % /home/carlo/prolog/replace.pl compiled 0,00 sec, 2,280 bytes 
?- tr(replace,2000000). 
% 3,999,999 inferences, 2,123 CPU in 2,128 seconds (100% CPU, 1884446 Lips) 
true . 

?- tr(replace1,2000000). 
% 5 inferences, 1,410 CPU in 1,414 seconds (100% CPU, 4 Lips) 
true. 

?- tr(replace,4000000). 
% 7,999,999 inferences, 3,510 CPU in 3,520 seconds (100% CPU, 2279267 Lips) 
true . 

?- tr(replace1,4000000). 
% 5 inferences, 2,825 CPU in 2,833 seconds (100% CPU, 2 Lips) 
true. 

?- tr(replace,5000000). 
% 9,999,999 inferences, 3,144 CPU in 3,153 seconds (100% CPU, 3180971 Lips) 
true . 

?- tr(replace1,5000000). 
% 5 inferences, 4,476 CPU in 4,486 seconds (100% CPU, 1 Lips) 
ERROR: =../2: Arguments are not sufficiently instantiated 
^ Exception: (9) setup_call_catcher_cleanup(system:true, prolog_statistics:catch(user:call(replace1, [_G1, _G4, _G7, _G10|...], 4999999, test, _G15000005), _G15000021, (report(t(1324124267.2924964, 18.892632697, 28490132), 10), throw(_G15000021))), _G15000145, prolog_statistics: (_G15000032=true)) ? abort 
% Execution Aborted 

我第一次嘗試（K = 10000000）殺死了進程！ 所以，我不喜歡，試圖獲得一些性能，我最終填充到SWI-Prolog的郵件列表發送錯誤報告...

編輯：後到SWI-Prolog的郵件列表後，和（快速！）更正，我已經重建，這裏是一個關於內存使用情況的提示（現在它全部是ISO標準代碼！）。由於不尋常的大值，需要一個堆棧增長指令前：

?- prolog_stack_property(global,limit(L)), N is L*2, set_prolog_stack(global,limit(N)). 
N = 536870912. 

這裏是更新的過程：

replace2(L, I, X, R) :- 
    Dummy =.. [dummy|L], 
    J is I + 1, 
    setarg(J, Dummy, X), 
    Dummy =.. [dummy|R]. 

和測試：

?- tr(replace,10000000). 
% 19,999,999 inferences, 5.695 CPU in 5.719 seconds (100% CPU, 3511942 Lips) 
true . 

?- tr(replace2,10000000). 
% 5 inferences, 2.564 CPU in 2.571 seconds (100% CPU, 2 Lips) 
true. 

它的速度更快的代碼，但請注意Jan對我的郵件的評論：

歸結爲= ..（+， - ）中的差錯處理。固定。 B.t.w. I 認爲這是非常糟糕的工作方式。即使你想 這樣做，只需使用setarg/3而不是nb_setarg/3。後者應該是不得已而爲之。此方法使用更多內存 ，因爲它需要巨大的術語和列表。最後，仿函數 （名稱/參數對）當前不會被回收，因此您爲每個替換的列表創建一個這樣的對象，其中這個對象從未被使用過。

Answer 4

真的，沒有人應該永遠與 IMO任何相當長的普通列表做到這一點，因爲每次更新將佔用O(n)新的空間。通過setarg/nb_setarg直接set_once /更新將佔用0新空間，並用二叉樹表示列表，O(log(n))新空間。替換也可以保存在一個單獨的字典中，本身保持爲一棵樹（因爲它需要增長）。 A 分塊列表（與in here一樣）可以在樹中保存大塊，每個固定大小的複合詞可通過setarg/nb_setarg直接設置/更新，並根據需要在樹中添加新的塊。

即使沒有更新，只是訪問平原名單是無可救藥緩慢，O(n)時間，在一個瞬間打開任何算法二次。列表只有很短的時間，或者作爲一項家庭作業練習。

Answer 5

如何以這種直截了當的方式做到這一點？

 
:- use_module(library(clpfd)). 

list_nth0_item_replaced([_|Xs], 0, E, [E|Xs]). 
list_nth0_item_replaced([X|Xs], N, E, [X|Ys]) :- 
    N #> 0, 
    N #= N0+1, 
    list_nth0_item_replaced(Xs, N0, E, Ys). 

這裏是指定的OP用例：

?- list_nth0_item_replaced([a,b,c,d],1,z,Ls). 
    Ls = [a,z,c,d] 
; false. 

上面的代碼是純粹的，所以我們可以提出更多的一般查詢—和期望邏輯的聲音回答：

?- list_nth0_item_replaced([a,b,c,d], N, X, Ls). 
    N = 0, Ls = [X,b,c,d] 
; N = 1, Ls = [a,X,c,d] 
; N = 2, Ls = [a,b,X,d] 
; N = 3, Ls = [a,b,c,X] 
; false. 

Answer 6

如果我們使用same_length/2,append/3和length/2，我們不需要編寫遞歸代碼：

由OP給出

 
list_nth0_item_replaced(Es, N, X, Xs) :- 
    same_length (Es, Xs), 
    append (Prefix, [_|Suffix], Es), 
    length (Prefix, N), 
    append(Prefix, [X|Suffix], Xs). 

樣品查詢：

?- list_nth0_item_replaced([a,b,c,d], 1, z, Xs). 
    Xs = [a,z,c,d] 
; false. 

這個工程 「在其他方向」 呢！

?- list_nth0_item_replaced(Xs, 1, z, [a,z,c,d]). 
    Xs = [a,_A,c,d] 
; false. 

更妙的是，我們甚至不需要指定具體指標：

?- list_nth0_item_replaced(Es, N, X, [a,z,c,d]). 
    N = 0, X = a, Es = [_A, z, c, d] 
; N = 1, X = z, Es = [ a,_A, c, d] 
; N = 2, X = c, Es = [ a, z,_A, d] 
; N = 3, X = d, Es = [ a, z, c,_A] 
; false. 

?- list_nth0_item_replaced([a,b,c,d], N, X, Xs). 
    N = 0, Xs = [X,b,c,d] 
; N = 1, Xs = [a,X,c,d] 
; N = 2, Xs = [a,b,X,d] 
; N = 3, Xs = [a,b,c,X] 
; false. 

Answer 7

代碼呈現in this previous answer是相當多才多藝—感謝clpfd。

是否有缺點？是的，有一個缺點：效率低下！

在這個答案中，我們提高性能和保留了多功能性。

 
:- use_module(library(clpfd)). 

我們繼續像this previous answer沒有當它定義的謂詞fd_length/2：

list_nth0_item_replaced__NEW(Es, N, X, Xs) :- 
    list_index0_index_item_replaced(Es, 0,N, X, Xs). 

list_index0_index_item_replaced([_|Es], I ,I, X, [X|Es]). 
list_index0_index_item_replaced([E|Es], I0,I, X, [E|Xs]) :- 
    I0 #< I, 
    I1 #= I0+1, 
    list_index0_index_item_replaced(Es, I1,I, X, Xs). 

所以......有它得到任何更快嗎？

 
?- numlist(1,100000,Zs), time(list_nth0_item_replaced(Zs,99999,x,Xs)). 
% 14,499,855 inferences, 0.893 CPU in 0.893 seconds (100% CPU, 16237725 Lips) 
Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...], 
Xs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; 
% 7 inferences, 0.000 CPU in 0.000 seconds (99% CPU, 18377 Lips) 
false. 

?- numlist(1,100000,Zs), time(list_nth0_item_replaced__NEW(Zs,99999,x,Xs)). 
% 499,996 inferences, 0.049 CPU in 0.049 seconds (100% CPU, 10158710 Lips) 
Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...], 
Xs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; 
% 6 inferences, 0.000 CPU in 0.000 seconds (93% CPU, 213988 Lips) 
false. 

OK，它是更快。但它仍然是多功能的？

 
?- list_nth0_item_replaced__NEW([a,b,c,d], 1, z, Xs). 
    Xs = [a,z,c,d] 
; false. 

?- list_nth0_item_replaced__NEW(Xs, 1, z, [a,z,c,d]). 
    Xs = [a,_A,c,d] 
; false. 

?- list_nth0_item_replaced__NEW(Es, N, X, [a,z,c,d]). 
    N = 0, X = a, Es = [_A, z, c, d], 
; N = 1, X = z, Es = [ a,_A, c, d] 
; N = 2, X = c, Es = [ a, z,_A, d], 
; N = 3, X = d, Es = [ a, z, c,_A] 
; false. 

?- list_nth0_item_replaced__NEW([a,b,c,d], N, X, Xs). 
    N = 0, Xs = [X,b,c,d] 
; N = 1, Xs = [a,X,c,d] 
; N = 2, Xs = [a,b,X,d] 
; N = 3, Xs = [a,b,c,X] 
; false. 

看起來沒問題！

Answer 8

我想出了另一種方法，我認爲這是正確的（？）。我不知道運行時複雜性。

replace(I, L, E, K) :- 
    nth0(I, L, _, R), 
    nth0(I, K, E, R). 

用法：

?- replace(2, [1, 2, 3, 4, 5], 10, X). 
X = [1, 2, 10, 4, 5].