Prolog - list length

Author

list length

Algernon

2004-07-05, 8:56 am

I've been fooling around with writing a tutorial (mainly to improve my
skills) and I've used an example from Art of Prolog for finding the length
of a list namely:

length(List,N) :- nonvar(List), length1(List,N).
length(List,N) :- var(List), nonvar(N), length2(List,N).

length1([_|Ls],N) :-
length1(Ls,N1),
N is N1 + 1.
length1([],0).

length2([_|Ls],N) :-
N > 0,
N1 is N - 1,
length2(Ls,N1).
length2([],0).

using the meta-language predicates var/1 and nonvar/1 we are able to
determine the length of a list is N given the list or generate a list of
length N given N. As I was fooling with this example, I starting thinking of
accumulators so I came up with this:

list_length(List,N) :- list_length(List,0,N).

list_length([],N,N).
list_length([_L|Ls],N0,N) :-
N1 is N0 + 1,
list_length(Ls,N1,N).

I've tested this and found equivalent solutions for both versions of length
as well as the built-in length/2. My question is, have I missed something or
is it better to use list_length/2?

thanks

John Cullen

2004-07-06, 8:57 am

vannoord@let.rug.nl wrote in message news:<ccbbk7$i7f$1@info.service.rug.nl>...
> Algernon <algernon@dmv.com> wrote:
>
>
>
>
> Have you tried:
>
> ?- list_length(List,6), fail.

How about :

list_length(List,N) :- list_length(List,0,N).

list_length([],N,N) :- !.
list_length([_L|Ls],N0,N) :-
N1 is N0 + 1,
list_length(Ls,N1,N).

or

list_length(List,N) :- list_length(List,0,N).

list_length([],N,N).
list_length([_L|Ls],N0,N) :-
N1 is N0 + 1,
list_length(Ls,N1,N), !.

??

John

vannoord@let.rug.nl

2004-07-06, 8:57 am

John Cullen <eturtle@address.com> wrote:
> vannoord@let.rug.nl wrote in message news:<ccbbk7$i7f$1@info.service.rug.nl>...
[color=darkred]
> How about :

> list_length(List,N) :- list_length(List,0,N).

> list_length([],N,N) :- !.
> list_length([_L|Ls],N0,N) :-
> N1 is N0 + 1,
> list_length(Ls,N1,N).

> or

> list_length(List,N) :- list_length(List,0,N).

> list_length([],N,N).
> list_length([_L|Ls],N0,N) :-
> N1 is N0 + 1,
> list_length(Ls,N1,N), !.

versions with ! are not equivalent to the built-in version (at least in
Sicstus), since in the built-in version you can use the predicate in -,-
mode and get all solutions:

| ?- length(A,B).
A = [],
B = 0 ? ;
A = [_A],
B = 1 ? ;
A = [_A,_B],
B = 2 ? ;
A = [_A,_B,_C],
B = 3 ?

Apart from that, the built-in version is more robust in cases such as:

?- length(A,-3).
no

Gj

--
Gertjan van Noord Alfa-informatica, RUG, Postbus 716, 9700 AS Groningen
vannoord at let dot rug dot nl http://www.let.rug.nl/~vannoord

Algernon

2004-07-06, 4:09 pm

Yeah, that was my next question(s), when I put a cut in the first clause of
list_length/3 I can safely backtrack into the predicate however I can no
longer enumerate lists of varying sizes by list_length(X,Y). So what is the
better version? (assuming there is no e
quivalent built-in) the version with var and nonvar even though its rather
ugly and relies on meta predicates and can build a large tree because it's
not left recursive. And what about cuts, should they be avoided at all costs
or are the acceptable times for their use? And my final question. Are the
built-in operations done in unit time? That is, if I call the built-in
length on a list of size 4 does it require four reductions?

bart demoen

2004-07-06, 8:59 pm

Algernon wrote:
> [...]
> And my final question. Are the
> built-in operations done in unit time? That is, if I call the built-in
> length on a list of size 4 does it require four reductions?

I am going for the final question only ...

