www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - D Recurrences

reply Ben Grabham <Evil.Nebster gmail.com> writes:
Hey,

Shouldn't both these programs output the fibonnacci numbers? Only the 
first one does.

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;
}



import std.range;
import std.stdio;
int main() {
	auto a = recurrence!("a[n-1] + (n < 2 ? 0 : a[n-2])")(1);
	int i = 0;
	foreach(int n; a) {
		if(i++ > 20) break;
		writefln("%d", n);
	}
	return 0;
}
Jun 09 2011
next sibling parent reply Ben Grabham <Evil.Nebster gmail.com> writes:
On 09/06/11 16:19, Ben Grabham wrote:
 Hey,

 Shouldn't both these programs output the fibonnacci numbers? Only the
 first one does.

 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;
 }



 import std.range;
 import std.stdio;
 int main() {
 auto a = recurrence!("a[n-1] + (n < 2 ? 0 : a[n-2])")(1);
 int i = 0;
 foreach(int n; a) {
 if(i++ > 20) break;
 writefln("%d", n);
 }
 return 0;
 }

Also, is there a takeWhile function? I can't find one in the documents...
Jun 09 2011
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
Ben Grabham wrote:
 Also, is there a takeWhile function?
 I can't find one in the documents...

Not yet, but hopefully there will be: http://d.puremagic.com/issues/show_bug.cgi?id=4535
Jun 09 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/9/11 10:42 AM, Timon Gehr wrote:
 Ben Grabham wrote:
 Also, is there a takeWhile function?
 I can't find one in the documents...

Not yet, but hopefully there will be: http://d.puremagic.com/issues/show_bug.cgi?id=4535

I think what's unclear is that until() has an overload that takes only the predicate and the range. There's no example for that, so the definition kinda gets lost in the noise. // scan range up until the first zero auto a = until!"a == 0"(range); Andrei
Jun 09 2011
parent Timon Gehr <timon.gehr gmx.ch> writes:
Andrei Alexandrescu wrote:
 On 6/9/11 10:42 AM, Timon Gehr wrote:
 Ben Grabham wrote:
 Also, is there a takeWhile function?
 I can't find one in the documents...

Not yet, but hopefully there will be: http://d.puremagic.com/issues/show_bug.cgi?id=4535

I think what's unclear is that until() has an overload that takes only the predicate and the range. There's no example for that, so the definition kinda gets lost in the noise. // scan range up until the first zero auto a = until!"a == 0"(range); Andrei

Oh, I did not know that. That makes things quite a bit better. Still, takeWhile > until. Timon
Jun 09 2011
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/9/11 10:32 AM, Ben Grabham wrote:
 On 09/06/11 16:19, Ben Grabham wrote:
 Hey,

 Shouldn't both these programs output the fibonnacci numbers? Only the
 first one does.

 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;
 }



 import std.range;
 import std.stdio;
 int main() {
 auto a = recurrence!("a[n-1] + (n < 2 ? 0 : a[n-2])")(1);
 int i = 0;
 foreach(int n; a) {
 if(i++ > 20) break;
 writefln("%d", n);
 }
 return 0;
 }

Also, is there a takeWhile function? I can't find one in the documents...

until? Andrei
Jun 09 2011
parent Timon Gehr <timon.gehr gmx.ch> writes:
 On 6/9/11 10:32 AM, Ben Grabham wrote:
 On 09/06/11 16:19, Ben Grabham wrote:
 Hey,

 Shouldn't both these programs output the fibonnacci numbers? Only the
 first one does.

 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;
 }



 import std.range;
 import std.stdio;
 int main() {
 auto a = recurrence!("a[n-1] + (n < 2 ? 0 : a[n-2])")(1);
 int i = 0;
 foreach(int n; a) {
 if(i++ > 20) break;
 writefln("%d", n);
 }
 return 0;
 }

Also, is there a takeWhile function? I can't find one in the documents...

until? Andrei

