Я сделал предикат Prolog posAt(List1,P,List2), который проверяет, являются ли элементы в позиции P из List1 и List2 равными:
posAt([X|Z], 1, [Y|W]) :-
X = Y.
posAt([Z|X], K, [W|Y]) :-
K > 1,
Kr is K - 1,
posAt(X, Kr, Y).
При тестировании:
?- posAt([1,2,3], X, [a,2,b]).
Я ожидал вывод X = 2, но вместо этого получил следующую ошибку:
ERROR: >/2: Arguments are not sufficiently instantiated
Почему я получаю эту ошибку?
Предикат Prolog - это отношение между аргументами и ваш оператор
элемент в позиции P списка List1 и List2 равен
является, очевидно, примером, где возможны несколько решений.
?- posAt([1,2,3],X,[1,5,3,7]).
X = 1.
Итак, ответ от sharky, хотя ясно объясняет, почему возникает техническая ошибка, требуется небольшая коррекция:
posAt([X0|_], Pos, Pos, [X1|_]) :-
X0 == X1.
Теперь он работает так, как ожидалось.
?- posAt([1,2,3],X,[1,5,3,7]).
X = 1 ;
X = 3 ;
false.
Написание простых предикатов для обработки списка - это очень ценная практика ученичества и основной способ эффективного изучения языка. Если вы склонны также изучать доступные предикаты библиотеки, вот версия, использующая nth1/3 из библиотеки (lists)
posAt(L0, P, L1) :-
nth1(P, L0, E),
nth1(P, L1, E).
Выводится:
?- posAt([1,2,3],X,[1,5,3,7]).
X = 1 ;
X = 3.
Может быть интересно попытаться понять, почему в этом случае интерпретатор "верхнего уровня" SWI-Prolog способен вывести детерминированность решения.
Это происходит потому, что, когда подкласс K > 1 оценивается Prolog, K все еще является несвязанной переменной, а не числом. Стандартный пролог не может (не будет) оценивать истинное/ложное значение ограничений цифрового диапазона, например, когда они не измельчены (в отличие от решателей ограничений, таких как CLP, которые позволяют это, но работают по-другому).
Рассмотрим это решение:
posAt(L0, Pos, L1) :-
posAt(L0, 1, Pos, L1).
posAt([X0|_], Pos, Pos, [X1|_]) :-
X0 == X1.
posAt([_|X0s], CurrPos, Pos, [_|X1s]) :-
NextPos is CurrPos + 1,
posAt(X0s, NextPos, Pos, X1s).
Первый предикат posAt/3 устанавливает начальное условие: списки как позицию 1 и вызывает posAt/4 для повторения списка.
Первое предложение posAt/4 - условие соответствия: элементы в обоих списках в одной позиции равны. В этом случае текущая переменная позиции унифицирована с Pos, результатом.
Если предложение выше, потому что элементы списка X0 и X1 были неравными, позиция списка CurrPos увеличивается на единицу, а рекурсивный вызов posAt/4 начинает снова обрабатываться при следующей паре элементов.
EDIT: удалено неправильное вырезание в первом разделе posAt/4 (благодаря @chac для пикапа)
Общее решение для таких задач - ограничения.
Использовать clpfd для целочисленной арифметики, которая работает во всех направлениях:
:- use_module(library(clpfd)).
posAt([X|_], 1, [X|_]).
posAt([_|X], K, [_|Y]) :-
K #> 1,
Kr #= K - 1,
posAt(X,Kr,Y).
С помощью этих простых изменений ваш пример работает точно так, как ожидалось:
?- posAt([1,2,3], X, [a,2,b]). X = 2 ; false.
(Это просто появилось на моей панели инструментов, следовательно, последний ответ...)
Я рассмотрел вопрос и думал, можно ли предложить решение, близкое к исходному вопросу. Проблема, как уже объяснялось, заключается в том, что для отношения > необходимы его аргументы. На самом деле аналогично для is. Однако это можно легко устранить путем изменения целей:
posAt([X|_], 1, [X|_]).
posAt([_|X], K, [_|Y]) :-
posAt(X, Kr, Y),
K is Kr+1,
K > 1.
Это решение состоит в том, что время выполнения является линейным по длине обоих списков, пока K заземлен. Однако есть проблема, если первые элементы соответствуют списку, как хорошо проиллюстрированы в ответ повторением.
Фактически последний элемент лишний, следовательно, эквивалентен.
posAt([X|_], 1, [X|_]).
posAt([_|X], K, [_|Y]) :-
posAt(X, Kr, Y),
K is Kr+1.
Однако, как доказано @repeat, этот код ужасно медленный. это, вероятно, связано с тем, что код разрушает рекурсию хвоста.
Логическое чистое решение решит эту проблему. Здесь мы будем представлять натуральные числа, используя аксиомы Пеано (s/1 преемник или отношение), и решение станет
posAt([X|_], zero, [X|_]).
posAt([_|X], s(K), [_|Y]) :-
posAt(X, K, Y).
однако это непросто, поэтому хакерское решение примерно эквивалентно
posAt([X|_], [a], [X|_]).
posAt([_|X], [a|L], [_|Y]) :-
posAt(X, L, Y).
Сроки этого решения дают
N=8000,numlist(1,N,_Zs), length(_LN,N),time(posAt(_Zs,_LN,_Zs)).
7,999 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 7342035 Lips)
N = 8000
TL; DR: Ответы @CAFEBABE, @CapelliC, @mat и @sharky все не хватает!
Итак... каковы именно недостатки предложенных ранее ответов?
@CAFEBABE заявила:
Приятно об этом решении состоит в том, что время выполнения является линейным по длине обоих списков.
Положим это утверждение на тест!
?- numlist(1,1000,Zs), time(posAt__CAFEBABE1(Zs,1000,Zs)). % 999,001 inferences, 0.090 CPU in 0.091 seconds (100% CPU, 11066910 Lips) Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; % 4 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 66738 Lips) false.
Облом! Остальные прекрасно справляются:
?- numlist(1,1000,Zs), time(posAt__CapelliC1(Zs,1000,Zs)). % 671 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 3492100 Lips) Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...]. ?- numlist(1,1000,Zs), time(posAt__mat1(Zs,1000,Zs)). % 3,996 inferences, 0.001 CPU in 0.001 seconds (99% CPU, 3619841 Lips) Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; % 5 inferences, 0.000 CPU in 0.000 seconds (89% CPU, 154703 Lips) false. ?- numlist(1,1000,Zs), time(posAt__sharky1(Zs,1000,Zs)). % 1,000 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 2627562 Lips) Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; % 4 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 97109 Lips) false.
@CapelliC использует nth1/3, который может (и не вызывает) вызвать проблемы с универсальным завершением:
?- time((posAt__CapelliC1(_,N,[a,b,c]), false)). **LOOPS**
D'ах! Остальные все прекрасно справляются:
?- time((posAt__CAFEBABE1(_,_,[a,b,c]), false)). % 14 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 1098470 Lips) false. ?- time((posAt__mat1(_,_,[a,b,c]), false)). % 2,364 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 2764075 Lips) false. ?- time((posAt__sharky1(_,_,[a,b,c]), false)). % 6 inferences, 0.000 CPU in 0.000 seconds (89% CPU, 207247 Lips) false.
@mat имеет сложности.
@CAFEBABE и @CapelliC делают "немного лучше", их коды быстрее, потому что они используют полагаться на примитивы нижнего уровня (is)/2 и nth1/3.
?- numlist(1,1000,Zs), time((posAt__mat1(Zs,_,_), false)). % 33,365,972 inferences, 1.643 CPU in 1.643 seconds (100% CPU, 20304661 Lips) false. ?- numlist(1,1000,Zs), time((posAt__CAFEBABE1(Zs,_,_), false)). % 1,001,002 inferences, 0.083 CPU in 0.083 seconds (100% CPU, 12006557 Lips) false. ?- numlist(1,1000,Zs), time((posAt__CapelliC1(Zs,_,_), false)). % 171,673 inferences, 0.030 CPU in 0.030 seconds (100% CPU, 5810159 Lips) false.
В этом отношении лучше всего работает код @sharky:
?- numlist(1,1000,Zs), time((posAt__sharky1(Zs,_,_), false)). % 1,003 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 1605658 Lips) false.
В коде @sharky используется мета-логический встроенный предикат (==)/2, который заставляет его терять логическую устойчивость при использовании с недостаточно инстанцированными терминами. Этот запрос должен быть успешным:
?- posAt__sharky1([a], 1, Xs). false.
Другие коды дают логически обоснованный ответ:
?- posAt__CAFEBABE1([a], 1, Xs). Xs = [a|_G235] ; false. ?- posAt__CapelliC1([a], 1, Xs). Xs = [a|_G235]. ?- posAt__mat1([a], 1, Xs). Xs = [a|_G235] ; false.
Пройдя первый ответ, код @CAFEBABE получает меньше :
?- numlist(1,1000,Zs), time(posAt__CAFEBABE1(Zs,1,Zs)). % 0 inferences, 0.000 CPU in 0.000 seconds (93% CPU, 0 Lips) Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; % 999,004 inferences, 0.076 CPU in 0.076 seconds (100% CPU, 13121058 Lips) false.
Аналогичный, но на порядок меньше; проблемы отображаются с кодом @sharky:
?- numlist(1,1000,Zs), time(posAt__sharky1(Zs,1,Zs)). % 1 inferences, 0.000 CPU in 0.000 seconds (75% CPU, 31492 Lips) Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; % 1,003 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 1078556 Lips) false.
Коды @CapelliC и @mat работают нормально:
?- numlist(1,1000,Zs), time(posAt__CapelliC1(Zs,1,Zs)). % 7 inferences, 0.000 CPU in 0.000 seconds (85% CPU, 306802 Lips) Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...]. ?- numlist(1,1000,Zs), time(posAt__mat1(Zs,1,Zs)). % 0 inferences, 0.000 CPU in 0.000 seconds (80% CPU, 0 Lips) Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; % 5 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 345662 Lips) false.
Итак... что мы будем делать? Почему бы не следовать этому подходу и объединить код @mat и @sharky?
<Предварительно > : - use_module (библиотека (clpfd)). posAt__NEW (L0, Pos, L1): - posAt__NEW_ (L0, 1, Pos, L1). posAt__NEW _ ([ X | _], Pos, Pos, [ X | _]). posAt__NEW _ ([_ | X0s], CurrPos, Pos, [_ | X1s]): - CurrPos # < Позы, NextPos # = CurrPos + 1, posAt__NEW_ (X0s, NextPos, Pos, X1s).Повторите предыдущие примеры запросов с помощью posAt__NEW/3:
?- numlist(1,1000,Zs), time(posAt__NEW(Zs,1000,Zs)). % 4,997 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 18141619 Lips) Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; % 9 inferences, 0.000 CPU in 0.000 seconds (71% CPU, 122877 Lips) false. ?- time((posAt__NEW(_,_,[a,b,c]), false)). % 440 inferences, 0.001 CPU in 0.001 seconds (98% CPU, 803836 Lips) false. ?- numlist(1,1000,Zs), time((posAt__NEW(Zs,_,_), false)). % 154,955 inferences, 0.014 CPU in 0.014 seconds (100% CPU, 11067900 Lips) false. ?- posAt__NEW([a], 1, Xs). Xs = [a|_G229] ; false. ?- numlist(1,1000,Zs), time(posAt__NEW(Zs,1,Zs)). % 1 inferences, 0.000 CPU in 0.000 seconds (93% CPU, 121818 Lips) Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; % 7 inferences, 0.000 CPU in 0.000 seconds (86% CPU, 266748 Lips) false.
Хорошо! Наконец, мы убеждаемся, что цель, использованная в запросе 3 rd выше, имеет линейную сложность:
?- numlist(1,100,Zs), time((posAt__NEW(Zs,_,_), false)). % 15,455 inferences, 0.004 CPU in 0.004 seconds (100% CPU, 3545396 Lips) false. ?- numlist(1,1000,Zs), time((posAt__NEW(Zs,_,_), false)). % 154,955 inferences, 0.016 CPU in 0.017 seconds (98% CPU, 9456629 Lips) false. ?- numlist(1,10000,Zs), time((posAt__NEW(Zs,_,_), false)). % 1,549,955 inferences, 0.098 CPU in 0.099 seconds (99% CPU, 15790369 Lips) false. ?- numlist(1,100000,Zs), time((posAt__NEW(Zs,_,_), false)). % 15,499,955 inferences, 1.003 CPU in 1.007 seconds (100% CPU, 15446075 Lips) false.