Сумма списка в прологе - PullRequest
Новая
       18

Сумма списка в прологе

4 голосов
/ 14 марта 2012

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

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 в первой «итерации», но это было бы очень процедурно, и, к сожалению, я не совсем склонен к прологу, чтобы сделать эту работу.Есть идеи или предложения?

Ответы [ 3 ]

4 голосов
/ 14 марта 2012

Ваше первое предложение должно читаться как 

sum([], 0).

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

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

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

3 голосов
/ 14 марта 2012

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

?- 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)).

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

при условии, что цели справа -правая сторона
мы заключаем, что находится с левой стороны

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

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

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

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

sum([s(X)|Xs], s(Sum)):-sum([X|Xs],Sum).
0 голосов
/ 16 марта 2012

Я на самом деле не следую вашей логике, что со всеми кажущимися посторонними s(X) структурами.

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

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

  • Сумма пустого списка равна 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!
...