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?
Here is a general methodology for debugging and testing Prolog predicates:
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:
By removing goals, we can generalize a program1. 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.