You are basically asking whether the length of a list can be determined
in constant time (that's how I interprete your "unit time"), or whether
it is linear in the length of the list.

One could imagine that together the length of a list is available like
the length of a vector in Java, so that it is accessible in constant
time. Let's do a Gedankenexperiment :-)

Construct an open ended list like

Xa = [a|Xb], Xb = [b|Xc], Xc = [c|Z]

Each of the Xa ... Xc must have also its length - which is not yet known
because the list is open ended.
Now unify Z with [] and suddenly the lengths of Xa ... Xc are known to
be 3, 2 and 1

Does that give an indication on whether it is reasonable that each list
has its length available at O(1) cost ?

You can do a real experiment to find out that list_length (of a closed
list) is linear in its length - try it and report on it here !

Cheers

Bart Demoen

vannoord@let.rug.nl

2004-07-06, 8:59 pm

Algernon <algernon@dmv.com> wrote:
> Yeah, that was my next question(s), when I put a cut in the first clause of
> list_length/3 I can safely backtrack into the predicate however I can no
> longer enumerate lists of varying sizes by list_length(X,Y). So what is the
> better version? (assuming there is no e
> quivalent built-in) the version with var and nonvar even though its rather
> ugly and relies on meta predicates and can build a large tree because it's
> not left recursive.

well, of course, we like our predicates to be nice and beautiful, but
it really all starts with functionality. If the functionality is the
same then we prefer the beautiful one. But if the beautiful one cannot
do the same task, then what is the point?

> And what about cuts, should they be avoided at all costs
> or are the acceptable times for their use?

there are certain things that you cannot do without cuts. But there
are some difficult aspects about cuts, so that you'd not use them
if you can. Furthermore, there's a fairly large class of situations
in which you can't use "pure" code, but where if-then-else suffices.
In those case, I prefer if-then-else over cut.

> And my final question. Are the
> built-in operations done in unit time?

If only that were true, then I'd ask my Prolog provider to supply much
more built-in predicates... Perhaps he could port my whole project...

> That is, if I call the built-in
> length on a list of size 4 does it require four reductions?

Bart has answered that...

Gj

--
Gertjan van Noord Alfa-informatica, RUG, Postbus 716, 9700 AS Groningen
vannoord at let dot rug dot nl http://www.let.rug.nl/~vannoord

John Cullen

2004-07-07, 8:58 am

vannoord@let.rug.nl wrote in message news:<cce36u$8nt$1@info.service.rug.nl>...
>[...]
>
>versions with ! are not equivalent to the built-in version (at least
in
>Sicstus), since in the built-in version you can use the predicate in
-,-
>mode and get all solutions:
>
>| ?- length(A,B).
>A = [],
>B = 0 ? ;
>A = [_A],
>B = 1 ? ;
>A = [_A,_B],
>B = 2 ? ;
>A = [_A,_B,_C],
>B = 3 ?
>
>
>Apart from that, the built-in version is more robust in cases such
as:
>
>?- length(A,-3).
>no

In that case the original could be modified (although it starts
looking a little messy) as follows:

list_length(List,N) :-
list_length(List,0,N).

list_length([],N,N).
list_length([_L|Ls],N0,N) :-
( nonvar(N) -> N >= N0 ; true ),
N1 is N0 + 1,
list_length(Ls,N1,N).

As far as I can see (but that's not necessarily very far :-), this
should give the same result as the Sicstus version you mentioned.

>Gj

John
----
john dot cullen (at) portoeditora dot pt

Algernon

2004-07-07, 8:57 pm

Thanks John,

I had finally come up with:
list_length(List,N) :- list_length(List,0,N).

list_length([],N,N).
list_length([_L|Ls],N0,N) :-
( nonvar(N), N0 >= N ->
!, fail
; N1 is N0 + 1,
list_length(Ls,N1,N)
).

However I didnt much care for the cut fail combo. I liked your solution
better.

Thanks also to vannoord and bart also. I guess I didnt make myself clear.
Let me rephrase my last question, Do the built-in predicates such as length,
nth0 and nth1 have access to the underlying architecure of either the prolog
implementation or the computer such that they can determine the length (or
index of an element therein) etc of a list in some constant time? By unit
time I meant that the built-in (+)/2 can evaluate an expression in unit time
whereas if we were to define X + Y as sigma(0 to X-1)(Y+1) it would not be
unit time.

vannoord@let.rug.nl

2004-07-08, 3:56 am

Algernon <algernon@dmv.com> wrote:

> Thanks also to vannoord and bart also. I guess I didnt make myself clear.
> Let me rephrase my last question, Do the built-in predicates such as length,
> nth0 and nth1 have access to the underlying architecure of either the prolog
> implementation or the computer such that they can determine the length (or
> index of an element therein) etc of a list in some constant time? By unit
> time I meant that the built-in (+)/2 can evaluate an expression in unit time
> whereas if we were to define X + Y as sigma(0 to X-1)(Y+1) it would not be
> unit time.

I think Bart understood your question, and his explanation should have
shown that the answer is "no" (and must be "no" too).

Gj

--
Gertjan van Noord Alfa-informatica, RUG, Postbus 716, 9700 AS Groningen
vannoord at let dot rug dot nl http://www.let.rug.nl/~vannoord

algernon

2004-07-16, 8:58 pm

<vannoord@let.rug.nl> wrote in message
news:ccio9u$c1g$1@info.service.rug.nl...
> I think Bart understood your question, and his explanation should have
> shown that the answer is "no" (and must be "no" too).
>
> Gj
>
>
>
> --
> Gertjan van Noord Alfa-informatica, RUG, Postbus 716, 9700 AS Groningen
> vannoord at let dot rug dot nl http://www.let.rug.nl/~vannoord

But why does it have to be no? Is it not in the interests of the
implementation to have an architecture that allows certain builtin
predicates to be handled (nonlogically). I doubt that there is an
implementation out there that handles arithmetic functionality with
successors used in Art of Prolog so why should they be forced to rely on the
logical structure of lists, when there are
ways around this.

vannoord@let.rug.nl

2004-07-16, 8:58 pm

algernon <dpatterson@dmv.com> wrote:

> <vannoord@let.rug.nl> wrote in message
> news:ccio9u$c1g$1@info.service.rug.nl...
[color=darkred]
> But why does it have to be no? Is it not in the interests of the
> implementation to have an architecture that allows certain builtin
> predicates to be handled (nonlogically). I doubt that there is an
> implementation out there that handles arithmetic functionality with
> successors used in Art of Prolog so why should they be forced to rely on the
> logical structure of lists, when there are
> ways around this.

You can certainly use other representations than 'the logical structure
of lists', but I think the point of Bart's answer was that you can't do
this in constant time.

Gj

--
Gertjan van Noord Alfa-informatica, RUG, Postbus 716, 9700 AS Groningen
vannoord at let dot rug dot nl http://www.let.rug.nl/~vannoord

Sponsored Links