What the the variables in following program stores

Question

total_item([],0).
total_item([_|Rest],N) :- total_item(Rest,C), N is C+1.

This program takes an array as input and count the total number of item in that list. But I am not getting what exactly variable N and C stores. Any explanation would be appreciate. Thank you

Answer 1

Read it backwards:

total_item([], 0).

total_item maps 0 to [] (relates the two).

total_item([_ | Rest], N) :- 
    total_item( Rest,       C    ), 
                       N is C + 1 .

with C mapped to Rest, C+1 is mapped to [_ | Rest] -- the list one element longer than the list Rest.

See this with the most general query working in the generative fashion:

2 ?- total_item(L, C).
L = [],
C = 0 ;
L = [_G1464],
C = 1 ;
L = [_G1464, _G1467],
C = 2 ;
L = [_G1464, _G1467, _G1470],
C = 3 ;
L = [_G1464, _G1467, _G1470, _G1473],
C = 4 .

Answer 2

Will Ness answer should have provided you with a clear understanding of that predicate definition. But there's more that you can learn from it. Let's do a trace of a simple call. Here I'm using GNU Prolog but most Prolog system provide the same trace functionality:

| ?- trace.
The debugger will first creep -- showing everything (trace)

yes
{trace}
| ?- total_item([1,2,3], N).
      1    1  Call: total_item([1,2,3],_285) ? 
      2    2  Call: total_item([2,3],_354) ? 
      3    3  Call: total_item([3],_378) ? 
      4    4  Call: total_item([],_402) ? 
      4    4  Exit: total_item([],0) ? 
      5    4  Call: _430 is 0+1 ? 
      5    4  Exit: 1 is 0+1 ? 
      3    3  Exit: total_item([3],1) ? 
      6    3  Call: _459 is 1+1 ? 
      6    3  Exit: 2 is 1+1 ? 
      2    2  Exit: total_item([2,3],2) ? 
      7    2  Call: _285 is 2+1 ? 
      7    2  Exit: 3 is 2+1 ? 
      1    1  Exit: total_item([1,2,3],3) ? 

N = 3

(1 ms) yes

You can see in the first four lines that the predicate results in walking the list until the end and only then we compute the pending N is C + 1 goals. Each element in the list results in one pending arithmetic evaluation goal. These pending goals must be stored in a stack until the recursive call to the total_item /2 predicate terminates. As a consequence, computing the length of a list of size N requires space (for the stack) proportional to N. I.e. this predicate definition is not tail-recursive.

But we can rewrite the predicate, making it tail-recursive to improve its space complexity by using an accumulator. An accumulator is an argument that stores intermediate results, in this case, the count so far of the number of elements in the list:

total_item(List, Total) :-
    total_item(List, 0, Total).

total_item([], Total, Total).
total_item([_| Rest], Total0, Total) :-
    Total1 is Total0 + 1,
    total_item(Rest, Total1, Total).

Let's trace the same goal:

| ?- total_item([1,2,3], N).
      1    1  Call: total_item([1,2,3],_285) ? 
      2    2  Call: total_item([1,2,3],0,_285) ? 
      3    3  Call: _382 is 0+1 ? 
      3    3  Exit: 1 is 0+1 ? 
      4    3  Call: total_item([2,3],1,_285) ? 
      5    4  Call: _435 is 1+1 ? 
      5    4  Exit: 2 is 1+1 ? 
      6    4  Call: total_item([3],2,_285) ? 
      7    5  Call: _488 is 2+1 ? 
      7    5  Exit: 3 is 2+1 ? 
      8    5  Call: total_item([],3,_285) ? 
      8    5  Exit: total_item([],3,3) ? 
      6    4  Exit: total_item([3],2,3) ? 
      4    3  Exit: total_item([2,3],1,3) ? 
      2    2  Exit: total_item([1,2,3],0,3) ? 
      1    1  Exit: total_item([1,2,3],3) ? 

N = 3

(1 ms) yes

Notice that how the accumulator, the second argument in the auxiliary total_item/3 predicate is incremented as we walk thew list. With this definition, there are no pending goals, which means the space complexity is O(1) instead of O(N). Much better.