Re: D Recurrences
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
Re: D Recurrences
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
Re: D Recurrences
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
Re: D Recurrences
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
Re: D Recurrences
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
Re: D Recurrences
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
Re: D Recurrences
Andrei Mitrovic wrote: > On 6/9/11, Steven Schveighoffer wrote: >> On Thu, 09 Jun 2011 14:45:49 -0400, Andrej Mitrovic >> 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
Re: D Recurrences
On 6/9/11, Steven Schveighoffer wrote: > On Thu, 09 Jun 2011 14:45:49 -0400, Andrej Mitrovic > 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.
Re: D Recurrences
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 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.
Re: D Recurrences
Timon Gehr wrote: > Steve Schveighoffer wrote: >> On Thu, 09 Jun 2011 14:45:49 -0400, Andrej Mitrovic >> 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
Re: D Recurrences
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
Re: D Recurrences
Steve Schveighoffer wrote: > On Thu, 09 Jun 2011 14:45:49 -0400, Andrej Mitrovic > 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
Re: D Recurrences
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
Re: D Recurrences
On Thu, 09 Jun 2011 14:45:49 -0400, Andrej Mitrovic 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
Re: D Recurrences
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?
Re: D Recurrences
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
Re: D Recurrences
I never understood why it's called "open" interval. What does it 'open'?
Re: D Recurrences
On Thu, 09 Jun 2011 14:02:47 -0400, Ben Grabham
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
Re: D Recurrences
On 09/06/11 18:49, Steven Schveighoffer wrote:
On Thu, 09 Jun 2011 13:31:18 -0400, Ben Grabham
wrote:
On 09/06/11 18:11, Steven Schveighoffer wrote:
On Thu, 09 Jun 2011 13:06:54 -0400, Ben Grabham
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 10 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
Re: D Recurrences
On Thu, 09 Jun 2011 13:31:18 -0400, Ben Grabham
wrote:
On 09/06/11 18:11, Steven Schveighoffer wrote:
On Thu, 09 Jun 2011 13:06:54 -0400, Ben Grabham
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 10 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
Re: D Recurrences
On 09/06/11 18:11, Steven Schveighoffer wrote:
On Thu, 09 Jun 2011 13:06:54 -0400, Ben Grabham
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 10 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
Re: D Recurrences
On Thu, 09 Jun 2011 13:06:54 -0400, Ben Grabham
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
Re: D Recurrences
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
Re: D Recurrences
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
Re: D Recurrences
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
Re: D Recurrences
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
Re: D Recurrences
> 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
Re: D Recurrences
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
Re: D Recurrences
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
Re: D Recurrences
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
Re: D Recurrences
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
Re: D Recurrences
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
Re: D Recurrences
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...
D Recurrences
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;
}
