Я хотел бы иметь предикат Prolog, который может заменить элемент в списке по указанному индексу.
Пример:
% replace(+List,+Index,+Value,-NewList).
?- L=[a,b,c,d], replace(L,1,z,L2).
L2 = [a,z,c,d]
Я не знаю, как это сделать. Спасибо за вашу помощь! Лоик.
Я дам вам базовый случай, я думаю, что вы должны быть в состоянии сделать рекурсивный случай с легкостью:
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, если есть хорошая замена в границах.
Ответ от 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. последнее должно действительно быть последним средством. Этот метод использует больше памяти потому что для этого нужен как огромный термин, так и список. Наконец, функторы (пары имя/арность) в настоящее время не исправлены, поэтому вы создаете один такой объект для каждой замены списка с длиной, на которой это никогда не использовался.
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).
Действительно, никто никогда не должен делать это с помощью простых списков любой IMO значительной длины, так как каждое обновление будет занимать новое место O(n). Прямое set_once/update через setarg/nb_setarg займет 0 новое пространство и с бинарным древовидным представлением списков, O(log(n)) новое пространство. Замены могут также храниться в отдельном словаре, который сам по себе поддерживается как дерево (поскольку он должен расти). Перемещенный список (в виде здесь) может содержать большие куски в дереве, каждый из которых представляет собой составной термин фиксированного размера, который может быть установлен/обновляться через setarg/nb_setarg, и добавьте новые куски в дерево по мере необходимости.
Даже без обновления, просто доступ к простым спискам безнадежно медленный, O(n) время, превращая любой алгоритм квадратичным в jiffy. Списки только хорошие, очень короткие, или как домашнее задание.
Если мы используем same_length/2, append/3 и length/2, нам не нужно писать рекурсивный код:
Пример запроса, заданного 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.
Представленный код в этом предыдущем ответе довольно разносторонний, благодаря clpfd.
Есть ли недостаток? Да, есть недостаток: Неэффективность!
В этом ответе мы повышаем производительность и сохраняем универсальность.
<Предварительно > : - use_module (библиотека (clpfd)).Как сделать это прямолинейным способом?
<Предварительно > : - 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.
Еще один способ, который я считаю правильным (?). Я не знаю о сложности выполнения.
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].