Get and replace elements in 2d array using recursion

Help! Predicate
,
1

I`d like to have a procedure for replacing elements in matrix like:

replace(Matrix, I, J, New_value, New_matrix)

Example:

?- replace([[1,2,3],[4,5,6],[7,8,9]],0,1,5,Result).

   Result = [[1,5,3],[4,5,6],[7,8,9]]

There is a need to use recursion.
Thanks for your help!

2 
replace_matrix(INth0, JNth0, NewVal, Matrix, NewMatrix) :-
    must_be(nonneg, INth0), 
    must_be(nonneg, JNth0),
    % I and J becomes the list of levels
    replace_matrix_(Matrix, [INth0, JNth0], NewVal, NewMatrix).

replace_matrix_([H|T], [Nth0|LevelsT], NewVal, NewMatrix) :-
    % Nth0 is the current position on current level
    (   Nth0 > 0
    ->  Nth0Prev is Nth0 - 1,
        NewMatrix = [H|NewMatrix1],
        Levels1 = [Nth0Prev|LevelsT],
        % Iterate through the list to the desired element
        replace_matrix_(T, Levels1, NewVal, NewMatrix1)
    ;   LevelsT = []
        % Replace this element, because am at the lowest level
    ->  NewMatrix = [NewVal|T]
    ;   NewMatrix = [NewElem|T],
        % Drill down into next level of the matrix
        replace_matrix_(H, LevelsT, NewVal, NewElem)
    ).

Result:

?- time(replace_matrix(0, 1, X, [[1,2,3],[4,5,6],[7,8,9]],Result)).
% 15 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 319373 Lips)
Result = [[1,X,3],[4,5,6],[7,8,9]].

Note the changed argument order.

3

For replacing the nth item in a list:

replace_nth(N, OldElem, NewElem, List, List2) :-
    length(L1, N),
    append(L1, [OldElem|Rest], List),
    append(L1, [NewElem|Rest], List2).

?- replace_nth(2, OldElem, 666, [0,1,2,3,4,5,6,7], Replaced).
OldElem = 2,
Replaced = [0, 1, 666, 3, 4, 5, 6, 7].

and then combine them:

replace_m_n(Matrix, I, J, NewValue, NewMatrix) :-
    replace_nth(I, Old1, New1, Matrix, NewMatrix),
    replace_nth(J, _OldElem2, NewValue, Old1, New1).

As for recursion: append/3 is recursive:

append([], List, List).
append([X|Xs], Ys, [X|Zs]) :-
    append(Xs, Y, Zs).

and so is length/2:

length([], 0).
length([_|Xs], Len) :-
    when((nonvar(Len);nonvar(Len2)), succ(Len2, Len)),
    length(Xs, Len2).
3 Likes
4

I’ve just seen this length/2 definition on stackoverflow also. Surely this is far better (although not as fast as the builtin length/2:

length_slower_than_builtin(Lst, Len) :-
    (nonvar(Len) -> Once = true ; Once = false),
    length_slower_than_builtin_(Lst, 0, Len),
    % To prevent infinite loop with e.g. length_slower_than_builtin(Lst, 1)
    (Once = true -> ! ; true).

length_slower_than_builtin_([], Len, Len).
length_slower_than_builtin_([_|T], Upto, Len) :-
    Upto1 is Upto + 1,
    length_slower_than_builtin_(T, Upto1, Len).

Performance comparison:

?- numlist(1, 200000, Lst), time(length_when(Lst, Len)).
% 5,400,009 inferences, 3.233 CPU in 3.214 seconds (101% CPU, 1670314 Lips)

?- numlist(1, 200000, Lst), time(length_slower_than_builtin(Lst, Len)).
% 200,002 inferences, 0.008 CPU in 0.008 seconds (100% CPU, 24801254 Lips)