Пролог, треугольные числа, аккумуляторы и хвостовая рекурсия

Question

Я работаю над домашним заданием, состоящим из 2 частей. Во-первых, написать программу Prolog, которая проверяет, принадлежит ли определенная пара X, Y к http://en.wikipedia.org/wiki/Triangular_number. Например: (2, 3) = правда; (4, 10) = правда и так далее.

Первое решение использует "обычную" рекурсию, и я решил это так:

triangle(0, 0).
triangle(X, Y) :- X > 0, Y > 0, A is X - 1, B is Y - X, triangle(A, B).

Вторая часть заключается в том, чтобы решить эту проблему с помощью хвостовой рекурсии / аккумулятора, используя предикат треугольник /3. Хотя я использовал аккумулятор в другом наборе, в котором его использование было совершенно очевидным, поэтому у меня есть общее представление о том, как использовать аккумулятор, я весьма озадачен тем, как его использовать в этом контексте.

Итак, я не ищу алгоритм, я бы скорее решил его сам, но больше практических советов о том, как применить аккумулятор в этом контексте.

Answer 1

Начало всегда одинаковое, то есть первые три строки - это то, что вы пишете для каждого хвостового рекурсивного предиката (с [] вместо 0 для предикатов списка).

Оттуда вы можете продолжать без особых изменений:

 triangle_t(X, Y) :- triangle_t(X, 0, Y).
 triangle_t(0, Y, Y).
 triangle_t(X, Acc, Y) :-
          X > 0,
          A is X - 1,
          AccX is Acc + X,
          triangle_t(A, AccX, Y).

Вот немного статистики для большого X:

64 ?- time(triangle(1000000,500000500000)).
% 4,000,000 inferences, 0.50 CPU in 0.52 seconds (96% CPU, 8012769 Lips)
true.

65 ?- time(triangle_t(1000000,500000500000)).
% 3,000,001 inferences, 0.41 CPU in 0.44 seconds (92% CPU, 7396405 Lips)
true.

Таким образом, в то время как ваш собственный предикат в основном уже хвостовой рекурсии (потому что рекурсивный вызов - последнее, что нужно сделать), версия с аккумулятором все еще экономит некоторое время, потому что вам не нужна проверка на Y > 0, Если вы введете эту строку в triangle_t предикат, они снова имеют точно такие же характеристики времени выполнения:

67 ?- time(triangle_t(1000000,500000500000)).
% 4,000,001 inferences, 0.53 CPU in 0.53 seconds (100% CPU, 7541432 Lips)
true.

Также обратите внимание, что теперь вы можете использовать предикат для генерации n-го треугольного числа.