Prolog - Any way to tail-recurse this?

Author

Any way to tail-recurse this?

pineapple.link@yahoo.com

2007-08-21, 10:07 pm

Just adding up numbers in a list. I already know you could do the
below better, cleaner, and in fewer steps. My question is how to tail-
recurse it, if possible.

(the first arg in the predicate is the list, the second is the
"total")

Thanks.
---------------------

addlist([],0).
addlist([X],X).
addlist([H|[X]],Y) :- Y is H+X. %This pred is probably unnecessary,
but aids my understanding
addlist([H1|[H2|T]],Y1) :- addlist([H2|T],Y2), Y1 is H1+Y2.

pineapple.link@yahoo.com

2007-08-22, 8:06 am

Think I figured out one....

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

Pierpaolo BERNARDI

2007-08-22, 7:07 pm

On Wed, 22 Aug 2007 14:33:56 +0200, <pineapple.link@yahoo.com> wrote:

> Think I figured out one....
>
> addlist([],0).
> addlist([X],X).
> addlist([First|[Second|Rest]],Total) :- Total2 is Total-First,
> addlist([Second|Rest], Total2).

Ingenious, but addlist([1,2,3],T) to calculate the sum does not work.
It can only check that the sum you supply is correct.
I think you have not found the solution of the exercise yet. :)

Note that [A|[B|C]] is the same as [A,B|C].
The second way of writing is easier to read.

P.

Steve Harlow

2007-08-22, 7:07 pm

In article <op.txgr0vo1xbm8ci@eraora>,
"Pierpaolo BERNARDI" <pierpaolo@secondbox.net> wrote:

> On Wed, 22 Aug 2007 14:33:56 +0200, <pineapple.link@yahoo.com> wrote:
>
>
> Ingenious, but addlist([1,2,3],T) to calculate the sum does not work.
> It can only check that the sum you supply is correct.
> I think you have not found the solution of the exercise yet. :)
>
> Note that [A|[B|C]] is the same as [A,B|C].
> The second way of writing is easier to read.
>
> P.

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

pineapple.link@yahoo.com

2007-08-22, 7:07 pm

> "Pierpaolo BERNARDI" <pierpaolo@secondbox.net> wrote:

Thanks (my own personal exercise, BTW - not a class I'm taking).

What, exactly, is the "rule" for activating the ability to have Prolog
"fill in" a variable... in this case calculating the sum? Is it
something to do with "instantiation" or "non-instantiation" of a
variable?
[color=darkred]
> addlist([],0).
> addlist([X],X).
> addlist([First, Second|Rest], Total) :-
> Sum is First+Second,
> addlist([Sum|Rest], Total).

Excellent! Much easier to understand. Now why didn't I think of that?

bart demoen

2007-08-22, 7:07 pm

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

pineapple.link@yahoo.com

2007-08-22, 7:07 pm

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

I am impressed with your analysis, and code contribution. However,
are you saying that the above code (the poster above you, and perhaps
my last attempt as well, albeit an uglier version) is NOT tail-
recursive? From what I have read, it seems that it should be. It
does some work and gets that stuff "out of the way," and then lastly
calls itself again.

If it is not tail-recursive, can you tell me why not?

Thanks.

bart demoen

2007-08-22, 7:07 pm

On Wed, 22 Aug 2007 10:15:45 -0700, pineapple.link wrote:

>
> I am impressed with your analysis, and code contribution. However,
> are you saying that the above code (the poster above you, and perhaps
> my last attempt as well, albeit an uglier version) is NOT tail-
> recursive? From what I have read, it seems that it should be. It
> does some work and gets that stuff "out of the way," and then lastly
> calls itself again.
>
> If it is not tail-recursive, can you tell me why not?

Your version was tail-recursive.

I should have been more clear and written something like:

You are a small step away from a tailrecursive version that at
the same time keeps ... as a separate accu.

It is kind of a waste to put the accu in a datastructure - but as the
other poster noted, quite cunning.

Now that I am at it, maybe a little thing on case analysis.
if you deal with lists, there are usually only two cases: the empty list
and the non-empty list. If you think a predicate that deals with lists
needs more than these two cases, there are only the following five
possibilities:

you are wrong and need to rethink
you are wrong and need to rethink
you are wrong and need to rethink
you are wrong and need to rethink
you were right

:-)

Cheers

Bart Demoen

pineapple.link@yahoo.com

2007-08-22, 7:07 pm

Thanks - I hope I'm learning a little something here. Tell me - why
is it a waste to keep the accumulator in the data structure (albeit
cunning, as you mentioned), and what is the advantage of the way you
do it?

Again, thanks.

(It is quite difficult to get the "hang" of this "thinking
recursively," but I'm trying, and at least I did come up with a
recursive solution, albeit an ugly one, heh)

bart demoen

2007-08-22, 7:07 pm

On Wed, 22 Aug 2007 11:18:39 -0700, pineapple.link wrote:

> Thanks - I hope I'm learning a little something here. Tell me - why
> is it a waste to keep the accumulator in the data structure (albeit
> cunning, as you mentioned), and what is the advantage of the way you
> do it?
>
> Again, thanks.
>
> (It is quite difficult to get the "hang" of this "thinking
> recursively," but I'm trying, and at least I did come up with a
> recursive solution, albeit an ugly one, heh)

It wasn't ugly. But it is a bit more difficult to understand.
Because ...
When one tries to give a declarative reading of a predicate, one
usually tries to establish a relationship between the arguments
of the predicate. For instance for my

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

the relationship addlist/3 establishes between its three arguments
X,Y and Z is

Z equals the sum of Y and the value of every element in X

That is made a bit easier by having the extra accumulator argument.

When you hide the accumulator inside another argument of a predicate,
a similar statement usually becomes more involved. Since you wrote your
version of addlist yourself, maybe you should try to come up with a
reading that gives a relationship between its arguments.

About the waste - let me first repeat your definition of addlist/2

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

It is clear to us that the recursive call only can match the heads of the
second and third clause of addlist/2 - most Prolog systems don't exploit
this - XSB is an exception. For most implementations, it is a waste of
cpu cycles to construct a list with first element Sum, just to take the
list apart in the next activation of addlist - a waste in time and space.
But you might not be interested in efficiency of course.
The waste is then solely in the brain cycles to understand it, because
the reading is more difficult (I'm challenging you for the second time :-)

Cheers

Bart Demoen

Sponsored Links