until is not generic enough. It requires you to provide a dummy parameter if you want to use an unary predicate. And you will have to reverse the predicate: Thinking "while" is more convenient than thinking "until". Phobos should definitely get a takeWhile function. Timon
Jun 09 2011
prev sibling next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
Ben Grabham wrote:
 Hey,

 Shouldn't both these programs output the fibonnacci numbers? Only the
 first one does.

 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;
 }



 import std.range;
 import std.stdio;
 int main() {
  auto a = recurrence!("a[n-1] + (n < 2 ? 0 : a[n-2])")(1);
  int i = 0;
  foreach(int n; a) {
   if(i++ > 20) break;
   writefln("%d", n);
  }
  return 0;
 }

You use the function recurrence incorrectly in the second example: You may only use a[n-1] to a[n-x] in your formula where x is the number of arguments given to the template function. It would be nice if the library could enforce this, but (at least currently) it cannot. Timon
Jun 09 2011
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/9/11 10:19 AM, Ben Grabham wrote:
 Hey,

 Shouldn't both these programs output the fibonnacci numbers? Only the
 first one does.

 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;
 }



 import std.range;
 import std.stdio;
 int main() {
 auto a = recurrence!("a[n-1] + (n < 2 ? 0 : a[n-2])")(1);
 int i = 0;
 foreach(int n; a) {
 if(i++ > 20) break;
 writefln("%d", n);
 }
 return 0;
 }

The second implementation is in error. The state of the recurrence is defined by the number of parameters, so it will consist of one number. Fibonacci needs the last two numbers. The code doesn't fail because recurrence uses modulus with all indices, which means a[n-1] and a[n-2] will refer to the same (and only) element in the recurrence state. It would be be possible to detect this at run time, but it would slow things down a bit. Andrei
Jun 09 2011
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
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
Jun 09 2011
next sibling parent reply Ben Grabham <Evil.Nebster gmail.com> writes:
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? Thanks, Nebster
Jun 09 2011
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/9/11 12:06 PM, Ben Grabham wrote:
 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?

recurrence() is very simple: it starts with the state you pass to it. Then each popFront() overwrites the head of the state (heh) with the calculated value from the existing state. I agree that one could delay any computation until the initial state is exhausted - for example, if the state size is 100, then there's no need to do anything for the first 99 steps. That's far from a common case however as most recurrences have small states and are iterated numerous times. The necessary bookkeeping would slow down that common case a bit. Andrei
Jun 09 2011
prev sibling parent reply Ben Grabham <Evil.Nebster gmail.com> writes:
On 09/06/11 18:11, Steven Schveighoffer wrote:
 On Thu, 09 Jun 2011 13:06:54 -0400, Ben Grabham <Evil.Nebster 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

I tried that, but how can I calculate the values only when I want them? Would I have to store them in a linked list? Since if I know that I will need 100000 prime numbers, it takes my old pc about 4.7 seconds to calculate them. But can I only calculate them when I need them? I am running through the recurrence twice so I don't want to calculate it twice. This is theoretical so please no answers like put them both in one loop, etc. Thanks for all the info so far! I'm learning quite a lot! Thanks, Nebster
Jun 09 2011
parent reply Ben Grabham <Evil.Nebster gmail.com> writes:
On 09/06/11 18:49, Steven Schveighoffer wrote:
 On Thu, 09 Jun 2011 13:31:18 -0400, Ben Grabham <Evil.Nebster gmail.com>
 wrote:

 On 09/06/11 18:11, Steven Schveighoffer wrote:
 On Thu, 09 Jun 2011 13:06:54 -0400, Ben Grabham <Evil.Nebster 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

I tried that, but how can I calculate the values only when I want them? Would I have to store them in a linked list? Since if I know that I will need 100000 prime numbers, it takes my old pc about 4.7 seconds to calculate them. But can I only calculate them when I need them?

It's a recurring sequence. As such, each element depends on the previous n elements. I don't see how you can only calculate them when needed, unless you want to do some sort of memoization with recursion. recurrence expects to be traversed in a certain order, it's sort of like dynamic programming. The array simply stores all the values needed to an array, so you can re-access the same values without running through the recurrence. One thing you could do is using Appender, you can continue a recurrence. So let's say you need the 5th element of the array: alias recurrence!q{ a[n-1] + a[n-2] } fib; Appender!int app; app.put(take(fib(0, 1), 5)); auto elems = app.data; auto the5thElement = elems[4]; And now, you need the 10th element: app.put(take(fib(elems[$-2], elems[$-1]), 10 - elems.length)); // extend sequence to 10 elements elems = app.data; // need to re-retrieve the elements auto the10thElemet = elems[9]; Kind of ugly, but maybe it's close enough to what you want.
 I am running through the recurrence twice so I don't want to calculate
 it twice.

