Finding Length of List in Prolog
list, prolog
Solution
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 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.
Problem
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?