Sum the atomic elements in a deep list in prolog

Question

I am beginner in Prolog programming. I wrote this program to sum the atomic of a deep list with accumulator.

    deep_sum(Xs, N) :- deep_sum(Xs, 0, N).
    deep_sum([], N, N).
    deep_sum([X|Y], M, N) :- atomic(X), Q is M + X, deep_sum(Y, Q, N).
    deep_sum([X|Y], M, N) :- M is P + Q, deep_sum(X, P, N), deep_sum(Y, Q, N).

Why do I get "ERROR: is/2: Arguments are not sufficiently instantiated"?

It works fine without accumulator:

    deep_sum([], 0).
    deep_sum([X|Y], S) :- atomic(X), !, deep_sum(Y, Q), S is Q + X.
    deep_sum([X|Y], S) :- deep_sum(X, P), deep_sum(Y, Q), S is P + Q.

Please add sample queries, in particular the one which showed that error. — repeat

Steven Steven · Accepted Answer · 2015-12-15T09:13:11

The problem is with your last clause:

deep_sum([X|Y], M, N) :-  M is P+Q, deep_sum(X,P,N), deep_sum(Y,Q,N).

The direct issue of the error is that neither P nor Q have a value when M is P+Q is executed. Just moving it to the back won't solve it though, the clause has more issues.

Let's take a look at the recursive calls. deep_sum(X,P,N) in words means "N is the deep sum of the head (X), given accumulator P". There are two issues here: P does not have a value, and N is supposed to be the total sum of the entire list, not just the head.

The same issues are there in the second recursive call. The accumulator Q does not have a value yet, and again N is used as the result. So now N has 3 meanings: deep sum of the head, deep sum of the tail, and deep sum of the entire list! Obviously something is not right there.

Let's try to put in words how the recursive rule should behave. The result N should be equal to the sum of a) the current accumulator, b) the deep sum of the head and c) the deep sum of the tail. a and b can be easily combined: simply pass in the current accumulator as the accumulator for the recursive call: deep_sum(X, M, N1). Here I use another variable N1 to hold this result. Now we just have to sum this with the deep sum of the tail. Again, we can simply pass N1 as accumulator for the recursive call, and everything will be accumulated as expected.

Putting everything together, your recursive rule should look like this:

deep_sum([X|Y], M, N) :- 
    deep_sum(X, M, N1), 
    deep_sum(Y, N1, N).

For completeness, my deep_sum/3 implementation would look something like this:

deep_sum(X, M, N) :- 
    number(X), 
    N is M + X.
deep_sum([], N, N).
deep_sum([X|Y], M, N) :- 
    deep_sum(X, M, N1), 
    deep_sum(Y, N1, N).

The main differences are:

Only one recursive clause; the clause where you handle numbers doesn't need to be recursive.
number/1 instead ofatomic/1, so you don't attempt to add strings or so.
Rearranged the order of the clauses to not leave any useless choice point once the calculation is done.

Sum the atomic elements in a deep list in prolog

1 Answers