Yes, you only run through it once, then use the array with the cached data to retrieve what you want. Accessing the array does not recalculate the data. The Appender solution simply keeps a running cache of the data. You could probably abstract out the 'extending' function. In fact, this whole thing could be abstracted into a 'cached recurrence' type. -Steve

Thanks, that should do the trick! At the moment I was using auto elems = array(chain(elems, take(primes - elems.length))); or something similar to that Also, when using a foreach, is there a special syntax that says include the last number? As an example, if I want to loop from -n to +n, I have to do foreach(i; -n..n+1) Thanks, Nebster
Jun 09 2011
next sibling parent reply Ben Grabham <Evil.Nebster gmail.com> writes:
On 09/06/11 19:45, Andrej Mitrovic wrote:
 I never understood why it's called "open" interval. What does it 'open'?

Don't know the answer to that one, just know it's always been called a open interval when both endpoints aren't included. D's foreach loops are half-closed intervals. Oh well, that's a shame. I ended up writing a lazy cached list and filter implementation anyway :) It may use more memory but it's worth it for me! Thanks for all the help! Nebster
Jun 09 2011
next sibling parent reply Ben Grabham <Evil.Nebster gmail.com> writes:
On 09/06/11 19:54, Ben Grabham wrote:
 On 09/06/11 19:45, Andrej Mitrovic wrote:
 I never understood why it's called "open" interval. What does it 'open'?

Don't know the answer to that one, just know it's always been called a open interval when both endpoints aren't included. D's foreach loops are half-closed intervals. Oh well, that's a shame. I ended up writing a lazy cached list and filter implementation anyway :) It may use more memory but it's worth it for me! Thanks for all the help! Nebster

Oh, I do have one question though, How does the save property work? I can't seem to be able to return an integer (index) rather than the whole object. How can I do it?
Jun 09 2011
parent reply Ben Grabham <Evil.Nebster gmail.com> writes:
On 09/06/11 20:15, Jonathan M Davis wrote:
 The save property of a forward range returns a copy of that range. In most
 cases, since ranges are generally restructs, it just returns the range. You
 use it when you want to save the original range and still be able pop elements
 off.

 auto orig = range.save;

 //pop off as many elements from range as I want.
 //orig still has all of its elements

 The elements aren't copied however, just the range. Regardless, it has nothing
 to do with returning an element from a range, so I don't understand your
 question about returning an index rather than a whole object. Ranges don't
 really use indicies. indexOf will tell you the index of a particular element,
 and you can increment a counter every time you pop off an element if you want
 to know how many elements you've consumed, but once an element has been popped
 off, it's not part of that range anymore (though it could be part of a saved
 range), so that could seriously affect by what you mean by index, depending on
 what you're doing.

 - Jonathan M Davis

I want to make it so that foreach works but I'm storing an array which when changed, want to keep it like that, even after the foreach, I just want to reset the index to 0 At the moment, I have to do: foreach(i; 0..100) ... lazy._n = 0; foreach(i; 0..100) ... I want to do: foreach(n; lazy) ... foreach(n; lazy) ... Thanks, Nebster
Jun 09 2011
parent Ben Grabham <Evil.Nebster gmail.com> writes:
On 10/06/11 05:43, Jonathan M Davis wrote:
 On 2011-06-09 20:35, Ben Grabham wrote:
 On 09/06/11 20:15, Jonathan M Davis wrote:
 The save property of a forward range returns a copy of that range. In
 most cases, since ranges are generally restructs, it just returns the
 range. You use it when you want to save the original range and still be
 able pop elements off.

 auto orig = range.save;

 //pop off as many elements from range as I want.
 //orig still has all of its elements

 The elements aren't copied however, just the range. Regardless, it has
 nothing to do with returning an element from a range, so I don't
 understand your question about returning an index rather than a whole
 object. Ranges don't really use indicies. indexOf will tell you the
 index of a particular element, and you can increment a counter every
 time you pop off an element if you want to know how many elements you've
 consumed, but once an element has been popped off, it's not part of that
 range anymore (though it could be part of a saved range), so that could
 seriously affect by what you mean by index, depending on what you're
 doing.

 - Jonathan M Davis

