Search code examples
prolog

Difference between variables used to count items in a prolog list


I don't understand why this block performs the count:

lengthTest([],0).
lengthTest([_ | X], R) :- lengthTest(X, R1), 
    R is R1 + 1.

and the following no, it returns only false.

lengthTest([],0).
lengthTest([_ | X], R) :- lengthTest(X, R), 
    R is R + 1.

Can anyone explain what happens under the hood? i'm using swi-prolog

Thanks


Solution

  • First of all, what values are candidates for R in the second rule of your second version?

    There is a single candidate only: R = 0 which comes from the fact. OK, why not. Let's now read the recursive rule with that knowledge:

    lengthTest([_ | X], 0/*R*/) :-  lengthTest(X, 0/*R*/), 
        0/*R*/ is 0/*R*/ + 1.
    

    Reading that rule from right-to-left in the direction of the arrow :- (that's an asciified ←):

    lengthTest(X, 0/*R*/): Provided X is a list with length 0 (why not) and 0/*R*/ is 0/*R*/ + 1 is true (let's ignore that for a moment)

    then it follows that

    the list with one more element has length 0.

    In other words, all lists have length 0. Does this make sense to you? Maybe (I'm kidding).

    But regardless of this odd conclusion, what about 0/*R*/ is 0/*R*/ + 1 which I ignored for the moment?

    ?- 0/*R*/ is 0/*R*/ + 1.
       false.
    

    So this never holds and thus the conclusion can never be drawn.

    BTW, you claimed that this definition »returns only false« which is not true, for it succeeds as follows:

    ?- lengthTest([], 0).
       true.