Избегайте двойного рекурсивного вызова в Прологе - PullRequest
Новая
       33

Избегайте двойного рекурсивного вызова в Прологе

0 голосов
/ 13 февраля 2020

У меня есть код Пролога: 

f([ ],-1).

f([H|T],S):- f(T,S1), S1>0, !, S is S1+H.

f([_|T],S):- f(T,S1), S is S1.

Как мне избежать второго (избыточного) рекурсивного вызова f(T,S1), в третьем предложении общий эффект от предиката остается прежним?

Я знаю, что это можно сделать, определив дополнительный предикат.

Как можно определить такой предикат?

Ответы [ 2 ]

1 голос
/ 13 февраля 2020 
| ?- length(L,_), f(L,R).
   L = [],
   R = -1
;  L = [_A],
   R = -1
;  L = [_A,_B],
   R = -1
;  L = [_A,_B,_C],
   R = -1
;  L = [_A,_B,_C,_D],
   R = -1
;  L = [_A,_B,_C,_D,_E],
   R = -1
;  L = [_A,_B,_C,_D,_E,_F],
   R = -1
;  L = [_A,_B,_C,_D,_E,_F,_G],
   R = -1
;  L = [_A,_B,_C,_D,_E,_F,_G,_H],
   R = -1
;  L = [_A,_B,_C,_D,_E,_F,_G,_H,_I],
   R = -1
;  L = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J],
   R = -1 ...

Это звонит в колокол?

Хорошо, вот что я бы ответил: 

f(L, -1) :-
   length(L, _).

Хотя это теперь завершается и завершается ошибкой для f(L, 0), тогда как первоначальное определение петельные. Если вы настаиваете и на этой эквивалентности: 

f(L, MinusOne) :-
   length(L, _),
   MinusOne = -1.
0 голосов
/ 13 февраля 2020

Сначала мы переписываем это немного, чтобы лучше увидеть сходства, 

f([ ],-1).
f([H|T],S) :- f(T,S1), S1>0, !, S is S1+H.
f([H|T],S) :- f(T,S1),          S is S1.

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

f([ ],-1).
f([H|T],S) :- f(T,S1), additional_predicate(S1,S,H).

Теперь все, что осталось сделать, это написать те же цели под новым именем: 

additional_predicate(S1,S,H):- S1>0, !, S is S1+H.
additional_predicate(S1,S,H):- S is S1.

И это все.

Проще говоря, после того, как вызов f(T,S1) завершен, S1 уже рассчитан, поэтому нет необходимости заново его пересчитывать.

...