List Length in Prolog

Question

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).

Aenea

Answer 1

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.

Liking

Answer 2

this code

length_1(0,[]).
length_1(L+1, [H|T]) :- length_1(L,T).

works (please note the added square braces), but in unexpected way. It will build an expression tree, that could be evaluated later:

?- length_1(X, [1,2,3]), L is X.
X = 0+1+1+1,
L = 3.

In your rewritten code (second version), you get an error because N1 is not yet instantiated at the time you call is/2.

Borsch

Answer 3

len([], LenResult):-
    LenResult is 0.

len([X|Y], LenResult):-
    len(Y, L),
    LenResult is L + 1.

Inning

Although this code may answer the question, providing additional context regarding why and/or how it answers the question would significantly improve its long-term value. Please edit your answer to add some explanation. – Dejesus

Answer 4

As hinted in Carlo's answer, L+1 is a Prolog term with two arguments, L and 1, whose functor is +. Prolog is not a functional language, so you can not type L+1 and expect it to be evaluated to the sum. Try to follow Carlo's suggestion and use the is/2 predicate to force arithmetic evaluation. For example, calling the goal X is 3 + 4 will evaluate the right operand and attempt to unify the result with the left operand. If the left operand, X, is a variable, it will be unified with 7. Also note that, in Prolog, variables are single assignment (but can be further instantiated if the assigned term includes variables, however). I.e. you can only assign a term to a variable once. This assignment is undone when you backtrack over the goal doing the assignment.

Grandson

Answer 5

The other answers point out relevant issues, but I think the problem is simply an uninstantiated variable. In the last example

length([], 0).
length([H|T], N) :- N is N1+1, length(T, N1).

Although we can have variables on the right hand side of is, they must have been instantiated to an integer so that Prolog can carry out the arithmetic operation. In the example above, N1 is not instantiated yet, and Prolog cannot apply the is functor. The type of error is not mentioned in the question, but it should be an instantiation_error or "Arguments are not sufficiently instantiated" (if in SWI-Prolog).

When you invert the goals in the second rule

length([], 0).
length([H|T], N) :- length(T, N1), N is N1+1.

N1 is already instantiated to an integer by the time is gets called, and the program completes without errors.

See also this other thread.

Hbeam

Answer 6

Find list length in Prolog:

list_member(X,[X|_]).

list_member(X,[_|TAIL]) :- list_member(X,TAIL).

Phew

You've posted a solution for member rather than length. A better member is at swi-prolog.org/pldoc/doc/_SWI_/library/lists.pl?show=src#member/… – Desdemona