Сумма списка в prolog

Question

Я читаю книгу "Искусство пролога" и нашел упражнение, которое гласит: "Определите отношение sum(ListOfIntegers,Sum), которое выполняется, если Sum является суммой ListOfIntegers, без использования какого-либо вспомогательного предиката".Я придумал это решение:

sum([],Sum).
sum([0|Xs], Sum):-sum(Xs, Sum).
sum([s(X)|Xs], Sum):-sum([X|Xs],s(Sum)).

Который работает не совсем так, как мне бы хотелось.

?- sum([s(s(0)),s(0),s(s(s(0)))],X).
true ;
false.

Я ожидал, что X будет

s(s(s(s(s(s(0))))))

Я думал, что проблема в том, что я должен "инициализировать" Sum равным 0 на первой "итерации", но это было бы очень процедурно, и, к сожалению, я не совсем разбираюсь в prolog, чтобы заставить это работать.Есть какие-нибудь идеи или предложения?

Answer 1

Лучший способ локализовать проблему - сначала упростить ваш запрос:

?- sum([0],S).

true
?- sum([],S).

true

Даже для них вы получаете в качестве ответа, что какой-нибудь S будем делать.Нравится

?- sum([],s(s(0))).
yes

С [] может быть обработан только вашим фактом, ошибка должна заключаться именно в этом факте.Вы заявили:

sum([], Sum).

Что означает, что сумма [] это просто что угодно.Вы, вероятно, имели в виду 0.

Еще одна ошибка скрывается в последнем правиле...После исправления первой ошибки мы получаем

?- sum([0],Sum).
Sum = 0
?- sum([s(0)],Sum).
no

Здесь последнее предложение является ответственным.В нем говорится:

sum([s(X)|Xs], Sum):-sum([X|Xs],s(Sum)).

Рекурсивные правила относительно сложно читать в Prolog.Самый простой способ понять их - это посмотреть на :- и поймите, что это должна быть стрелка ← (таким образом, стрелка справа налево), означающая:

при условии, что цели в правой части верны

---

мы делаем вывод о том, что находится с левой стороны

Итак, по сравнению с неформальным письмом стрелки указывают в противоположном направлении!

Для нашего запроса мы можем рассмотреть следующий пример, заменяющий Xs с [] и X с 0.

sum([s(0)| [] ], Sum) :- sum([0| []],s(Sum)).

Таким образом, это правило теперь читается справа налево:Представленный, sum([0],s(Sum)) это правда, ...Однако мы знаем, что только sum([0],0) держится, но не эта цель.Следовательно, это правило никогда не применяется!То, что вы намеревались, было скорее противоположным:

sum([s(X)|Xs], s(Sum)):-sum([X|Xs],Sum).

Answer 2

Ваш первый пункт должен гласить

sum([], 0).

С этим изменением бессмысленный true возвращение исчезает, и вы остаетесь с одной проблемой:третье предложение меняет логику суммирования на противоположную.Это должно быть

sum([s(X)|Xs], s(Sum)) :- sum([X|Xs], Sum).

потому что количество s/1 термины в левом аргументе для sum/2 должно быть равно их количеству в правильном аргументе.

Answer 3

Я на самом деле не следоваю за вашей логикой, что со всеми кажущимися посторонними структурами генеракодицетагкод плавающих о.

не было бы проще и проще сделать что-то подобное?

Сначала определите ваше решение на простом английском, таким образом:

.
• сумма пустого списка 0.
• сумма непустого списка получается путем добавления головки списка в сумму хвоста списка.

Из этого определения пролог следует напрямую:

sum( []     , 0 ) .  % the sum of an empty list is 0.
sum( [X|Xs] , T ) :- % the sum of an non-empty list is obtained by:
  sum( Xs , T1 ) ,   % - first computing the sum of the tail
  T is X + T1        % - and then, adding that the to head of the list
  .                  % Easy!

.