I am beginner in Prolog programming. I wrote this program to calculate the length of a list. Why is below program wrong?
length(0, []).
length(L+l, H|T) :- length(L, T).
I wrote below program and it works correctly.
length([], 0).
length([H|T], N) :- length(T, N1), N is N1+1.
when I changed the order, I got an error. Why?
length([], 0).
length([H|T], N) :- N is N1+1, length(T, N1).
Answer
You need to use an accumulator. While you could do something like this:
list_length([] , 0 ).
list_length([_|Xs] , L ) :- list_length(Xs,N) , L is N+1 .
which will recurse all the way down to the end of the list and then, as each invocation returns, add one to the length, until it gets back to the top level with the correct result.
The problem with this approach is that each recursion pushes a new stack frame on the stack. That means you will [eventually] run out of stack space given a long enough list.
Instead, use a tail-recursive intermediary, like this:
list_length(Xs,L) :- list_length(Xs,0,L) .
list_length( [] , L , L ) .
list_length( [_|Xs] , T , L ) :-
T1 is T+1 ,
list_length(Xs,T1,L)
.
This code seeds a worker predicate that carries an accumulator, seeded with 0. On each recursion it creates a new accumulator whose value is the current value + 1. When the end of the list is reached, the value of the accumulator is unified with the desired result.
The prolog engine is smart enough (TRO/Tail Recursion Optimization) to see that it can reuse the stack frame on each call (since none of the locals are used after the recursive call), thus neatly converting the recursion into iteration.