Рекурсивный поиск & Аккумуляторы и счетчики в Прологе

Question

После долгого поиска в google я не мог найти ясного ответа на этот вопрос: В Prolog делать рекурсию самостоятельно легко. Моя основная проблема заключается в понимании, где разместить аккумуляторы и счетчики. Ниже приведен пример:

nXlist(N,X,[X|T]):- 
    N \=0, 
    N1 is N-1, 
    nXList(N1,X,T). 
nXList(0,_,[]). 

media([X|L], N, Soma):- 
    media(L, N1, Soma1), 
    N is N1 + 1, 
    Soma is Soma1 + X. 
media([], 0, 0). 

В первом примере я использовал счетчик ПЕРЕД рекурсии, но во втором примере я использую его ПОСЛЕ. Причина, по которой я это сделал, - это вызванная попытка и увидеть причину, по которой я действительно не могу понять, почему иногда бывает до и иногда после ...

Answer 1

update: Самое главное, если рекурсивный вызов не последний, предикат не является хвостом рекурсивным. Поэтому, если возможно, следует избегать чего-либо после рекурсивного вызова. Обратите внимание, что оба определения в the answer на user false- это рекурсивные хвосты, и это связано именно с тем, что арифметические условия там размещены до рекурсивного вызова в обоих из них. Это так важно, что мы должны приложить усилия, чтобы заметить это явно.

---

Иногда мы отсчитываем, иногда подсчитываем. Я обсуждаю это в another answer. В нем рассказывается о аккумуляторах, пресах и увяданиях. :)

Там же эта вещь называется «ассоциативность» из операции (скажем, +), где

a+(b+(c+....)) == (a+b)+(c+...) 

, что позволяет нам перегруппироваться и (частично) вычислить раньше, чем позже. Как можно скорее, но не раньше.

Answer 2

Короткий ответ: вы можете разместить такие арифметические отношения как до, так и после этого. По крайней мере, если вы используете ограничения вместо (is)/2. Единственное отличие может заключаться в прекращении и ошибках.

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

:- use_module(library(clpfd)). 

nXList(0,_,[]). 
nXList(N,X,[X|T]):- 
    N #> 0, 
    N1 #= N-1, 
    nXList(N1,X,T). 

media([], 0, 0). 
media([X|L], N, Soma):- 
    N #> 0, 
    N #= N1 + 1, 
    Soma #= Soma1 + X, 
    media(L, N1, Soma1). 

Теперь вы можете использовать эти определения в гораздо более общем виде, скажем:

?- nXList(3, X, T). 
T = [X, X, X] ; 
false. 

?- media(Xs, 3, S). 
Xs = [_A, _B, _C], 
_D+_A#=S, 
_C+_B#=_D ; 
false. 

... nXList/3 может более компактно выражается:

..., length(T, N), maplist(=(X), T), ... 

Answer 3

Возможно, центральная точка зрения г Вопрос заключается в преамбуле:

В Прологе делать рекурсию сама его легко

Это не легко, это обязательным. У нас нет циклов, потому что у нас нет способа контролировать их. Переменные назначают один раз.

Так что, я думаю, что практический ответ довольно прост: если «предикат» (как есть/2) нуждается значения переменного, вы заземлить переменную перед тем называть его.

Для меня это помогает рассматривать программу Prolog (набор предложений) как произведения грамматики и аргументы предложения как атрибуты, либо наследуемые (значения, вычисленные перед «указателем инструкции»), либо синтезированные (значения, вычисленные здесь «здесь», , который будет возвращен).