Re: pls confirm what approach is more efficient

mneuhaber22@xxxxxxxxxx wrote:

Can all left recursive functions be transformed into right recursive? 

The answer to this wouldn't help you.

Can all predicates that consume resources proportionate to the size of
the input set be rewritten cleverly to consume constant resources?


Is this asking whether the (space) complexity classes
linear-space and constant-space are equal ? I bet they are not :-)

If the answer to these questions is no, then what classes of problems
lend themselves to more efficient rewrite and how?


I have no answer.

I wish I could understand your thinking that led you to write sum/3. 

Ah, this is an easy one :-) It is standard practice in declarative
languages.

The general technique is called "accumulating parameter" and you do it all the time in C; e.g. the sum function would be something like:

	accu = 0;
	while is_list(L)
		{
			accu = accu + head(L);
			L = L->next;
		}
	return(accu);

Often, when you would transform a recursive C-function into a while loop
(or a for), you would introduce such a variable that holds the value
"up-to-now". It accumuilates until it has the final value. The
equivalent in Prolog is: transforming a left-recursive predicate
into a tail-recursive one (the while loop) with an extra parameter.
Saumya Debray has some paper(s) about it and his PhD Thesis contains
stuff about it as well - to do it automatically I mean.

Cheers

Bart Demoen
.