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

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

10 голосов
/ 20 марта 2012

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

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

Ответы [ 5 ]

9 голосов
/ 20 марта 2012

Предикат Пролога - это отношение между аргументами и вашим утверждением

элемент в позиции 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 может вывести определенность решения.

7 голосов
/ 20 марта 2012

Это происходит потому, что, когда Prolog оценивает подцель K > 1, 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 снова начинает обработку на следующей паре элементов .

РЕДАКТИРОВАТЬ: Удалено неправильное сокращение в первом пункте posAt/4 (спасибо @chac за подбор)

2 голосов
/ 09 февраля 2016

TL; DR: Ответы @ CAFEBABE , @ CapelliC , @ mat и @ sharky все не хватает!

Итак ... что же точно являются недостатками ответов, предложенных ранее?

  • @ CAFEBABE заявлено:

    Приятно, что в этом решении время выполнения линейно по длине обоих списков.

    Давайте проверим это утверждение! 

    ?- numlist(1,1000,Zs), time(posAt__CAFEBABE1(Zs,1000,Zs)).
% <b>999,001</b> 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.

    Облом! Остальные прекрасно справляются: 

    <sub>?- numlist(1,1000,Zs), time(posAt__CapelliC1(Zs,1000,Zs)).
% <b>671</b> 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)).
% <b>3,996</b> 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)).
% <b>1,000</b> 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.
</sub>

  • @ CapelliC использовал nth1/3, что может (и может) вызвать проблемы с универсальным завершением: 

    ?- time((posAt__CapelliC1(_,N,[a,b,c]), false)).
<b>**LOOPS**</b>

    D'Oh! Все остальные прекрасно справляются: 

    <sub>?- time((posAt__CAFEBABE1(_,_,[a,b,c]), false)).
% 14 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 1098470 Lips)
<b>false</b>.

?- time((posAt__mat1(_,_,[a,b,c]), false)).
% 2,364 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 2764075 Lips)
<b>false</b>.

?- time((posAt__sharky1(_,_,[a,b,c]), false)).
% 6 inferences, 0.000 CPU in 0.000 seconds (89% CPU, 207247 Lips)
<b>false</b>.
</sub>

  • Код @ mat имеет проблемы со сложностью. @CAFEBABE и @CapelliC делают «немного лучше» - их коды работают быстрее, потому что они используют примитивы более низкого уровня (is)/2 и nth1/3. 

    ?- numlist(1,1000,Zs), time((posAt__mat1(Zs,_,_), false)).
% <b>33,365,972</b> inferences, 1.643 CPU in 1.643 seconds (100% CPU, 20304661 Lips)
false.

?- numlist(1,1000,Zs), time((posAt__CAFEBABE1(Zs,_,_), false)).
% <b>1,001,002</b> inferences, 0.083 CPU in 0.083 seconds (100% CPU, 12006557 Lips)
false.

?- numlist(1,1000,Zs), time((posAt__CapelliC1(Zs,_,_), false)).
% <b>171,673</b> inferences, 0.030 CPU in 0.030 seconds (100% CPU, 5810159 Lips)
false.

    Код @sharky явно лучший в этом отношении: 

    <sub>?- numlist(1,1000,Zs), time((posAt__sharky1(Zs,_,_), false)).
% <b>1,003</b> inferences, 0.001 CPU in 0.001 seconds (100% CPU, 1605658 Lips)
false.
</sub>

  • В коде @ sharky используется встроенный мета-логический предикат (==)/2, что приводит к потере логической устойчивости при использовании с недостаточно конкретизированными терминами. Этот запрос должен быть выполнен успешно: 

    ?- posAt__sharky1([a], 1, Xs).
<b>false</b>.

    Все остальные коды дают логически обоснованный ответ: 

    <sub>?- posAt__CAFEBABE1([a], 1, Xs).
<b>Xs = [a|_G235]</b> ;
false.

?- posAt__CapelliC1([a], 1, Xs).
<b>Xs = [a|_G235]</b>.

