std.range should support recursion (Was: One-line FFT, nice!)

[jerro]

On Tuesday, 25 September 2012 at 17:48:49 UTC, jerro wrote:
>> import std.algorithm, std.math, std.range;
>> typeof(R.init.stride(0)) dft(R)(R v)
>> {
>> 	return v.length <= 1
>> 	? v.stride(1)
>> 	: (p =>
>> 	   chain(map!(q => q[0] + q[1])(p),
>> 	         map!(q => q[0] - q[1])(p)))
>> 	  (zip(dft(v.stride(2)),
>> 		map!(p => p[1] * expi(p[0] * -2 * PI / v.length))
>> 		(zip(iota(v.length / 2),
>> 		 dft(v.drop(1).stride(2))))));
>> }
>> void main() { dft([1.0, 2, 3]); }
>>
>>
>> Which gives the following error:
>>
>>
>> Test.d(5): Error: incompatible types for ((stride(v,1u)) ? 
>> ((*delegate @system 
>> Result(Zip!(Result,MapResult!(__lambda8,Zip!(Result,Result))) 
>> p)
>> {
>> 	return chain(map(p),map(p));
>> }
>> )(zip(dft(stride(v,2u)),map(zip(iota(v.length() / 
>> 2u),dft(stride(drop(v,1u),2u)))))))): 'Result' and 'Result'
>> Test.d(10): Error: template instance Test.dft!(Result) error 
>> instantiating
>> Test.d:19: instantiated from here: dft!(double[])
>> Test.d(5): Error: incompatible types for ((stride(v,1u)) ? 
>> ((*delegate @system 
>> Result(Zip!(Result,MapResult!(__lambda8,Zip!(Result,Result))) 
>> p)
>> {
>> 	return chain(map(p),map(p));
>> }
>> )(zip(dft(stride(v,2u)),map(zip(iota(v.length / 
>> 2u),dft(stride(drop(v,1u),2u)))))))): 'Result' and 'Result'
>> Test.d(19): Error: template instance Test.dft!(double[]) error 
>> instantiating
>>
>>
>>
>> How should I interpret it?
>>
>> Thanks!
>
> One possible reason for this error could be that you are 
> returning a result of chain() if length is larger than 1 and a 
> result of stride() otherwise.

I'd like to add that I don't think you can make this work the way 
you meant it to. The problem is that you return a chain when the 
length is 2, a chain of chains when the length is 4, and so on. 
What fft of length n would actually need to return is a binary 
tree of ranges with n leaves. The size of memory needed for the 
value returned from fft therefore depends on the length of the 
range it was given as an argument. So you need to either use heap 
allocated memory for the return type, or the return type needs to 
depend on the parameter range's length, which would mean that the 
parameter range's length needs to be a template parameter.

I think there is one thing in this code that will hurt 
performance much, much, more than allocations. This code will 
compute elements of the result lazily. So each time you want to 
read an element from the resulting range, O(log(n)) functions 
passed to map() will need to be computed. The problem is that 
each of those functions computes sine and cosine, so sine and 
cosine need to be computed O(log(n)) times for each element. To 
get all n elements, you will need to compute them O(n log(n)). 
Because computing sine and cosine is about two orders of 
magnitude slower than multiplication and division, this will be 
very slow.