Простая программа пролога. Ошибка при получении:>/2: Аргументы недостаточно

Я сделал предикат 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

Почему я получаю эту ошибку?

Ответы

Ответ 1

Предикат 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 способен вывести детерминированность решения.

Ответ 2

Это происходит потому, что, когда подкласс 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 для пикапа)

Ответ 3

Общее решение для таких задач - ограничения.

Использовать 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.

Ответ 4

(Это просто появилось на моей панели инструментов, следовательно, последний ответ...)

Я рассмотрел вопрос и думал, можно ли предложить решение, близкое к исходному вопросу. Проблема, как уже объяснялось, заключается в том, что для отношения > необходимы его аргументы. На самом деле аналогично для 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

Ответ 5

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.