'Prolog: replace the nth item in the list with the first

I'd like to have a Prolog predicate that can replace the nth item in the list with the first.

Example:

% replace(+List,+Counter,-New List, %-First Item).
?- replace([1,2,3,4,5],3,L,Z).

L = [1, 2, 1, 4, 5]
Z = 1

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

listprolog


Solution 1:[1]

Try using the predicate nth1(Index, List, Item, Rest):

?- nth1(3, [1,2,3,4,5], Item, Rest).
Item = 3,
Rest = [1, 2, 4, 5].

?- nth1(3, List, 1, [1,2,4,5]).
List = [1, 2, 1, 4, 5].

Putting it all together:

replace(List, Index, NewList, First) :-
    List = [First|_],
    nth1(Index, List, _Removed, Rest),
    nth1(Index, NewList, First, Rest).

Examples:

?- replace([1,2,3,4,5], 3, L, Z).
L = [1, 2, 1, 4, 5],
Z = 1.

?- replace([one,two,three,four,five], 4, NewList, First).
NewList = [one, two, three, one, five],
First = one.

Solution 2:[2]

Another method, slightly faster (replacing succ/2 with simple arithmetic helped performance):

replace_nth_with_first(Nth1, Lst, LstReplaced, First) :-
    must_be(positive_integer, Nth1),
    Lst = [First|_Tail],
    replace_nth_with_first_(Nth1, Lst, LstReplaced, First).

% Keeping the arguments simple, to ensure that Nth1 = 1 matches
replace_nth_with_first_(1, Lst, LstReplaced, First) :-
    !,
    Lst = [_Head|Tail],
    LstReplaced = [First|Tail].
replace_nth_with_first_(Nth1, [H|Lst], [H|LstReplaced], First) :-
    Nth is Nth1 - 1,
    replace_nth_with_first_(Nth, Lst, LstReplaced, First).

Result in swi-prolog:

?- replace_nth_with_first(3, [a, b, c, d, e], R, F).
R = [a,b,a,d,e],
F = a.

Performance comparison:

?- numlist(1, 2000000, L), time(replace_nth_with_first(1000000, L, R, First)).
% 1,000,004 inferences, 0.087 CPU in 0.087 seconds (100% CPU, 11428922 Lips)

% slago's
?- numlist(1, 2000000, L), time(replace_f(L, 1000000, R, First)).
% 2,000,011 inferences, 0.174 CPU in 0.174 seconds (100% CPU, 11484078 Lips)

Note the argument order, as per https://swi-prolog.discourse.group/t/split-list/4836/8

Solution 3:[3]

You might use append/3. Nice, concise, and declarative:

replace( [X|Xs] , 1 , [X|Xs], X ) .  % replacing the first item in the list is a no-op
replace( Ls     , I , L1    , X ) :- % for anything else...
  I > 1 ,                            % - the index must be greater than 1
  J is I-1 ,                         % - the length of the prefix is I-1
  length( [X|Xs], J ) ,              % - construct an empty/unbound prefix list of the desired length
  append( [X|Xs] , [_|Ys] , Ls ) ,   % - break the source list up into the desired bits
  append( [X|Xs] , [X|Ys] , L1 )     % - and then put everything back together in the desired manner
  .                                  % Easy!

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 slago
Solution 2
Solution 3 Nicholas Carey

Related Questions