CODEWITHSUNDEEP
prolog
user4406062
user4406062

Reputation:

Get the length of a list in prolog in a non-recursive way

I have the following code for getting the length of a list in prolog, it works recursively. Is there any other way for getting the length?

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

Any suggestions would be appreciated.

Upvotes: 3

Views: 1054

Answers (3)

re Paul
re Paul

Reputation: 122

Sorry I could not resist to try out this "challenge":

Input=[a,b,b,b,b,b,b,b,b,a,b,c,d,f], between(1,inf,K),findall( _,between(1,K,_),FreeList), ( FreeList=Input,!,true).

findall/3 is doing the behind-the-scenes recursion, code is making unifications of lists FreeList and Input until they unify

Upvotes: 0

user1812457
user1812457

Reputation:

You are asking the wrong question :)

But seriously: the only sensible way of finding the length of a list is to use the built-in length/2. How it is implemented is irrelevant -- more important are its semantics:

?- length([a,b], 2).
true.

?- length([a,b], 4).
false.

?- length([a,b,c], Len).
Len = 3.

?- length(List, 3).
List = [_G937, _G940, _G943].

?- length(List, Len).
List = [],
Len = 0 ;
List = [_G949],
Len = 1 ;
List = [_G949, _G952],
Len = 2 . % and so on

Either way, it doesn't get simpler than that. Any other way of finding the length of a list, or checking for the length of a list, or creating a list of a certain length, or enumerating lists of increasing length is going to be less "simple" than using length/2.

And then: learning Prolog means learning how length/2, and the other nicely declarative built-ins can be used.

Repeating an element N times

Splitting a list into segments of some length

Exactly one pair in a list

Rotate a list

I am sure you can think of many other uses of length/2.

Upvotes: 4

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726479

Here is an iterative solution that uses repeat/0 predicate:

getlength(L,N) :-
    retractall(getlength_res(_)),
    assert(getlength_res(0)),
    retractall(getlength_list(_)),
    assert(getlength_list(L)),
    repeat,
        (
            getlength_list([]), !, getlength_res(N)
        ;
            retract(getlength_res(V)), W is V + 1, assert(getlength_res(W)),
            retract(getlength_list([_|T])), assert(getlength_list(T)), fail
        ).

This solution creates and retracts facts getlength_res/1 and getlength_list/1 as it walks through the list, replacing the old list with a shorter one, and the old number with a number that is greater by one at each iteration of repeat/0. In a sense, the two dynamically asserted/retracted facts behave very much like assignable variables of imperative languages.

Demo.

In general, iterative solutions in Prolog are harder to read than their recursive counterparts. This should come as no surprise, considering that anything that has an effect of an assignment statement of an imperative programming language goes against the grain with Prolog's design philosophy.

Upvotes: 2

Related Questions