I want to make it so that foreach works but I'm storing an array which when changed, want to keep it like that, even after the foreach, I just want to reset the index to 0 At the moment, I have to do: foreach(i; 0..100) ... lazy._n = 0; foreach(i; 0..100) ... I want to do: foreach(n; lazy) ... foreach(n; lazy) ...

0 .. 100 has nothing to do with ranges. That's a built-in feature of foreach. This would use a range foreach(i; iota(0, 100)) because iota generates one, but 0 .. 100 doesn't. But there's no array involved in foreach(i; 0 .. 100) anyway, and you state that you're storing an array as part of this, so I really don't know what you're trying to do. I'd need to see actual code to be of any help. - Jonathan M Davis

Sorry, didn't really make that clear. Inside the foreach, I'm using popFront and front to get the values and then outside, I set the index (_n) back to 0. What I want to do is "save" the _n value and then restore it at the beginning and end of the foreach respectively. I don't have the code on me atm, but when I get hold of it, I'll post it if you still need it. Thanks, Nebster
Jun 11 2011
prev sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On 2011-06-09 11:59, Ben Grabham wrote:
 On 09/06/11 19:54, Ben Grabham wrote:
 On 09/06/11 19:45, Andrej Mitrovic wrote:
 I never understood why it's called "open" interval. What does it 'open'?

Don't know the answer to that one, just know it's always been called a open interval when both endpoints aren't included. D's foreach loops are half-closed intervals. Oh well, that's a shame. I ended up writing a lazy cached list and filter implementation anyway :) It may use more memory but it's worth it for me! Thanks for all the help! Nebster

Oh, I do have one question though, How does the save property work? I can't seem to be able to return an integer (index) rather than the whole object. How can I do it?

The save property of a forward range returns a copy of that range. In most cases, since ranges are generally restructs, it just returns the range. You use it when you want to save the original range and still be able pop elements off. auto orig = range.save; //pop off as many elements from range as I want. //orig still has all of its elements The elements aren't copied however, just the range. Regardless, it has nothing to do with returning an element from a range, so I don't understand your question about returning an index rather than a whole object. Ranges don't really use indicies. indexOf will tell you the index of a particular element, and you can increment a counter every time you pop off an element if you want to know how many elements you've consumed, but once an element has been popped off, it's not part of that range anymore (though it could be part of a saved range), so that could seriously affect by what you mean by index, depending on what you're doing. - Jonathan M Davis
Jun 09 2011
prev sibling next sibling parent David Nadlinger <see klickverbot.at> writes:
On 6/9/11 8:45 PM, Andrej Mitrovic wrote:
 I never understood why it's called "open" interval. What does it 'open'?

I suppose because, in the topological sense, an open set does not include its boundary, while a closed set does. No boundary <=> open seems quite intuitive to me… David
Jun 09 2011
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
Steve Schveighoffer wrote:
 On Thu, 09 Jun 2011 14:45:49 -0400, Andrej Mitrovic
 <andrej.mitrovich gmail.com> wrote:

 I never understood why it's called "open" interval. What does it 'open'?

Look at the terminology section of http://en.wikipedia.org/wiki/Interval_(mathematics) No clue as to the "why" :) -Steve

Actually it does not make too much sense to use the terms open or closed on integer intervals in a strict mathematical sense. If your universe is the integers, all subsets of the integers are neither open nor closed, with the exception of the empty set and the set of all integers, which are both open and closed. :o) Timon
Jun 09 2011
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
Timon Gehr wrote:
 Steve Schveighoffer wrote:
 On Thu, 09 Jun 2011 14:45:49 -0400, Andrej Mitrovic
 <andrej.mitrovich gmail.com> wrote:

 I never understood why it's called "open" interval. What does it 'open'?

Look at the terminology section of http://en.wikipedia.org/wiki/Interval_(mathematics) No clue as to the "why" :) -Steve

