Prolog - How to get the sum of a list's elements?

Question

I'm very new to prolog and I am trying to write a little program that, given a list, returns the sum of the list's elements. Following all the examples I've seen led me to a solution that looks like this:

addup([],0).
addup([FirstNumber | RestOfList], Total) :-
    addup(RestOfList, TotalOfRest),
    Total is FirstNumber + TotalOfRest.

But when I test that solution with these values:

?- addup([1,2,3,4],0).

I just get garbage values from it like _34521.

Then I tried a second solution that looks like this:

sum([], 0).
sum([H|T], N):-
    X is H+N,
    sum(T, X).

This one is able to add up the numbers correctly, but it is unable to pass the final value of X, which is the true answer, into N. So for the test case:

?- sum([1,2,3,4], 0).

I get an answer of 6, the final value of N, and the second-to-last value of X, instead of 10, the final value of X. Any help and/or explanations of why neither of these solutions work would be greatly appreciated. Thanks.

Answer 1

Firstly, the sum of an empty list is 0 - this is the base case, which you already had.

Secondly, the sum N of an element H and a list T is the sum of the list T added to H. Prolog operates on unification, so this says that N is unified with the sum of H and T, where the sum of T is unified with X using sum(T,X).

sum([], 0).
sum([H|T], N):-
    sum(T, X),
    N is X + H.

This gives:

?- sum([1,2,3,4],N).
N = 10.

In your original question, ?- sum([1,2,3,4], 0). actually says "this is true if the sum of the list [1,2,3,4] is 0" - you need to pass a variable as the second argument to sum to be unified with the answer.

Further information:

_34521 is a representation of an unbound variable - this says that there is a variable, but that it has not yet been unified with a value.

Secondary consideration:

For a suitably long list, the implementation above will run out of stack space, as each frame of the recursion must be stored, so that the addition can happen from the bottom up. In order to prevent a stack error, we can use a tail-recursive accumulator like so:

sum(L, N):-
    sum(L, 0, N).

sum([],N,N).
sum([H|T],A,N) :-
    A1 is A + H,
    sum(T,A1,N).

... which retains the signature of the original method, wrapping sum/3. As there is no choice-point in the body of the rule (given that A + H is always the same for a given A and H, and the list is either empty or not), Prolog will discard each frame as it leaves scope (as there is nothing more to be done with it) and, on completion, will return to the original caller.

Simplified stack for sum([1,2,3],N) in each instance:

non-tail-recursive:

rest-of-stack
rest-of-stack,sum([1|[2,3]],_1001)
rest-of-stack,sum([1|[2,3]],_1001),sum([2|[3]],_1002)
rest-of-stack,sum([1|[2,3]],_1001),sum([2|[3]],_1002),sum([3|[]],_1003)
rest-of-stack,sum([1|[2,3]],_1001),sum([2|[3]],_1002),sum([3|[]],_1003),sum([],0)
rest-of-stack,sum([1|[2,3]],_1001),sum([2|[3]],_1002),sum([3|[]],3)
rest-of-stack,sum([1|[2,3]],_1001),sum([2|[3]],5)
rest-of-stack,sum([1|[2,3]],6)
rest-of-stack

tail-recursive:

rest-of-stack
rest-of-stack,sum([1,2,3],_1001)
rest-of-stack,sum([1|[2,3]],0,_1001)
rest-of-stack,sum([2|[3]],1,_1001)
rest-of-stack,sum([3|[]],3,_1001)
rest-of-stack,sum([],6,6)
rest-of-stack

Note that the tail-recursive stack has a limited depth for any length of list (dependent on what is calling it), where the non-tail-recursive stack goes to a depth directly proportional to the length of the list.

Thus, a call such as N is 10^7,length(L,N),maplist(=(1),L),sum(L,N). (as raised by @false) will likely fail without tail-recursion, and likely succeed with it.