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

Я читаю книгу «Искусство пролога» и нашел упражнение, которое гласит: «Определите сумму отношения (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 successor-arithmetics
person kaiseroskilo    schedule 14.03.2012    source источник

Ответы (3)


arrow_upward
3
arrow_downward

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

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

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

provided, that the goals on the right-hand side are true
we conclude what is found on the left-hand side

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

Для нашего запроса мы можем рассмотреть следующий экземпляр, заменяющий 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).
person false    schedule 14.03.2012
comment
Никогда не думал, что так смогу решить свою проблему ... Спасибо! - person kaiseroskilo; 14.03.2012
comment
Это не первый вопрос Пролога, который был вдохновлен другим языком. Я полагаю, что в последнее время Erlang избаловал программистов на Prolog, или он отражает определенное мышление правил. В Erlang можно было обойтись без Пеано: sum ([]) - ›0; сумма ([X | Y]) - ›X + сумма (Y). И декларативное чтение слева направо размыто, а '- ›' логически перепутано. - person Mostowski Collapse; 15.03.2012
comment
В Прологе II действительно был -> вместо :-, это было примерно в 1980 году. Намерение состояло в том, чтобы подчеркнуть аспект перезаписи. Эрлангу около 1987 года. - person false; 15.03.2012

arrow_upward
4
arrow_downward

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

sum([], 0).

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

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

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

person Fred Foo    schedule 14.03.2012
comment
Отлично! Спасибо за помощь! - person kaiseroskilo; 14.03.2012

arrow_upward
0
arrow_downward

Я не совсем слежу за вашей логикой, со всеми кажущимися посторонними 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!
person Nicholas Carey    schedule 15.03.2012
comment
OP изучает Пролог с Искусство Пролога, по-прежнему отличный выбор. И там вначале используются s (X) -натуральные числа. - person false; 16.03.2012