Actually it does not make too much sense to use the terms open or closed on integer intervals in a strict mathematical sense. If your universe is the integers, all subsets of the integers are neither open nor closed, with the exception of the empty set and the set of all integers, which are both open > and closed. :o)

I'm sorry, this was misinformation. Actually *all* subsets are both open and closed. Timon
Jun 09 2011
parent KennyTM~ <kennytm gmail.com> writes:
On Jun 10, 11 03:20, Timon Gehr wrote:
 Timon Gehr wrote:
 Steve Schveighoffer wrote:
 On Thu, 09 Jun 2011 14:45:49 -0400, Andrej Mitrovic
 <andrej.mitrovich gmail.com>  wrote:

 I never understood why it's called "open" interval. What does it 'open'?

Look at the terminology section of http://en.wikipedia.org/wiki/Interval_(mathematics) No clue as to the "why" :) -Steve

Actually it does not make too much sense to use the terms open or closed on integer intervals in a strict mathematical sense. If your universe is the integers, all subsets of the integers are neither open nor closed, with the exception of the empty set and the set of all integers, which are both open> and closed. :o)

I'm sorry, this was misinformation. Actually *all* subsets are both open and closed. Timon

That depends on how you define the topology on Z anyway.
Jun 09 2011
prev sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
Andrei Mitrovic wrote:
 On 6/9/11, Steven Schveighoffer <schveiguy yahoo.com> wrote:
 On Thu, 09 Jun 2011 14:45:49 -0400, Andrej Mitrovic
 <andrej.mitrovich gmail.com> wrote:

 I never understood why it's called "open" interval. What does it 'open'?

http://en.wikipedia.org/wiki/Interval_(mathematics) No clue as to the "why" :) -Steve

The why is what I'm after. Let me take a look at some definitions of "open" from thefreedictionary (excluding the definitions under the math section): "Carried on in full view" "Spread out; unfolded" "Accessible to all" "Lacking effective regulation" It seems more natural to me to think of open as something that encompasses a larger scope. E.g. when you spread your arms you have a larger area between your hands, not smaller.

I think it is called open, because you can go into any direction from a point within an open set without leaving the set. There are no boundaries. Timon
Jun 09 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 09 Jun 2011 13:06:54 -0400, Ben Grabham <Evil.Nebster 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
Jun 09 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 09 Jun 2011 13:31:18 -0400, Ben Grabham <Evil.Nebster gmail.com>  
wrote:

 On 09/06/11 18:11, Steven Schveighoffer wrote:
 On Thu, 09 Jun 2011 13:06:54 -0400, Ben Grabham <Evil.Nebster 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

I tried that, but how can I calculate the values only when I want them? Would I have to store them in a linked list? Since if I know that I will need 100000 prime numbers, it takes my old pc about 4.7 seconds to calculate them. But can I only calculate them when I need them?

It's a recurring sequence. As such, each element depends on the previous n elements. I don't see how you can only calculate them when needed, unless you want to do some sort of memoization with recursion. recurrence expects to be traversed in a certain order, it's sort of like dynamic programming. The array simply stores all the values needed to an array, so you can re-access the same values without running through the recurrence. One thing you could do is using Appender, you can continue a recurrence. So let's say you need the 5th element of the array: alias recurrence!q{ a[n-1] + a[n-2] } fib; Appender!int app; app.put(take(fib(0, 1), 5)); auto elems = app.data; auto the5thElement = elems[4]; And now, you need the 10th element: app.put(take(fib(elems[$-2], elems[$-1]), 10 - elems.length)); // extend sequence to 10 elements elems = app.data; // need to re-retrieve the elements auto the10thElemet = elems[9]; Kind of ugly, but maybe it's close enough to what you want.
 I am running through the recurrence twice so I don't want to calculate  
 it twice.

Yes, you only run through it once, then use the array with the cached data to retrieve what you want. Accessing the array does not recalculate the data. The Appender solution simply keeps a running cache of the data. You could probably abstract out the 'extending' function. In fact, this whole thing could be abstracted into a 'cached recurrence' type. -Steve
Jun 09 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 09 Jun 2011 14:02:47 -0400, Ben Grabham <Evil.Nebster gmail.com>  
wrote:

 Also, when using a foreach, is there a special syntax that says include  
 the last number?
 As an example, if I want to loop from -n to +n, I have to do foreach(i;  
 -n..n+1)

