Definition of list_length/2
Author Message
Definition of list_length/2

Below is a definition of list_length/2 (length/2 in Edinburgh
compatibles).  I would like to know whether there is a better/shorter
solution that handles all cases and is deterministic given certain
calling patterns (see definition below).

-- Anjo.

%   list_length(?List, ?Length)
%
%   List is a list of length Length.
%
%   Note: list_length/2 is deterministic if the arguments are
%   sufficiently instantiated (i.e. if Length is given and/or
%   List is a proper list), otherwise it generates alternative
%   solutions on backtracking.

list_length(List, Length) :-
integer(Length), !,
list_length_det(List, Length).  % Always deterministic
list_length(List, Length) :-
var(Length),
list_length_non(List, Length).  % Possibly non-deterministic

/*
list_length_non(List, N) :-             % This clause only if the Prolog
List == [], !,                  %  does not perform clause indexing.
N = 0.
*/
list_length_non([], 0).
list_length_non([_|Xs], N) :-
list_length_non(Xs, M),
N is M+1.

list_length_det([], 0) :- !.
list_length_det([_|Xs], N) :-
M is N-1,
list_length_det(Xs, M).

Sat, 01 Aug 1992 23:27:17 GMT
Definition of list_length/2

Quote:

>Below is a definition of list_length/2 (length/2 in Edinburgh
>compatibles).  I would like to know whether there is a better/shorter
>solution
>list_length_non([], 0).
>list_length_non([_|Xs], N) :-
>        list_length_non(Xs, M),
>        N is M+1.

This bit is not tail recursive and can easily be improved using an
accumulator (this is something you should always look out for):

list_length_non(Xs, N) :-
list_length_non_ac(Xs, 0, N).

list_length_non_ac([], N, N).
list_length_non_ac([_|Xs], N0, N) :-
N1 is N0 + 1,
list_length_non_ac(Xs, N1, N).

lee

Sun, 02 Aug 1992 09:13:43 GMT
Definition of list_length/2

Quote:

> list_length_non(Xs, N) :-
>    list_length_non_ac(Xs, 0, N).

> list_length_non_ac([], N, N).
> list_length_non_ac([_|Xs], N0, N) :-
>    N1 is N0 + 1,
>    list_length_non_ac(Xs, N1, N).

To avoid endless recursion after the first (and only) solution to
length( -L, +N), while still allowing unrestricted backtracking for
length( -L, -N):

length(Xs, N) :-
length(Xs, 0, N).

length([], N, N).
length([_|Xs], N0, N) :-
(
var( N ), !
;
N0 < N
),
N1 is N0 + 1,
length(Xs, N1, N).

----
Andreas Stolcke

1957 Center St., Suite 600, Berkeley, CA 94704  (415) 642-4274 ext. 126

Mon, 03 Aug 1992 03:13:42 GMT

 Page 1 of 1 [ 3 post ]

Relevant Pages