Is there anybody to explain how does this code actually work?(PROLOG)

Question

So, the story began with counting the number of elements inside a list.

Then, I encountered this code when I searched for the solutions in Internet.

count([],0).                 
count([_HEAD|TAIL],X) :-          
   count(TAIL,X1),
   X is X1+1.

However, there was no clear explanation on how the code actually worked and that is why I ask here in order to get a clear explanation about this code.

Hope that someone can explain step by step so that I can understand better.

Answer 1

Please think declaratively. You are relating a list to its length, so a better, relational name would be list_length/2: The first argument is a list, the second its length.

Obviously, the length of the empty list [] is 0.

Further, if Tail is a list of length L0, then the length of [_|Tail] is the number L0 + 1.

Answer 2

count([] ,0) means that an empty list has 0 element. Now, to count the elements of a list

count([_HEAD|TAIL],X):-       
    % we remove the first element of the list
    % we count the elements of the rest of the list
    count(TAIL,X1),
    % and we add 1 to the number of the elements of the rest
    X is X1+1.

Answer 3

Learning to think recursively is hard. Most recursive problems can be broken down into a few "special cases" and the general case. In this case, we have two cases:

• the empty list. This is our special case. The length of the empty list is ALWAYS zero.

• A non-empty list. This is our general case.We have the list's head (a single item) and its tail (the remainder of the list: zero or more items). So, we can say that the length of a non-empty list is the length of its tail, plus 1 (the head).

Prolog lets you simply declare these to be facts defining truth. Then we let the Prolog inference engine determine the truth or falsity of an assertion. To whit:

count( []     , 0 ) .  % The count of an empty list is zero
count( [_|Xs] , N ) :- % If the list is non-empty, 
  count( Xs, T ) ,     % - we count its tail as T
  N is T+1             % - and then add 1.
  .                    %

Then... you can say things like:

?- count([],3).
false.

?- count([a,b,c],3).
true.

This also works in a generative manner:

?- count( List , 3 ) .
List = [_G938, _G941, _G944] .

Or even...

?- count(X,N).
X = [], N = 0 ;
X = [_G950], N = 1 ;
X = [_G950, _G953], N = 2 ;
X = [_G950, _G953, _G956], N = 3 ;
...

Note that this is not tail-recursive and feed a list of sufficient length, will eventually overflow its stack.

You can write it in a tail-recursive manner as well, which might be easier to understand:

count( Xs , N ) :-    % to count the number of items in a list,
  count( Xs , 0 , N ) % - invoke the helper, seeding the accumulator with 0.
  .                   %

count( []     , N , N ) .  % if the source list is empty, the accumulator contains the number of items in the list.
count( [_|Xs] , T , N ) :- % otherwise (source list is non-empty)
  T1 is T+1 ,              % - increment the accumulator, and
  count(Xs,T1,N)           % - recurse down on the tail, passing the incremented accumulator
  .                        %