No. Almost all ranges in D are open interval on the right (don't include the right element). There are some corner cases where this can be a problem, like if you wanted to iterate all the possible ubyte values, you have to do funky stuff like: foreach(uint _tmp; ubyte.min..ubyte.max + 1) { auto ub = cast(ubyte)_tmp; ... } -Steve
Jun 09 2011
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
I never understood why it's called "open" interval. What does it 'open'?
Jun 09 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 09 Jun 2011 14:45:49 -0400, Andrej Mitrovic  
<andrej.mitrovich gmail.com> wrote:

 I never understood why it's called "open" interval. What does it 'open'?

Look at the terminology section of http://en.wikipedia.org/wiki/Interval_(mathematics) No clue as to the "why" :) -Steve
Jun 09 2011
prev sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 6/9/11, Steven Schveighoffer <schveiguy yahoo.com> wrote:
 On Thu, 09 Jun 2011 14:45:49 -0400, Andrej Mitrovic
 <andrej.mitrovich gmail.com> wrote:

 I never understood why it's called "open" interval. What does it 'open'?

Look at the terminology section of http://en.wikipedia.org/wiki/Interval_(mathematics) No clue as to the "why" :) -Steve

The why is what I'm after. Let me take a look at some definitions of "open" from thefreedictionary (excluding the definitions under the math section): "Carried on in full view" "Spread out; unfolded" "Accessible to all" "Lacking effective regulation" It seems more natural to me to think of open as something that encompasses a larger scope. E.g. when you spread your arms you have a larger area between your hands, not smaller.
Jun 09 2011
prev sibling next sibling parent reply Ali =?iso-8859-1?q?=C7ehreli?= <acehreli yahoo.com> writes:
On Thu, 09 Jun 2011 16:19:23 +0100, Ben Grabham wrote:

 Hey,
 
 Shouldn't both these programs output the fibonnacci numbers? Only the
 first one does.
 
 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;
 }
 
 
 
 import std.range;
 import std.stdio;
 int main() {
 	auto a = recurrence!("a[n-1] + (n < 2 ? 0 : a[n-2])")(1); int i = 

 	foreach(int n; a) {
 		if(i++ > 20) break;
 		writefln("%d", n);
 	}
 	return 0;
 }

For what it's worth, here is a Fibonacci range. (Translated from D.ershane's "Aralıklar" (Ranges) chapter.) import std.stdio; import std.range; struct FibonacciRange { int first = 0; int second = 1; enum empty = false; property int front() const { return first; } void popFront() { int next = first + second; first = second; second = next; } FibonacciRange save() const { return this; } } void main() { writeln(take(FibonacciRange(), 20)); } Ali
Jun 09 2011
parent Ben Grabham <Evil.Nebster gmail.com> writes:
On 10/06/11 00:10, Ali Çehreli wrote:
 For what it's worth, here is a Fibonacci range. (Translated from
 D.ershane's "Aralıklar" (Ranges) chapter.)

 import std.stdio;
 import std.range;

 struct FibonacciRange
 {
      int first = 0;
      int second = 1;

      enum empty = false;

       property int front() const
      {
          return first;
      }

      void popFront()
      {
          int next = first + second;
          first = second;
          second = next;
      }

      FibonacciRange save() const
      {
          return this;
      }
 }

 void main()
 {
      writeln(take(FibonacciRange(), 20));
 }

 Ali

Have a look at bearophiles answer above. It is a bit shorter. Fibonacci was just an example, I don't actually use it anywhere :P Thanks for another way though, Nebster
Jun 09 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On 2011-06-09 20:35, Ben Grabham wrote:
 On 09/06/11 20:15, Jonathan M Davis wrote:
 The save property of a forward range returns a copy of that range. In
 most cases, since ranges are generally restructs, it just returns the
 range. You use it when you want to save the original range and still be
 able pop elements off.
 
 auto orig = range.save;
 
 //pop off as many elements from range as I want.
 //orig still has all of its elements
 
 The elements aren't copied however, just the range. Regardless, it has
 nothing to do with returning an element from a range, so I don't
 understand your question about returning an index rather than a whole
 object. Ranges don't really use indicies. indexOf will tell you the
 index of a particular element, and you can increment a counter every
 time you pop off an element if you want to know how many elements you've
 consumed, but once an element has been popped off, it's not part of that
 range anymore (though it could be part of a saved range), so that could
 seriously affect by what you mean by index, depending on what you're
 doing.
 
 - Jonathan M Davis

