anjo@swi.psy.uva.nl (Anjo Anjewierden) (02/13/90)
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).lee@munnari.oz.au (Lee Naish) (02/14/90)
In article <2733@swi.swi.psy.uva.nl> anjo@swi.psy.uva.nl () writes: >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
stolcke@icsi.Berkeley.EDU (Andreas Stolcke) (02/15/90)
In article <3179@munnari.oz.au>, lee@munnari.oz.au (Lee Naish) writes: > > 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 International Computer Science Institute stolcke@icsi.Berkeley.EDU 1957 Center St., Suite 600, Berkeley, CA 94704 (415) 642-4274 ext. 126