Re: Any way to tail-recurse this?

On Wed, 22 Aug 2007 16:31:46 +0100, Steve Harlow wrote:


addlist([],0).
addlist([X],X).
addlist([First, Second|Rest], Total) :-
Sum is First+Second,
addlist([Sum|Rest], Total).

You are now just a small step away from a tailrecursive version,
that keeps the head of the list as a separate accumulating parameter:

addlist([],0).
addlist([X|R],N) :- addlist(R,X,N).

addlist([],N,N).
addlist([X|R],In,Out) :- NewIn is In + X, addlist(R,NewIn,Out).

The usual tailrecursive version of addlist goes like this however:

addlist(L,N) :- addlist(L,0,N).

<and then the addlist/3 definition above>

It is worthwhile trying to give a declarative reading of addlist/3.


Tailrecursive predicates are usually associated with an accumulating
parameter. There is also a direct relation with a while loop for
computing the sum of the list elements in an imperative language:

result := 0; % initialize the accumulating parameter
while not at end of list
result := result + head(list);
list := tail(list)

Cheers

Bart Demoen
.