Fwd: Recursive functions and means
You have written:
//uses recursion, but takes advantage of OpenSCAD's automatic looping of
certain recursive function formats.
But all your examples are not tail recursive. This is the tail recursive
version I posted earlier, it ends with only a call to itself:
function sum(values, i = 0, sum = 0) =
i == len(values) ? sum : sum(values, i + 1, sum + values[i]);
sum + values[i] is calculated before it calls itself.
values[i] + sum(values, i+1)
Must call sum first and then add values[i] after it returns to itself, so
isn't a simple loop.
On 25 February 2017 at 02:33, Ari Diacou ari.diacou@gmail.com wrote:
I think it works now:
A=[2,3,4];
m=-2;
echo(str("A=",A));
echo(str("power mean(A,",m,")=",power_mean(A,m)));
echo(str("arithmetic mean=",mean(A)));
echo(str("harmonic mean=",harmonic_mean(A)));
echo(str("sum=",sum(A)));
echo(str("product=",product(A)));
echo(str("invert(A)=",invert(A)));
echo(str("power_each(A,",m,")=",power_each(A,m)));
function sum(values,i=0)=(
//outputs the sum of a list of values
//uses recursion, but takes advantage of OpenSCAD's automatic looping
of certain recursive function formats.
i==len(values) ? 0 :
values[i] + sum(values, i+1)
);
function product(values,i=0)=(
//outputs the product of a list of values
i==len(values) ? 1 :
values[i]*product(values, i+1)
);
function mean(values,i=0)=(
//outputs the arithmetic mean of a list of values
//uses recursion, but takes advantage of OpenSCAD's automatic looping
of certain recursive function formats.
//See https://en.wikipedia.org/wiki/Mean#Arithmetic_mean
i==len(values) ? 0 :
values[i] + sum(values, i+1)
)/len(values);
function geometric_mean(values)=pow(product(values),1/len(values));
//outputs the geometric mean of a list of values //uses recursion, but
takes advantage of OpenSCAD's automatic looping of certain recursive
function formats. See https://en.wikipedia.org/wiki/Mean#Geometric_mean
function harmonic_mean(values,i=0)=len(values)/sum(invert(values));
//outputs the harmonic mean of a list of values //uses recursion, but takes
advantage of OpenSCAD's automatic looping of certain recursive function
formats. //See https://en.wikipedia.org/wiki/Mean#Harmonic_mean
function invert(values)=[for(i=[0:len(values)-1]) 1/values[i]]; //inverts
each value in a list
function power_each(values,n)=[for(i=[0:len(values)-1])
pow(values[i],n)]; //returns a list of each value in a list raised to the
power of n. n can be any value.
function power_mean(values,m)=pow(sum(power_each(values,m))/len(values),1/m);
//See https://en.wikipedia.org/wiki/Mean#Generalized_means
On Fri, Feb 24, 2017 at 6:28 PM, Ari Diacou ari.diacou@gmail.com wrote:
That was the part of the wikibook i didn't understand, although I at
least updated the link to the wikipedia article.
On Fri, Feb 24, 2017 at 6:25 PM, nop head nop.head@gmail.com wrote:
echo(sum([1,2,3]));
function sum(values, i = 0, sum = 0) =
i == len(values) ? sum : sum(values, i + 1, sum + values[i]);
Is a better way to do it because it uses tail recursion. I.e. it ends by
calling itself. That is optimised to a loop by OpenSCAD, so it doesn't run
out of stack.
On 24 February 2017 at 23:23, Ari Diacou ari.diacou@gmail.com wrote:
Nice, I like that format better.
On Fri, Feb 24, 2017 at 6:21 PM, nop head nop.head@gmail.com wrote:
echo(sum([1,2,3]));
function sum(values, i = 0) =
i == len(values) ? 0 : values[i] + sum(values, i + 1);
Works.
On 24 February 2017 at 23:18, nop head nop.head@gmail.com wrote:
When i == len(values) you return values[i] but lists are indexed from
0, so you are try to access one past the end, hence the undef.
On 24 February 2017 at 23:10, Ari Diacou ari.diacou@gmail.com
wrote:
I am trying to write arithmetic, geometric and harmonic mean
functions in openscad.
It appears I need to use recursion (
Here is my program:
echo(sum([1,2,3]));
function sum(values,i=0)=(
(i==len(values)) ?
values[i] :
values[i] + sum(values, //f,
i+1)
);
The output should be 6. with the comment in line 5, the output is
undef, if you uncomment the "f," you get 5 errors, not 3, which means there
are too many calls.
Can anyone give me some help?
I took a look at the WikiBook, but it didnt help me much:
https://en.wikibooks.org/w/index.php?title=OpenSCAD_User_Man
ual/User-Defined_Functions_and_Modules&stable=0#Recursive_functions
Or if you have already written the functions I want (product, sum,
aritmentic mean, harmonic mean, and geometric mean) of a list of values,
send me those.
Thanks,
Ari M Diacou, Metis Industries
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.ope
nscad.org
It should be emphasized that non-tail recursive calls are subjected to
depth limits by the system - something like 10000. Recursions with tail
recursion elimination format have a much greater limit.
Thanks NopHead again. I think the following code implements the correct
format. Ronaldo, what you are saying sounds like what was in the WikiBook,
but as a mere physicist, I had no idea what "tail recursion elimination
format" meant (other than "MAGIC format"). Thanks though.
//////////////////// Main() ////////////////////////
A=[2,1,3,2];
B=[4,2,-1,1];
m=-2;
echo(str("A=",A));
echo(str("B=",B));
echo(str("A.B=",dot(A,B)));
echo(str("power mean(A,",m,")=",power_mean(A,m)));
echo(str("arithmetic mean=",mean(A)));
echo(str("harmonic mean=",harmonic_mean(A)));
echo(str("sum=",sum(A)));
echo(str("product=",product(A)));
echo(str("invert(A)=",invert(A)));
echo(str("power_each(A,",m,")=",power_each(A,m)));
///////////////// Functions ////////////////////////
/////////////// Types of Means /////////////////////
function sum(values, i=0, sum=0) =
i == len(values) ? sum : sum(values, i+1, sum+values[i]);
//outputs the sum of a list of values
//uses recursion, but takes advantage of OpenSCAD's automatic looping
of certain recursive function formats.
//Σ{i=[0:n-1]} values[i]
function product(values, i=0, total=1) =
i==len(values) ? total : product(values,i+1,total*values[i]);
//outputs the product of a list of values
//uses recursion, but takes advantage of OpenSCAD's automatic looping
of certain recursive function formats.
//Π{i=[0:n-1]} values[i]
function dot(A,B,i=0,total=0)=
len(A)!=len(B) ? undef :
i==len(A) ? total :
dot(A,B,i+1,A[i]*B[i]+total);
//outputs the dot product of two vectors if the lengths are the same,
otherwise, reports "undef"
//uses recursion, but takes advantage of OpenSCAD's automatic looping
of certain recursive function formats.
//Σ{i=[0:n-1]} values[i]
function mean(values)=sum(values)/len(values);
//outputs the arithmetic mean of a list of values
//uses recursion, but takes advantage of OpenSCAD's automatic looping
of certain recursive function formats.
//See https://en.wikipedia.org/wiki/Mean#Arithmetic_mean
//(1/n)*(Σ{i=[0:n-1]} values[i])
function geometric_mean(values)=pow(product(values),1/len(values));
//outputs the geometric mean of a list of values
//uses recursion, but takes advantage of OpenSCAD's automatic looping
of certain recursive function formats. See
https://en.wikipedia.org/wiki/Mean#Geometric_mean
// n*(Σ{i=[0:n-1]} values[i] )^(1/n)
function harmonic_mean(values,i=0)=len(values)/sum(invert(values));
//outputs the harmonic mean of a list of values //uses recursion, but
takes advantage of OpenSCAD's automatic looping of certain recursive
function formats.
//See https://en.wikipedia.org/wiki/Mean#Harmonic_mean
// n/(Σ{i=[0:n-1]} 1/values[i] )
function invert(values)=[for(i=[0:len(values)-1]) 1/values[i]];
//inverts each value in a list
// [1/values[i]]
function power_each(values,n)=[for(i=[0:len(values)-1]) pow(values[i],n)];
//returns a list of each value in a list raised to the power of n. n
can be any value.
// [values[i]^(n)]
function
power_mean(values,m)=pow(sum(power_each(values,m))/len(values),1/m); //See
https://en.wikipedia.org/wiki/Mean#Generalized_means //((1/n)*Σ{i=[0:n-1]}
values[i]^m)^(1/m)
function weighted_mean(values,weights)=dot(values,weights)/sum(weights);
// (Σ{i=[0:n-1]} values[i]*weights[i]) / (Σ{i=[0:n-1]} weights[i])
//See: https://en.wikipedia.org/wiki/Weighted_arithmetic_mean
On Sat, Feb 25, 2017 at 9:14 AM, Ronaldo Persiano rcmpersiano@gmail.com
wrote:
It should be emphasized that non-tail recursive calls are subjected to
depth limits by the system - something like 10000. Recursions with tail
recursion elimination format have a much greater limit.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
2017-02-25 18:39 GMT-03:00 Ari Diacou ari.diacou@gmail.com:
Ronaldo, what you are saying sounds like what was in the WikiBook, but as
a mere physicist, I had no idea what "tail recursion elimination format"
meant (other than "MAGIC format").
Ok, I understand your non understanding :) Recursion is not fully
intuitive. And I am not a specialist on it. Here is my understanding of the
subject.
First the jargon:
- tail recursion means that the recursion is the last (so tail) done
operation; - elimination refers to the internal operation the system does transforming
the recursion in a iteration.
Your first coding of sum() is not tail-recursive because the last operation
of values[i] + sum(values, i+1) is the operation + as nop heap pointed out.
The elimination process is done by the system (OpenSCAD). It creates an
iteration where the last sum is passed to next step without a function
call. It is not easy for the system to recognize a tail recursion and
provide an elimination of it. So, not all tail recursion is entitled to be
eliminated by OpenSCAD evaluator. For instance, the tail recursion in:
function sum(values, i=0, sum=0) =
let( n=len(values) )
i==n ?
sum:
sum(values, i+1, sum+values[i]);
is not transformed in an iteration by OpenSCAD because of the let(). Only
the two strict tail recursion formats you find in the Manual are in fact
entitled to be eliminated. It is not magic. It is a restriction.