?- posAt__mat1([a], 1, Xs).
<b>Xs = [a|_G235]</b> ;
false.
</sub>

  • Проходя мимо первого ответа, код @ 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|...] ;
% <b>999,004</b> inferences, 0.076 CPU in 0.076 seconds (100% CPU, 13121058 Lips)
false.

    Аналогично & mdash; но на порядок меньше & mdash; проблемы с кодом @ sharky: 

    <sub>?- 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|...] ;
% <b>1,003</b> inferences, 0.001 CPU in 0.001 seconds (100% CPU, 1078556 Lips)
false.</sub>

    С кодами @CapelliC и @mat все в порядке: 

    <sub>?- numlist(1,1000,Zs), time(posAt__CapelliC1(Zs,1,Zs)).
% <b>7</b> 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|...] ;
% <b>5</b> inferences, 0.000 CPU in 0.000 seconds (84% CPU, 345662 Lips)
false.
</sub>

Итак ... что нам делать? Почему бы не следовать этому подходу и объединить код @ mat и @ sharky? 

:- use_module(<a href="http://eu.swi-prolog.org/man/clpfd.html" rel="nofollow noreferrer">library(clpfd)</a>).

posAt__NEW(L0, Pos, L1) :- 
    posAt__NEW_(L0, 1, Pos, L1).

posAt__NEW_([<b>X</b>|_], Pos, Pos, [<b>X</b>|_]).
posAt__NEW_([_|X0s], CurrPos, Pos, [_|X1s]) :-
    <b>CurrPos<a href="http://www.swi-prolog.org/pldoc/doc_for?object=%23%3C%20/%202" rel="nofollow noreferrer"> #< </a>Pos,</b>
    NextPos<b><a href="http://www.swi-prolog.org/pldoc/doc_for?object=%23%3D%20/%202" rel="nofollow noreferrer"> #= </a></b>CurrPos + 1,
    posAt__NEW_(X0s, NextPos, Pos, X1s).

Давайте снова запустим приведенные выше примеры запросов с помощью posAt__NEW/3: 

<sub>?- numlist(1,1000,Zs), time(posAt__NEW(Zs,1000,Zs)).
% <b>4,997</b> 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)
<b>false</b>.

?- numlist(1,1000,Zs), time((posAt__NEW(Zs,_,_), false)).
% <b>154,955</b> inferences, 0.014 CPU in 0.014 seconds (100% CPU, 11067900 Lips)
false.

?- posAt__NEW([a], 1, Xs).
<b>Xs = [a|_G229]</b> ;
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|...] ;
% <b>7</b> inferences, 0.000 CPU in 0.000 seconds (86% CPU, 266748 Lips)
false.
</sub>

Хорошо! Наконец, мы убедились, что цель, использованная в приведенном выше запросе 3 rd , имеет linear сложность: 

<sub>?- numlist(1,100,Zs), time((posAt__NEW(Zs,_,_), false)).
% <b>15,455</b> inferences, 0.004 CPU in 0.004 seconds (100% CPU, 3545396 Lips)
false.

?- numlist(1,1000,Zs), time((posAt__NEW(Zs,_,_), false)).
% <b>154,955</b> inferences, 0.016 CPU in 0.017 seconds (98% CPU, 9456629 Lips)
false.

?- numlist(1,10000,Zs), time((posAt__NEW(Zs,_,_), false)).
% <b>1,549,955</b> inferences, 0.098 CPU in 0.099 seconds (99% CPU, 15790369 Lips)
false.

?- numlist(1,100000,Zs), time((posAt__NEW(Zs,_,_), false)).
% <b>15,499,955</b> inferences, 1.003 CPU in 1.007 seconds (100% CPU, 15446075 Lips)
false.
</sub>
2 голосов
/ 09 февраля 2016

(Это только что появилось на моей панели, отсюда и поздний ответ ...)

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

однако, это время трудно, следовательно, решение hackish примерно эквивалентно 

  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
2 голосов
/ 02 декабря 2015

Общее решение для таких проблем: ограничения .

Используйте для целочисленной арифметики, которая работает во всех направлениях: 

:- 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]).
<b>X = 2</b> ;
false.
...