Prolog: заменить элемент в списке по указанному индексу

Я хотел бы иметь предикат Prolog, который может заменить элемент в списке по указанному индексу.

Пример:

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

Я не знаю, как это сделать. Спасибо за вашу помощь! Лоик.

Ответы

Ответ 1

Я дам вам базовый случай, я думаю, что вы должны быть в состоянии сделать рекурсивный случай с легкостью:

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

изменить

Теперь, когда op решил это, я добавлю рекурсивный случай:

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

В основном он использует оператор cut, чтобы не попасть в третье предложение fallback, если есть хорошая замена в границах.

Ответ 2

Ответ от 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.

Код быстрее, но обратите внимание на комментарий Яна к моей почте:

Сбрасывается до плохой обработки ошибок в =.. (+, -). Исправлена. B.t.w. я подумайте, что это довольно ужасный способ выполнить эту работу. Даже если вы хотите Чтобы сделать это, просто используйте setarg/3 вместо nb_setarg/3. последнее должно действительно быть последним средством. Этот метод использует больше памяти потому что для этого нужен как огромный термин, так и список. Наконец, функторы (пары имя/арность) в настоящее время не исправлены, поэтому вы создаете один такой объект для каждой замены списка с длиной, на которой это никогда не использовался.

Ответ 3

ok ясно, что замена, использующая рекурсию на @fortran, - это путь. но это слишком сумасшедший/медленный, чтобы фактически использовать?

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

В основном вы делаете пустой массив размера Idx и привязываете его к списку ввода. затем отбросьте элемент после этого и свяжите два списка вместе с заменяемым элементом, зажатым в.

это может быть упрощено, если вы ошибетесь, если вы попытаетесь установить idx N (индексирование из 0) списка элементов N.

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

Ответ 4

Действительно, никто никогда не должен делать это с помощью простых списков любой IMO значительной длины, так как каждое обновление будет занимать новое место O(n). Прямое set_once/update через setarg/nb_setarg займет 0 новое пространство и с бинарным древовидным представлением списков, O(log(n)) новое пространство. Замены могут также храниться в отдельном словаре, который сам по себе поддерживается как дерево (поскольку он должен расти). Перемещенный список (в виде здесь) может содержать большие куски в дереве, каждый из которых представляет собой составной термин фиксированного размера, который может быть установлен/обновляться через setarg/nb_setarg, и добавьте новые куски в дерево по мере необходимости.

Даже без обновления, просто доступ к простым спискам безнадежно медленный, O(n) время, превращая любой алгоритм квадратичным в jiffy. Списки только хорошие, очень короткие, или как домашнее задание.

Ответ 5

Если мы используем same_length/2, append/3 и length/2, нам не нужно писать рекурсивный код:

<Предварительно > list_nth0_item_replaced (Es, N, X, Xs): - same_length (Es, Xs), append (префикс, [_ | Суффикс], Es), length (префикс, N), append (Префикс, [X | Суффикс], Xs).

Пример запроса, заданного OP:

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

Ответ 6

Представленный код в этом предыдущем ответе довольно разносторонний, благодаря clpfd.

Есть ли недостаток? Да, есть недостаток: Неэффективность!

В этом ответе мы повышаем производительность и сохраняем универсальность.

<Предварительно > : - use_module (библиотека (clpfd)).

Мы продолжаем как

Ответ 7

Как сделать это прямолинейным способом?

<Предварительно > : - use_module (библиотека (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.

Выше код чист, поэтому мы можем запросить более общие запросы &mdash и ожидать логически правильные ответы:

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

Ответ 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].