Более глубокое объяснение графа пролога

Question

В настоящее время играю в Прологе ... У меня проблемы с поиском правила списка подсчета.Я нигде не смог найти хорошего объяснения.Может ли кто-нибудь дать мне разбить его на каждую рекурсию?

count(0, []).
count(Count, [Head|Tail]) :-
    count(TailCount, Tail),
    Count is TailCount + 1.

Одно место говорит, что оно рекурсивное (что имеет смысл для меня), а другое - что это не так.

Answer 1

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

count(C, L) :- count(0, C, L).

count(Total, Total, []).
count(SoFar, Count, [_Head|Tail]) :-
    Count1 is SoFar + 1,
    count(Count1, Count, Tail).

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

    ...,
    !, count(Count1, Count, Tail).

Answer 2

Определение правила вывода является рекурсивным. Эта программа пытается подсчитать количество элементов в списке.

count(0, []). Это аксиома, факт, правда, потому что ты так сказал. Здесь вы заявляете, что каждый пустой список имеет счетчик нуля.

count(Count, [Head|Tail]) :- count(TailCount, Tail), Count is TailCount + 1.

Это правило вывода, которое определяет, что левая часть :- истинна, если правая часть истинна. В этом правиле вывода также используется сопоставление с образцом, при этом совпадения совпадают с непустыми списками ([Head|Tail]). В частности, правило подсчета гласит, что переменная Count непустого списка является счетчиком части списка Tail, плюс 1 (плюс 1 - для подсчета элемента Head списка).