D Recurrences

Steven Schveighoffer schveiguy at yahoo.com
Thu Jun 9 10:11:31 PDT 2011


On Thu, 09 Jun 2011 13:06:54 -0400, Ben Grabham <Evil.Nebster at gmail.com>  
wrote:

> On 09/06/11 17:57, bearophile wrote:
>> Ben Grabham:
>>
>>> import std.range;
>>> import std.stdio;
>>> int main() {
>>> 	auto a = recurrence!("a[n-1] + a[n-2]")(0,1);
>>> 	int i = 0;
>>> 	foreach(int n; a) {
>>> 		if(i++>  20) break;
>>> 		writefln("%d", n);
>>> 	}
>>> 	return 0;
>>> }
>>
>> This program does something similar to yours (but it doesn't print  
>> newlines):
>>
>>
>> import std.stdio, std.range;
>>
>> void main() {
>>      auto fib = recurrence!q{ a[n-1] + a[n-2] }(0, 1);
>>      writeln(take(fib, 21));
>> }
>>
>> Bye,
>> bearophile
>
> Yeah, thanks
>
> I just wanted to post a bit of code which went wrong :P
> Didn't look for optimisations.
>
> Also, how come recurrence isn't properly lazy?
> If I define a recurrence and iterate over it twice with foreach, it  
> takes the same amount of time due to the stack size being set. Is there  
> a way of defining a lazy list that stores the results when calculated?

That's not lazy, that's caching.  lazy is 'calculate this when asked'.

You can cache with array:

auto cached = array(take(fib, 21));
// cached now contains the first 21 elements of fib.

-Steve


More information about the Digitalmars-d mailing list