Prolog List Amount

Question

I am reading the book “The Art of Prologue,” and I found an exercise that says: “Determine the sum of the relations (ListOfIntegers, Sum) that is executed if Sum is the sum of ListOfIntegers without using an auxiliary predicate.” I came up with this solution:

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

Which does not work exactly as we would like.

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

I expected X to be

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

I thought the problem was that I had to “initialize” Sum to 0 in the first “iteration”, but that would be very procedural, and, unfortunately, I'm not really leaving the prologue to do this job. Any ideas or suggestions?

Answer 1

The best way to localize the problem is to simplify your request first:

 ?- sum([0],S). true ?- sum([],S). true 

Even for those, you get an answer that any S will do. how

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

Since [] can only be handled by your fact, the error should be in this very fact. You stated:

 sum([], Sum). 

This means that the sum [] is just something. You probably meant 0.

Another error is hidden in the last rule ... After fixing the first error, we get

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

Here the last question is responsible. It reads:

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

Recursive rules are relatively difficult to read in Prolog. The easiest way to understand them is to look at :- and understand that it should be an arrow and a lar; (thus, arrow from right to left), which means:

provided that the goals on the right are true

---

, we conclude that is on the left side

Thus, compared to informal recording, arrows point in the opposite direction!

For our query, we can consider the following instance, substituting Xs with [] and X with 0.

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

So, this rule is now read from right to left: Provided that sum([0],s(Sum)) is true, ... However, we know that only sum([0],0) is fulfilled, but not the target. Therefore, this rule never applies! What you intended was rather the opposite:

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

Answer 2

Your first sentence should read

 sum([], 0). 

With this change, the empty return true disappears, and you have one problem: the third sentence cancels the summation logic. It should be

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

because the number of s/1 members in the left argument before sum/2 must be equal to the number of them in the correct argument.

Answer 3

I really don't stick with your logic, that with all the seemingly extraneous s(X) structures that float.

Wouldn't it be simpler and easier to do something like this?

First determine your decision in plain English, thus:

• The sum of the empty list is 0.
• The sum of the non-empty list is obtained by adding the list header to the sum of the tail of the list.

From this definition, the prologue follows directly:

 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!