如何使谓词用指定的新值替换列表中给定元素的最后一次出现

Question

你能帮我吗，我不知道怎么做：用指定的新值替换列表中给定元素最后一次出现的replace_last谓词

replace_last(InList, OutList) :-
append([[First], Middle, [Last]], InList),
append([[Last], Middle, [First]], OutList).

Answer 1

我会使用否定：

replace_last(Input,Find,Replace,Output) :-
append(X,[Find|Y],Input),
+ memberchk(Find,Y),
append(X,[Replace|Y],Output).

Answer 2

使用回溯：

replace_last_elem_match(Find, Replacement, Lst, LstReplaced) :-
last_elem_match_copy(Find, Lst, LstReplaced, Tail, After),
Tail = [Replacement|After].
last_elem_match_copy(Find, Lst, LstReplaced, Tail, After) :-
last_elem_match_copy_(Lst, Find, LstReplaced, Tail, After).
last_elem_match_copy_([H|T], Find, [H|LstReplaced], Tail, After) :-
last_elem_match_copy_(T, Find, LstReplaced, Tail, After), !.
last_elem_match_copy_([Find|T], Find, Tail, Tail, T).

swi-prolog中的结果：

?- time(replace_last_elem_match(a, z, [a,a,b,a,c,a], R)).
% 9 inferences, 0.000 CPU in 0.000 seconds (87% CPU, 399078 Lips)
R = [a,a,b,a,c,z].

然而，@CapelliC的解决方案更快(可能是因为memberchk在swi-prolog中是原生的(-性能比较：

?- numlist(1, 1_000_000, L), time(replace_last_elem_match(99999, z, L, R)).
% 1,000,003 inferences, 1.469 CPU in 1.472 seconds (100% CPU, 680792 Lips)
?- numlist(1, 1_000_000, L), time(replace_last(L, 99999, z, R)).
% 200,001 inferences, 0.023 CPU in 0.024 seconds (100% CPU, 8517234 Lips)

?- length(L, 1_000_000), maplist(=(a), L), time(replace_last_elem_match(a, z, L, R)).
% 1,000,003 inferences, 0.696 CPU in 0.698 seconds (100% CPU, 1436214 Lips)
?- length(L, 1_000_000), maplist(=(a), L), time(replace_last(L, a, z, R)).
% 4,000,001 inferences, 0.453 CPU in 0.454 seconds (100% CPU, 8824459 Lips)

Answer 3

我想你可以用append/3来做这件事，但这似乎像是用猎枪拍苍蝇：

replace_last( A , Bs , Cs ) :-
append( B1 , [_] , Bs ) ,
append( B1 , [A] , Cs )
.

但这比这更简单或更容易理解吗？

replace_last( A , [_]    , [A]    ) .
replace_last( A , [B|Bs] , [B|Cs] ) :- replace_last(A,Bs,Cs) .

你可以在https://swish.swi-prolog.org/p/tAnrXzKn.pl

Answer 4

我认为这是迄今为止发现的最快的方法：

last_match_replace(Find, Replace, Lst, LstReplaced) :-
phrase(last_match_replace_(Find, Replace, LstReplaced, Tail), Lst, Tail), !.
last_match_replace_(Find, Replace, Before, BeforeTail, Lst, [Replace|Rem]) :-
match_find(Lst, Find, Before, BeforeTail, Rem),
+ memberchk(Find, Rem).
match_find([Find|L], Find, T, T, L). 
match_find([E|L], Find, [E|T], Tail, Rem) :-
match_find(L, Find, T, Tail, Rem).

swi-prolog中的结果：

?- numlist(1, 1_000_000, L), time(last_match_replace(99999, z, L, R)).
% 100,011 inferences, 0.028 CPU in 0.028 seconds (100% CPU, 3514803 Lips)
?- length(L, 1_000_000), maplist(=(a), L), time(last_match_replace(a, z, L, R)).
% 3,000,010 inferences, 0.177 CPU in 0.177 seconds (100% CPU, 16962407 Lips)