序言：替换指定索引处列表中的元素

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].