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

Question

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

Я думал, что проблема в том, что я должен «инициализировать» Сумма к 0 в первом «итерации», но это было бы очень процедурной и, к сожалению, Я не очень ухожу в прологе, чтобы сделать эту работу. Любые идеи или предложения?

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. Самый простой способ понять их, чтобы посмотреть на :- и понять, что это должно быть стрелком ← (таким образом, справа налево стрелки) означает:

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

---

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

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

Для нашего запроса, мы можем рассмотреть следующее инстанцирование замещающего 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

Я действительно не следуя вашей логике, то, что со всеми seemingle посторонними 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!