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
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 reply "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
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 "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
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
parent reply "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
parent reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
I never understood why it's called "open" interval. What does it 'open'?
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
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 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
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 reply 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
parent reply 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
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
prev sibling next sibling parent reply "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
parent reply 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
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'?


 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.


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 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 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 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 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 = 


0;

 	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