пролог - сумма рекурсивного предиката (J, K, N) - PullRequest
Новая
       5

пролог - сумма рекурсивного предиката (J, K, N)

0 голосов
/ 07 марта 2020

Я пытаюсь решить упражнение из книги «Прологическое углубленное программирование».

Определить рекурсивный предикат сумма (J, K, N) , которая создает экземпляр N до суммы целых чисел от J до K включительно: 

?- sum(-1,1,What).
What = 0
?- sum(1,3,What).
What = 6
?- sum(6,7,What).
What = 13

Мой предикат ниже. 

sum(J, K, N) :- sum_iter(J, K, N, J, 0).   % clause_1

sum_iter(J, K, N, I, S) :-                 % clause_2
  Kn is K+1,                               % clause_X
  I = Kn,
  N = S,!.

sum_iter(J, K, N, I, S) :-     % clause_2, I - index, S - SumTmp
  I =< K,
  NewI is I+1,
  NewS is S+I,
  sum_iter(J, K, N, NewI, NewS).

Это работает правильно, но я не понимаю:

  • почему я должен использовать clause_X (почему +1)
  • и почему я не могу заменить clause_2 на

sum_iter(J, K, N, K, N) :- !.

В этом случае предикат прекращает работу на предыдущем шаге. Например, ожидайте: 

?- sum(1,3,What).
What = 6

НО вывод Prolog: 

?- sum(1,3,What).
What = 3

1 Ответ

1 голос
/ 07 марта 2020

Распечатка некоторых состояний: 

sum(J, K, N) :- sum_iter(J, K, N, J, 0).

% the rule at the end of the recursion

sum_iter(J, K, N, I, S) :-
  format("rule 1: J=~w K=~w N=~w I=~w S=~w\n", [J, K, N, I, S]),
  Kn is K+1,
  I = Kn,
  format("...pos 1 passed\n"),
  N = S,
  format("...pos 2 passed\n"),
  !.

% the rule perfoming the recursion

sum_iter(J, K, N, I, S) :-
  format("rule 2: J=~w K=~w N=~w I=~w S=~w\n", [J, K, N, I, S]),
  I =< K,
  format("...pos 3 passed\n"),
  NewI is I+1,
  NewS is S+I,
  sum_iter(J, K, N, NewI, NewS).

?- sum(1,3,What).
rule 1: J=1 K=3 N=_11338 I=1 S=0
rule 2: J=1 K=3 N=_11338 I=1 S=0
...pos 3 passed
rule 1: J=1 K=3 N=_11338 I=2 S=1
rule 2: J=1 K=3 N=_11338 I=2 S=1
...pos 3 passed
rule 1: J=1 K=3 N=_11338 I=3 S=3
rule 2: J=1 K=3 N=_11338 I=3 S=3
...pos 3 passed
rule 1: J=1 K=3 N=_11338 I=4 S=6
...pos 1 passed
...pos 2 passed
What = 6.

В конце I = Kn становится тестом: и I, и Kn устанавливаются в фактические значения, с I один «за концом».

Вы можете сделать это, используя I > K «охранник»: 

sum_iter(_, K, Res, I, Res) :- I > K,!.

Но что вы также хотите сделать:

  • Вызовите рекурсивное правило по умолчанию, если оно применимо.
  • Если это не так, вызовите "правило конца рекурсии".

Итак, перестановка лучше всего: 

sum(J, K, N) :- sum_iter(J, K, N, J, 0).


% the rule perfoming the recursion, with a guard "I =< K", which, once
% successful, commits the computation to this one rule, so we add "!"

sum_iter(J, K, N, I, S) :-
  format("rule 2: J=~w K=~w N=~w I=~w S=~w\n", [J, K, N, I, S]),
  I =< K,!, 
  format("...pos 3 passed\n"),
  NewI is I+1,
  NewS is S+I,
  sum_iter(J, K, N, NewI, NewS).

% the rule at the end of the recursion, also with guard:

sum_iter(J, K, Res, I, Res) :-
  format("end: J=~w K=~w I=~w Res=~w\n", [J, K, I, Res]),
  I > K,!.

На самом деле, нет необходимости в "сокращении" во втором правиле, потому что оно является последним правилом. В этом случае охранник также не нужен, это просто отрицание охранника в первом правиле. Но давайте оставим оба для ясности. 

?- sum(1,3,What).
rule 2: J=1 K=3 N=_15630 I=1 S=0
...pos 3 passed
rule 2: J=1 K=3 N=_15630 I=2 S=1
...pos 3 passed
rule 2: J=1 K=3 N=_15630 I=3 S=3
...pos 3 passed
rule 2: J=1 K=3 N=_15630 I=4 S=6
end: J=1 K=3 I=4 Res=6
What = 6.
...