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  
 
 [ 3 post ] 

 Relevant Pages 

1. Query on macro definitions within macro definitions within...

2. GUI-definition questions

3. Local words and definitions?

4. E-mail _can_ work for language definition

5. adverb definition via : in J 3.2

6. function dependencies and tacit definitions (J)

7. DDEF, a Direct Definition Workspace

8. Free Class Definition Generator add-on for ReStore Released

9. command language definition

10. Printing out a whole class definition

11. How can i write class definitions literally?

12. Help Library Glossary Definitions

 

 
Powered by phpBB® Forum Software