Clever Geek Handbook

Get length of list in prolog in non-recursive way

I have the following code to get the length of a list in a prologue, it works recursively. Is there any other way to get the length?

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

Any suggestions would be appreciated.

+3


source to share


3 answers


Here's an iterative solution that uses a predicate repeat/0

:

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 removes facts getlength_res/1

and getlength_list/1

, as it scans through the list, replacing the old list with the shorter one and the old number with the number that is larger in each iteration repeat/0

. In a sense, two dynamically asserted / retracted facts behave very much like assignable variables of imperative languages.



Demo version

In general, iterative solutions in Prolog are harder to read than their recursive counterparts. This shouldn't come as a surprise, given that anything that influences the assignment wording of an imperative programming language runs counter to Prolog's design philosophy.

+2


source


You are asking the wrong question :)

But seriously: the only sane way to find the length of a list is to use the inline length/2

. How this is implemented does not matter - its semantics are more important:

?- 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

In any case, this is not simplified. Any other way of finding the length of a list, or checking the length of a list, or creating a list of a specific length, or enumerating lists of increasing length would be less "easy" than using length/2

.

And then: learning in Prolog means learning length/2

, as well as other beautifully declarative builtins.



Repeating an element N times

Splitting a list into segments of some length

Exactly one pair on the list

Rotate list

I'm sure you can think of many other uses length/2

.

+4


source


Sorry, I could not resist this "task":

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 performs recursion behind the scenes, the code unifies the FreeList and Input until they unify

0


source






More articles:


All Articles