Prolog: replace an element in a list at a specifie

Question

I'd like to have a Prolog predicate that can replace an element in a list at a specified index.

Example:

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

I don't know how to do this. Thanks for your help! Loïc.

Answer 1

I'll give you the base case, I think you should be able to do the recursive case with ease:

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

edit:

Now that the op has solved it, I'll add the recursive case:

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

edit2:

This should return the original list in an out of bounds situation as @GeorgeConstanza asks in the comments:

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

It's basically taking advantage of the cut operator to not get to the third fallback clause if there's a good in-bounds replacement.

Answer 2

Another way I came up with, which I think is correct (?). I don't know about the runtime complexity.

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

Usage:

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

Answer 3

The code presented in this previous answer is quite versatile—thanks to clpfd.

Is there a downside? Yes, there is a downside: Inefficiency!

In this answer, we improve performance and preserve versatility.

:- use_module(library(clpfd)).

We proceed like this previous answer did when it defined the predicate 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).

So... has it gotten any faster?

?- 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, it is faster. But is it still versatile?

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

Looks alright to me!

Answer 4

Really, nobody should ever do this with plain lists of any considerable length IMO, as each update will take up O(n) new space. Direct set_once/update via setarg/nb_setarg will take up 0 new space, and with binary tree representation of lists, O(log(n)) new space. The replacements could also be held in a separate dictionary, itself maintained as a tree (as it needs to grow). A chunked list (as in here) could hold big chunks in a tree, each a fixed-sized compound term directly settable/updatable through setarg/nb_setarg, and add new chunks into the tree as needed.

Even without the update, just accessing plain lists is hopelessly slow, O(n) time, turning any algorithm quadratic in a jiffy. Lists are only good really short, or as a homework exercise.

Answer 5

ok clearly the replace using recursion by @fortran is the the way to go. but is this too crazy/slow to actually use?

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

Basically you make a blank array of size Idx and bind it to the input list. then discard the item after that and bind the two lists together with the replacement element sandwiched in.

this can be simplified further if you are OK failing if you try to set idx N (indexing from 0) of an N element list.

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

Answer 6

The answer from fortran it's ok, but in SWI-Prolog structs have unlimited arity, so this should work:

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

but, to my surprise:

?- % /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

My first attempt (with K=10000000) killed the process! So, to my dislike, attempting to gain some performance, I end up filling a bug report to SWI-Prolog mailing list...

EDIT: After the post to SWI-Prolog mailing list, and the (fast!) correction, I have rebuilt, and here is the version accounting for a hint on memory usage (now it's all ISO standard code!). Due to the unusual large values, a stack grow instruction is needed before:

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

Here is the updated procedure:

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

and the test:

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

The code it's faster, but please note the comment of Jan to my mail:

Boils down to poor error handling in =..(+,-). Fixed. B.t.w. I think this is pretty horrible way to do the job. Even if you want to do it this way, simply use setarg/3 instead of nb_setarg/3. The latter should really be a last resort. This method uses more memory because it needs both the huge term and the list. Finally, functors (name/arity pairs) are currently not reclaimed, so you create one such object for each replace of a list with a length on which this was never used.