I want to make it so that foreach works but I'm storing an array which when changed, want to keep it like that, even after the foreach, I just want to reset the index to 0 At the moment, I have to do: foreach(i; 0..100) ... lazy._n = 0; foreach(i; 0..100) ... I want to do: foreach(n; lazy) ... foreach(n; lazy) ...

0 .. 100 has nothing to do with ranges. That's a built-in feature of foreach. This would use a range foreach(i; iota(0, 100)) because iota generates one, but 0 .. 100 doesn't. But there's no array involved in foreach(i; 0 .. 100) anyway, and you state that you're storing an array as part of this, so I really don't know what you're trying to do. I'd need to see actual code to be of any help. - Jonathan M Davis
Jun 09 2011
prev sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On 2011-06-11 11:30, Ben Grabham wrote:
 On 10/06/11 05:43, Jonathan M Davis wrote:
 On 2011-06-09 20:35, Ben Grabham wrote:
 On 09/06/11 20:15, Jonathan M Davis wrote:
 The save property of a forward range returns a copy of that range. In
 most cases, since ranges are generally restructs, it just returns the
 range. You use it when you want to save the original range and still be
 able pop elements off.
 
 auto orig = range.save;
 
 //pop off as many elements from range as I want.
 //orig still has all of its elements
 
 The elements aren't copied however, just the range. Regardless, it has
 nothing to do with returning an element from a range, so I don't
 understand your question about returning an index rather than a whole
 object. Ranges don't really use indicies. indexOf will tell you the
 index of a particular element, and you can increment a counter every
 time you pop off an element if you want to know how many elements
 you've consumed, but once an element has been popped off, it's not
 part of that range anymore (though it could be part of a saved range),
 so that could seriously affect by what you mean by index, depending on
 what you're doing.
 
 - Jonathan M Davis

I want to make it so that foreach works but I'm storing an array which when changed, want to keep it like that, even after the foreach, I just want to reset the index to 0 At the moment, I have to do: foreach(i; 0..100) ... lazy._n = 0; foreach(i; 0..100) ... I want to do: foreach(n; lazy) ... foreach(n; lazy) ...

0 .. 100 has nothing to do with ranges. That's a built-in feature of foreach. This would use a range foreach(i; iota(0, 100)) because iota generates one, but 0 .. 100 doesn't. But there's no array involved in foreach(i; 0 .. 100) anyway, and you state that you're storing an array as part of this, so I really don't know what you're trying to do. I'd need to see actual code to be of any help. - Jonathan M Davis

Sorry, didn't really make that clear. Inside the foreach, I'm using popFront and front to get the values and then outside, I set the index (_n) back to 0. What I want to do is "save" the _n value and then restore it at the beginning and end of the foreach respectively. I don't have the code on me atm, but when I get hold of it, I'll post it if you still need it.

Well, if you're using foreach, I wouldn't expect you to be calling popFront and front explicitly. So, I don't know what you're doing there. And you don't really use indices much with ranges, so I'm not sure what you're trying to do with them here. A forward range won't be consumed by a foreach (an input range would, I believe, since it has no way to save it, but most ranges are at least forward ranges). Rather, a copy of it will be consumed. So, iterating over a range, won't consume it, if that's what you're trying to avoid. And if you're iterating over a range explicitly with popFront, then you can save the range with its save property prior to calling popFront. If it's just select values from a range that you're trying to save, then you're likely going to need to either stick them in a new container or save their indices (presumably by using a counter when iterating over the range) so that you can know where in the range they are to grab them up later (though that's not terribly efficient if the range isn't random access). And if that information doesn't help you, I really don't know what to say, because I don't understand what you're trying to do based on what you've said. What you've said makes me wonder if there's something key about ranges that you don't understand or whether there's just miscommunication going on here. So, if you need better advice, you're probably going to have to show me the code. - Jonathan M Davis
Jun 11 2011