Finding Length of List in Prolog

Question

I'm running Prolog and trying to write a small function returning the length of a list:

len([],0).
len([XS], Y) :-
    len([X|XS], M),
    Y is M+1.

My logic is that the recursive call should include the tail of the list (XS) and increase 1 to the previous length (Y is M+1.)

This always returns false.

Any thoughts?

Answer 1

Here is a general methodology for debugging and testing Prolog predicates:

Start with the most general query!

Think of it: In Prolog you do not need to make up some test data. You don't even need to understand a predicate at all: Just hand in free variables! That is always a professional move!

So in your case, that's

?- len(L,N).
L = [],
N = 0 ;
*LOOPS**

Your definition is not that bad as you claim: At least, it is true for the empty list.

Now, maybe look at the compiler warnings you probably received:

Warning: user://1:11:
        Singleton variables: [X]

Next read the recursive rule in the direction of the arrow :- that is, right-to-left:

Provided len([X|Xs], M) is true and Y is M+1 is true, provided all that is true, we can conclude that

len([XS], Y) is true as well. So you are always concluding something about a list of length 1 ([Xs]).

You need to reformulate this to len([X|Xs], M) :- len(Xs, N), Y is M+1.

And here is another strategy:

Generalize your program

By removing goals, we can generalize a program¹. Here is my favorite way to do it. By adding a predicate (*)/1 like so:

:- op(950,fy, *).

*_.

Now, let's remove all goals from your program:

len([],0).
len([XS], Y) :-
    * len([X|XS], M),
    * Y is M+1.

What we have now is a generalization. Once again, we will look at the answers of the most general query:

?- len(L, N).
L = [],
N = 0 ;
L = [_].

What? len/2 is only true for lists of length 0 and 1. That means, even len([1,2], N) fails! So now we know for sure: something in the visible remaining part of the program has to be fixed. In fact, [XS] just describes lists of length 1. So this has to be removed...

---

Fine print:

_{1 Certain restrictions apply. Essentially, your program has to be a pure, monotonic program.}