## digitalmars.D - ch-ch-update: series, closed-form series, and strides

- Andrei Alexandrescu (31/31) Jan 30 2009 I've updated my code and documentation to include series (as in math) in...
- dsimcha (4/35) Jan 30 2009 Is the code to this stuff posted anywhere yet? I'd be interested to rea...
- Andrei Alexandrescu (6/9) Jan 30 2009 Thanks for the interest! Much obliged:
- Jarrett Billingsley (4/15) Jan 30 2009 Shouldn't ClosedFormSeries.next, uh, increment _n? <_<
- Andrei Alexandrescu (3/21) Jan 30 2009 Ouch, fixed. Thanks!
- Andrei Alexandrescu (7/7) Jan 30 2009 Andrei Alexandrescu wrote:
- Bill Baxter (6/14) Jan 30 2009 This sounds interesting! So you'll have diagonal, banded, upper/lower
- Andrei Alexandrescu (34/49) Jan 30 2009 Sparse matrices too. For dense block matrices I'm thinking of a type
- Bill Baxter (9/59) Jan 30 2009 Whoa... excellent. I didn't even dare ask about sparse, or block
- Neal Becker (5/5) Feb 07 2009 One thing that I've found from various c++ vector/matrix libs, is that t...
- Don (3/9) Jan 31 2009 This sounds like the perfect approach. Everything's built around the
- Bill Baxter (8/18) Jan 31 2009 Yes indeed. It's a tried and true approach. I think you'll find a
- bearophile (5/6) Jan 30 2009 I think take(fib, 10) is quite better.
- Andrei Alexandrescu (3/11) Jan 31 2009 SPJ held a gun to my head and said: "take(10, fib)".
- Ary Borenszweig (3/15) Jan 31 2009 Who is SPJ?
- grauzone (5/22) Jan 31 2009 I prefer the other way around.
- Simen Kjaeraas (5/19) Jan 31 2009 Yeah, me too. "Take fib from 10" sounds backwards.
- Brian Palmer (2/7) Jan 31 2009 Yeah, but in Haskell they say "take 10 fib" because of partial function ...
- Sean Kelly (6/10) Jan 31 2009 I like function calls that read like a sentence. Here I'd read take(10,...
- Michel Fortin (6/10) Jan 31 2009 How about fib[0..10]?
- Ary Borenszweig (2/23) Jan 31 2009 That is *SO* awesome!!
- Andrei Alexandrescu (20/44) Jan 31 2009 Thanks! Constant-space factorial is just a line away:
- Ary Borenszweig (18/68) Jan 31 2009 Nice! :-)
- Ary Borenszweig (4/83) Jan 31 2009 Ah... But I can see the problem with delegates. I guess with strings you...
- Christopher Wright (3/6) Jan 31 2009 If it's an alias, it should be inlinable. The frontend doesn't do that,
- Ary Borenszweig (2/10) Jan 31 2009 The compile-time view doesn't show inlining. That happens later, I think...
- Jarrett Billingsley (5/8) Jan 31 2009 Or just steal things from other languages.
- Andrei Alexandrescu (3/16) Jan 31 2009 Today's naked string literals must go!!
- Jarrett Billingsley (3/21) Jan 31 2009 :O
- Andrei Alexandrescu (24/49) Jan 31 2009 Let me see. Say I made the mistake of using "b":
- Don (14/77) Jan 31 2009 In BLADE, what I did was provide an error message as an alternate return...
- Christopher Wright (2/7) Jan 31 2009 Yes, but they don't interact with an IDE.
- Andrei Alexandrescu (3/11) Jan 31 2009 It's the IDE that doesn't yet interact with them.
- Ary Borenszweig (8/20) Jan 31 2009 Hmm... How can the IDE tell that some T in a template, if it's a string,...
- Derek Parnell (7/12) Jan 31 2009 And syntax-highlighting editors just love them ;-) Knowing which strings
- Andrei Alexandrescu (7/17) Jan 31 2009 The language can help here. q{stuff} is a "token string" which
- Derek Parnell (6/7) Jan 31 2009 I was not aware of the q{} syntax. That should work for smart editors.
- Michel Fortin (9/15) Jan 31 2009 Hum, but since it's a string, shouldn't text editors highlight it as if
- Frits van Bommel (10/19) Jan 31 2009 I think it might be a nice idea to syntax-highlight those like regular
- Jason House (2/23) Jan 31 2009 I have never seen an std.algorithm example using q{}. I'd also expect su...
- Sean Kelly (3/33) Feb 03 2009 Awesome :-) I think that proves the efficacy of the approach all by its...
- Denis Koroskin (3/35) Feb 03 2009 I wonder how efficent it is? Does it store last few sequence elements or...
- Steven Schveighoffer (14/54) Feb 03 2009 Factorial series is defined in terms of the last term, so you only need ...
- Andrei Alexandrescu (4/17) Feb 03 2009 It's entirely possible, and I think it's a good idea. I'll look into
- Denis Koroskin (8/71) Feb 03 2009 Of course, but does it *really* discard old values? That's what I doubt.
- Steven Schveighoffer (7/68) Feb 03 2009 I don't think such a series is definable with Andrei's template. I thin...
- Joel C. Salomon (2/8) Feb 03 2009 Time-invariant, or shift-invariant.
- Andrei Alexandrescu (17/27) Feb 03 2009 Great! I didn't know (haven't learned college-level Math in English;
- Bill Baxter (8/35) Feb 03 2009 My digital signal processing textbook refers to "discrete-time
- Derek Parnell (9/11) Feb 03 2009 I'm not a mathemetician, but to me elements in a series cannot necessari...
- Steven Schveighoffer (5/11) Feb 03 2009 http://en.wikipedia.org/wiki/Recurrence_relation
- Lars Kyllingstad (20/39) Feb 04 2009 I believe the mathematically correct terms would be RecursiveSequence
- Joel C. Salomon (10/18) Feb 04 2009 These are sequences. (Or, in an EE context, “signals”, but let’s n...
- Andrei Alexandrescu (20/29) Feb 03 2009 Very simple (assuming a[0] = 1):
- Andrei Alexandrescu (21/65) Feb 03 2009 I wouldn't use it either, in fact I have a dim view of all books,
- Don (26/30) Jan 31 2009 I've been thinking a little about the concepts involved in range

I've updated my code and documentation to include series (as in math) in the form of infinite ranges. Also series in closed form (given n can compute the nth value without iterating) are supported as random-access ranges. Also Stride is provided. The Matrix container (speaking of scientific computing with D!) will support various representational choices, most importantly the ones endorsed by high-performance libraries. For Matrix, Stride is an important component as I'm sure anyone who's ever written a matrix knows. http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html Back to series. Finally my dream has come true: I can define a decent Fibonacci series clearly and efficiently in one line of code. No more idiotic recursive function that takes exponential time to finish! auto fib = series!("a[n-1] + a[n]")(1, 1); // write 10 Fibonacci numbers foreach (e; take(10, fib)) writeln(e); This means: * The state of the series consists of two values, which start as a[0] = 1 and a[1] = 1. This state will be stored inside the returned object in-situ (no dynamic allocation). * The means to compute the n+1'th element given the n'th and the n-1'th is a[n-1] + a[n]. The series object takes care of everything - keeping score, rotating buffers, advancing state, you name it. Walter sent me examples of famous series (e.g. Taylor, approximations of pi, etc.) that I want to put in as examples. I can't wait the next release so I can share this all with you guys! Feedback and suggestions welcome! (I know, I need to add the iota range presto!) Andrei

Jan 30 2009

== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s articleI've updated my code and documentation to include series (as in math) in the form of infinite ranges. Also series in closed form (given n can compute the nth value without iterating) are supported as random-access ranges. Also Stride is provided. The Matrix container (speaking of scientific computing with D!) will support various representational choices, most importantly the ones endorsed by high-performance libraries. For Matrix, Stride is an important component as I'm sure anyone who's ever written a matrix knows. http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html Back to series. Finally my dream has come true: I can define a decent Fibonacci series clearly and efficiently in one line of code. No more idiotic recursive function that takes exponential time to finish! auto fib = series!("a[n-1] + a[n]")(1, 1); // write 10 Fibonacci numbers foreach (e; take(10, fib)) writeln(e); This means: * The state of the series consists of two values, which start as a[0] = 1 and a[1] = 1. This state will be stored inside the returned object in-situ (no dynamic allocation). * The means to compute the n+1'th element given the n'th and the n-1'th is a[n-1] + a[n]. The series object takes care of everything - keeping score, rotating buffers, advancing state, you name it. Walter sent me examples of famous series (e.g. Taylor, approximations of pi, etc.) that I want to put in as examples. I can't wait the next release so I can share this all with you guys! Feedback and suggestions welcome! (I know, I need to add the iota range presto!) AndreiIs the code to this stuff posted anywhere yet? I'd be interested to read some of it. I actually learned a decent amount of template idioms by reading the old-school std.algorithm, so I'm curious how some of this stuff is implemented.

Jan 30 2009

dsimcha wrote:Is the code to this stuff posted anywhere yet? I'd be interested to read some of it. I actually learned a decent amount of template idioms by reading the old-school std.algorithm, so I'm curious how some of this stuff is implemented.Thanks for the interest! Much obliged: http://ssli.ee.washington.edu/~aalexand/d/algorithm.d http://ssli.ee.washington.edu/~aalexand/d/range.d http://ssli.ee.washington.edu/~aalexand/d/functional.d Andrei

Jan 30 2009

On Fri, Jan 30, 2009 at 10:48 PM, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:dsimcha wrote:Shouldn't ClosedFormSeries.next, uh, increment _n? <_< But very, very cool.Is the code to this stuff posted anywhere yet? I'd be interested to read some of it. I actually learned a decent amount of template idioms by reading the old-school std.algorithm, so I'm curious how some of this stuff is implemented.Thanks for the interest! Much obliged: http://ssli.ee.washington.edu/~aalexand/d/algorithm.d http://ssli.ee.washington.edu/~aalexand/d/range.d http://ssli.ee.washington.edu/~aalexand/d/functional.d

Jan 30 2009

Jarrett Billingsley wrote:On Fri, Jan 30, 2009 at 10:48 PM, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:Ouch, fixed. Thanks! Andreidsimcha wrote:Shouldn't ClosedFormSeries.next, uh, increment _n? <_< But very, very cool.Is the code to this stuff posted anywhere yet? I'd be interested to read some of it. I actually learned a decent amount of template idioms by reading the old-school std.algorithm, so I'm curious how some of this stuff is implemented.Thanks for the interest! Much obliged: http://ssli.ee.washington.edu/~aalexand/d/algorithm.d http://ssli.ee.washington.edu/~aalexand/d/range.d http://ssli.ee.washington.edu/~aalexand/d/functional.d

Jan 30 2009

Andrei Alexandrescu wrote: [snip] Oh, and I forgot: an embryonic Heap container is to be found in std.algorithm. Haven't figured how best to define heap growth yet. This is because it would be based on e.g. the controversial operator ~= for arrays. Andrei

Jan 30 2009

On Sat, Jan 31, 2009 at 12:12 PM, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:I've updated my code and documentation to include series (as in math) in the form of infinite ranges. Also series in closed form (given n can compute the nth value without iterating) are supported as random-access ranges. Also Stride is provided. The Matrix container (speaking of scientific computing with D!) will support various representational choices, most importantly the ones endorsed by high-performance libraries. For Matrix, Stride is an important component as I'm sure anyone who's ever written a matrix knows.This sounds interesting! So you'll have diagonal, banded, upper/lower triangular, symmetric, strided and dense matrices? How about 2D slices? --bb

Jan 30 2009

Bill Baxter wrote:On Sat, Jan 31, 2009 at 12:12 PM, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:Sparse matrices too. For dense block matrices I'm thinking of a type like this: alias BlockMatrix!(float, 3, [0, 2, 1]) M3; This defines a block rectangular matrix with three dimensions laid out in the order specified: In this case, M3 is laid out as a collection of column-order submatrices of 2 dimensions. (I deliberately chose a slightly odd example.) The last parameter of BlockMatrix can be any permutation of 0, 1, and 2, thus dictating how the dimensions are laid out. For an obvious example, here's a Fortran-compatible block matrix with column-major layout: alias BlockMatrix!(double, 2, [1, 0]) FortranMatrix; So it's pretty easy to choose any layout for any matrix with any number of dimensions. This matrix defines ranges that crawl it, called hyperplanes. There is a "natural" hyperplane that doesn't need any stride, and that's the cut along the dimension that varies slowest. That cut is the most efficient because it really has the layout of a (littler) BlockMatrix itself. Continuing on the M3 example, a "row" in that matrix has type: alias BlockMatrix!(float, 2, [1, 0]) M3Row; which is obtained by chopping the first element in the array [0, 2, 1] into [2, 1], and then decrementing what's left into [1, 2]. So if you have: M3 m; auto subM = m[3]; you get that smaller BlockMatrix with all amenities its larger cousin offered. But if you want a cut along a different dimension, a strided range will be returned. Jagged, banded, diagonal, fixed-size, and sparse layouts come naturally and will be hopefully supported in a mixable-and-matchable form (e.g. I want a block matrix of 3x3 matrices). I want to focus on storage for now, put it in the standard library, to then allow great scientific programmers like you guys to use those storages as a common data format on top of which cool algorithms can be implemented. AndreiI've updated my code and documentation to include series (as in math) in the form of infinite ranges. Also series in closed form (given n can compute the nth value without iterating) are supported as random-access ranges. Also Stride is provided. The Matrix container (speaking of scientific computing with D!) will support various representational choices, most importantly the ones endorsed by high-performance libraries. For Matrix, Stride is an important component as I'm sure anyone who's ever written a matrix knows.This sounds interesting! So you'll have diagonal, banded, upper/lower triangular, symmetric, strided and dense matrices? How about 2D slices?

Jan 30 2009

On Sat, Jan 31, 2009 at 1:40 PM, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:Bill Baxter wrote:Whoa... excellent. I didn't even dare ask about sparse, or block sparse, or n-dimensional arrays.On Sat, Jan 31, 2009 at 12:12 PM, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:Sparse matrices too. For dense block matrices I'm thinking of a type like this:I've updated my code and documentation to include series (as in math) in the form of infinite ranges. Also series in closed form (given n can compute the nth value without iterating) are supported as random-access ranges. Also Stride is provided. The Matrix container (speaking of scientific computing with D!) will support various representational choices, most importantly the ones endorsed by high-performance libraries. For Matrix, Stride is an important component as I'm sure anyone who's ever written a matrix knows.This sounds interesting! So you'll have diagonal, banded, upper/lower triangular, symmetric, strided and dense matrices? How about 2D slices?alias BlockMatrix!(float, 3, [0, 2, 1]) M3; This defines a block rectangular matrix with three dimensions laid out in the order specified: In this case, M3 is laid out as a collection of column-order submatrices of 2 dimensions. (I deliberately chose a slightly odd example.) The last parameter of BlockMatrix can be any permutation of 0, 1, and 2, thus dictating how the dimensions are laid out. For an obvious example, here's a Fortran-compatible block matrix with column-major layout: alias BlockMatrix!(double, 2, [1, 0]) FortranMatrix;Nice. Maybe you can have some predefined symbols for Fortran and C layouts too, so users don't have to think about it.So it's pretty easy to choose any layout for any matrix with any number of dimensions. This matrix defines ranges that crawl it, called hyperplanes. There is a "natural" hyperplane that doesn't need any stride, and that's the cut along the dimension that varies slowest. That cut is the most efficient because it really has the layout of a (littler) BlockMatrix itself. Continuing on the M3 example, a "row" in that matrix has type: alias BlockMatrix!(float, 2, [1, 0]) M3Row; which is obtained by chopping the first element in the array [0, 2, 1] into [2, 1], and then decrementing what's left into [1, 2]. So if you have: M3 m; auto subM = m[3]; you get that smaller BlockMatrix with all amenities its larger cousin offered. But if you want a cut along a different dimension, a strided range will be returned. Jagged, banded, diagonal, fixed-size, and sparse layouts come naturally and will be hopefully supported in a mixable-and-matchable form (e.g. I want a block matrix of 3x3 matrices). I want to focus on storage for now, put it in the standard library, to then allow great scientific programmers like you guys to use those storages as a common data format on top of which cool algorithms can be implemented.Excellent plan. This sounds like a great rallying point for numerics in D2. But get those ranges done first! --bb

Jan 30 2009

One thing that I've found from various c++ vector/matrix libs, is that the most useful have flexible storage backends. In other words, all of them can allocate their own storage that they 'own', but the most useful can also wrap a matrix 'view' around existing storage. This allows interworking with other libraries.

Feb 07 2009

Andrei Alexandrescu wrote:Jagged, banded, diagonal, fixed-size, and sparse layouts come naturally and will be hopefully supported in a mixable-and-matchable form (e.g. I want a block matrix of 3x3 matrices). I want to focus on storage for now, put it in the standard library, to then allow great scientific programmers like you guys to use those storages as a common data format on top of which cool algorithms can be implemented.This sounds like the perfect approach. Everything's built around the storage format.

Jan 31 2009

On Sun, Feb 1, 2009 at 3:30 AM, Don <nospam nospam.com> wrote:Andrei Alexandrescu wrote:Yes indeed. It's a tried and true approach. I think you'll find a similar approach in the likes of the Matrix Template Library, or FLENS. But I think those projects, particularly MTL, hit a wall because C++ meta-programming is just such a mess. I'm very excited to see what can be done with the full arsenal of D2 metaprogramming at one's disposal. --bbJagged, banded, diagonal, fixed-size, and sparse layouts come naturally and will be hopefully supported in a mixable-and-matchable form (e.g. I want a block matrix of 3x3 matrices). I want to focus on storage for now, put it in the standard library, to then allow great scientific programmers like you guys to use those storages as a common data format on top of which cool algorithms can be implemented.This sounds like the perfect approach. Everything's built around the storage format.

Jan 31 2009

Andrei Alexandrescu:foreach (e; take(10, fib)) writeln(e);I think take(fib, 10) is quite better. I presume the API of those things will need about a year of usage to become refined. Bye, bearophile

Jan 30 2009

bearophile wrote:Andrei Alexandrescu:SPJ held a gun to my head and said: "take(10, fib)". Andreiforeach (e; take(10, fib)) writeln(e);I think take(fib, 10) is quite better. I presume the API of those things will need about a year of usage to become refined. Bye, bearophile

Jan 31 2009

Andrei Alexandrescu escribi:bearophile wrote:Who is SPJ? I find "take(10, fib)" more readable: take 10 from fib. Same order.Andrei Alexandrescu:SPJ held a gun to my head and said: "take(10, fib)".foreach (e; take(10, fib)) writeln(e);I think take(fib, 10) is quite better. I presume the API of those things will need about a year of usage to become refined. Bye, bearophile

Jan 31 2009

Ary Borenszweig wrote:Andrei Alexandrescu escribi:I prefer the other way around. There's another argument for take(fib, 10) that isn't just about taste: if fib was an array, you could write fib.take(10). Weren't there discussions to allow a.F(b...) for F(a,b...) in general?bearophile wrote:Who is SPJ? I find "take(10, fib)" more readable: take 10 from fib. Same order.foreach (e; take(10, fib)) writeln(e);I think take(fib, 10) is quite better. I presume the API of those things will need about a year of usage to become refined. Bye, bearophile

Jan 31 2009

On Sat, 31 Jan 2009 14:35:50 +0100, Ary Borenszweig <ary esperanto.org.ar> wrote:Andrei Alexandrescu escribió:http://en.wikipedia.org/wiki/Simon_Peyton_Jonesbearophile wrote:Who is SPJ?foreach (e; take(10, fib)) writeln(e);I think take(fib, 10) is quite better. I presume the API of those things will need about a year of usage to become refined. Bye, bearophileI find "take(10, fib)" more readable: take 10 from fib. Same order.Yeah, me too. "Take fib from 10" sounds backwards. -- Simen

Jan 31 2009

Andrei Alexandrescu Wrote:bearophile wrote:Yeah, but in Haskell they say "take 10 fib" because of partial function application, it's important to decide which parameter is most likely to be useful in the last positions even if it doesn't read as well. That doesn't apply in D, unless you and Walter have been working even more magic behind the scenes that you haven't talked about yet. ;)Andrei Alexandrescu:SPJ held a gun to my head and said: "take(10, fib)". Andrei

Jan 31 2009

bearophile wrote:Andrei Alexandrescu:I like function calls that read like a sentence. Here I'd read take(10, fib) as "take 10 from fib". The only advantage of reversing the arguments is that it might decompose well into the property syntax: fib.take(10). Seanforeach (e; take(10, fib)) writeln(e);I think take(fib, 10) is quite better.

Jan 31 2009

On 2009-01-31 15:17:40 -0500, Sean Kelly <sean invisibleduck.org> said:I like function calls that read like a sentence. Here I'd read take(10, fib) as "take 10 from fib". The only advantage of reversing the arguments is that it might decompose well into the property syntax: fib.take(10).How about fib[0..10]? -- Michel Fortin michel.fortin michelf.com http://michelf.com/

Jan 31 2009

Andrei Alexandrescu escribi:I've updated my code and documentation to include series (as in math) in the form of infinite ranges. Also series in closed form (given n can compute the nth value without iterating) are supported as random-access ranges. Also Stride is provided. The Matrix container (speaking of scientific computing with D!) will support various representational choices, most importantly the ones endorsed by high-performance libraries. For Matrix, Stride is an important component as I'm sure anyone who's ever written a matrix knows. http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html Back to series. Finally my dream has come true: I can define a decent Fibonacci series clearly and efficiently in one line of code. No more idiotic recursive function that takes exponential time to finish! auto fib = series!("a[n-1] + a[n]")(1, 1); // write 10 Fibonacci numbers foreach (e; take(10, fib)) writeln(e);That is *SO* awesome!!

Jan 31 2009

Ary Borenszweig wrote:Andrei Alexandrescu escribi:Thanks! Constant-space factorial is just a line away: auto fact = series!("a[n] * (n + 1)")(1); foreach (e; take(10, fact)) writeln(e); writes: 1 1 2 6 24 120 720 5040 40320 362880 And this lousy series approximating pi: auto piapprox = series!("a[n] + (n & 1 ? 4. : -4.) / (2 * n + 3)")(4.); foreach (e; take(200, piapprox)) writeln(e); Very slowly convergent. :o) AndreiI've updated my code and documentation to include series (as in math) in the form of infinite ranges. Also series in closed form (given n can compute the nth value without iterating) are supported as random-access ranges. Also Stride is provided. The Matrix container (speaking of scientific computing with D!) will support various representational choices, most importantly the ones endorsed by high-performance libraries. For Matrix, Stride is an important component as I'm sure anyone who's ever written a matrix knows. http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html Back to series. Finally my dream has come true: I can define a decent Fibonacci series clearly and efficiently in one line of code. No more idiotic recursive function that takes exponential time to finish! auto fib = series!("a[n-1] + a[n]")(1, 1); // write 10 Fibonacci numbers foreach (e; take(10, fib)) writeln(e);That is *SO* awesome!!

Jan 31 2009

Andrei Alexandrescu escribi:Ary Borenszweig wrote:Nice! :-) I showed the Fibonacci example to a friend of mine and he said "that string stuff scares me a little". The same happens to me. What kind of error do you get if you mistype something in that string expression? Can you pass a delegate instead of a string? Something like: auto fib = series!((Range a, int n) { return a[n-1] + a[n]; })(1, 1); That seems much safe and will probably give a reasonable error if you mistype something. I know, it's longer than the previous one. But it would be nice if D had the following rule (or something similar to it): "if a delegate doesn't return, the last statement is converted to a return" (and you can ommit the semicolon). So now you can write: auto fib = series!((Range a, int n) { a[n-1] + a[n] })(1, 1); And if you could just ommit the types in the delegate... auto fib = series!((a, n) { a[n-1] + a[n] })(1, 1); Still a little longer than the original, but you get all the benefits of not using a string.Andrei Alexandrescu escribi:Thanks! Constant-space factorial is just a line away: auto fact = series!("a[n] * (n + 1)")(1); foreach (e; take(10, fact)) writeln(e); writes: 1 1 2 6 24 120 720 5040 40320 362880 And this lousy series approximating pi: auto piapprox = series!("a[n] + (n & 1 ? 4. : -4.) / (2 * n + 3)")(4.); foreach (e; take(200, piapprox)) writeln(e); Very slowly convergent. :o)I've updated my code and documentation to include series (as in math) in the form of infinite ranges. Also series in closed form (given n can compute the nth value without iterating) are supported as random-access ranges. Also Stride is provided. The Matrix container (speaking of scientific computing with D!) will support various representational choices, most importantly the ones endorsed by high-performance libraries. For Matrix, Stride is an important component as I'm sure anyone who's ever written a matrix knows. http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html Back to series. Finally my dream has come true: I can define a decent Fibonacci series clearly and efficiently in one line of code. No more idiotic recursive function that takes exponential time to finish! auto fib = series!("a[n-1] + a[n]")(1, 1); // write 10 Fibonacci numbers foreach (e; take(10, fib)) writeln(e);That is *SO* awesome!!

Jan 31 2009

Ary Borenszweig escribi:Andrei Alexandrescu escribi:Ah... But I can see the problem with delegates. I guess with strings you just mix them in a bigger expression and it's like inlining the call. With delegates you can't do that. So there's also a performance tradeoff...Ary Borenszweig wrote:Nice! :-) I showed the Fibonacci example to a friend of mine and he said "that string stuff scares me a little". The same happens to me. What kind of error do you get if you mistype something in that string expression? Can you pass a delegate instead of a string? Something like: auto fib = series!((Range a, int n) { return a[n-1] + a[n]; })(1, 1); That seems much safe and will probably give a reasonable error if you mistype something. I know, it's longer than the previous one. But it would be nice if D had the following rule (or something similar to it): "if a delegate doesn't return, the last statement is converted to a return" (and you can ommit the semicolon). So now you can write: auto fib = series!((Range a, int n) { a[n-1] + a[n] })(1, 1); And if you could just ommit the types in the delegate... auto fib = series!((a, n) { a[n-1] + a[n] })(1, 1); Still a little longer than the original, but you get all the benefits of not using a string.

Jan 31 2009

Ary Borenszweig wrote:Ah... But I can see the problem with delegates. I guess with strings you just mix them in a bigger expression and it's like inlining the call. With delegates you can't do that. So there's also a performance tradeoff...If it's an alias, it should be inlinable. The frontend doesn't do that, though, apparently (according to your compile time viewer).

Jan 31 2009

Christopher Wright escribi:Ary Borenszweig wrote:The compile-time view doesn't show inlining. That happens later, I think.Ah... But I can see the problem with delegates. I guess with strings you just mix them in a bigger expression and it's like inlining the call. With delegates you can't do that. So there's also a performance tradeoff...If it's an alias, it should be inlinable. The frontend doesn't do that, though, apparently (according to your compile time viewer).

Jan 31 2009

On Sat, Jan 31, 2009 at 9:34 AM, Ary Borenszweig <ary esperanto.org.ar> wrote:auto fib = series!((Range a, int n) { a[n-1] + a[n] })(1, 1); And if you could just ommit the types in the delegate... auto fib = series!((a, n) { a[n-1] + a[n] })(1, 1);Or just steal things from other languages. auto fib = series!(\a, n -> a[n - 1] + a[n])(1, 1); Haskell function literals, wee! Of course, it means actually using \ for something useful, unlike how it's used now.

Jan 31 2009

Jarrett Billingsley wrote:On Sat, Jan 31, 2009 at 9:34 AM, Ary Borenszweig <ary esperanto.org.ar> wrote:Today's naked string literals must go!! Andreiauto fib = series!((Range a, int n) { a[n-1] + a[n] })(1, 1); And if you could just ommit the types in the delegate... auto fib = series!((a, n) { a[n-1] + a[n] })(1, 1);Or just steal things from other languages. auto fib = series!(\a, n -> a[n - 1] + a[n])(1, 1); Haskell function literals, wee! Of course, it means actually using \ for something useful, unlike how it's used now.

Jan 31 2009

On Sat, Jan 31, 2009 at 10:23 AM, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:Jarrett Billingsley wrote::OOn Sat, Jan 31, 2009 at 9:34 AM, Ary Borenszweig <ary esperanto.org.ar> wrote:Today's naked string literals must go!!auto fib = series!((Range a, int n) { a[n-1] + a[n] })(1, 1); And if you could just ommit the types in the delegate... auto fib = series!((a, n) { a[n-1] + a[n] })(1, 1);Or just steal things from other languages. auto fib = series!(\a, n -> a[n - 1] + a[n])(1, 1); Haskell function literals, wee! Of course, it means actually using \ for something useful, unlike how it's used now.

Jan 31 2009

Ary Borenszweig wrote:Andrei Alexandrescu escribi: Nice! :-) I showed the Fibonacci example to a friend of mine and he said "that string stuff scares me a little". The same happens to me. What kind of error do you get if you mistype something in that string expression?Let me see. Say I made the mistake of using "b": auto fib = series!("a[n-1] + b[n]")(1, 1); std/functional.d(185): static assert "Bad binary function: a[n] + b[n-1] for types Cycle!(int[]) and uint. You need to use an expression using symbols a and n." Heck, that's even better than compiler's own error messages. Unfortunately, the line where the actual instantiation was invoked is not shown. I think that's entirely doable though. Say I forget to close a bracket: auto fib = series!("a[n] + a[n-1")(1, 1); The compiler penalizes that by never finishing compiling. That's a bug.Can you pass a delegate instead of a string? Something like: auto fib = series!((Range a, int n) { return a[n-1] + a[n]; })(1, 1);Not right now because delegate literals can't be templates. But I talked about that with Walter and he'll make it work.That seems much safe and will probably give a reasonable error if you mistype something. I know, it's longer than the previous one. But it would be nice if D had the following rule (or something similar to it): "if a delegate doesn't return, the last statement is converted to a return" (and you can ommit the semicolon). So now you can write: auto fib = series!((Range a, int n) { a[n-1] + a[n] })(1, 1); And if you could just ommit the types in the delegate... auto fib = series!((a, n) { a[n-1] + a[n] })(1, 1); Still a little longer than the original, but you get all the benefits of not using a string.Incidentally, I was talking to Walter about the shorter delegate form and he convinced me that it's too risky to have semantics depend on only one semicolon. But omitting the type names from a literal delegate is something we're mulling over. The truth is, the reasons against using strings for short functions are shrinking. I mean, you don't want to not use strings just to not use strings, right? I hope I convinced you that strings are unbeatable for short functions that don't need access to local state, their efficiency is exemplary, and their error messages are not half bad. Andrei

Jan 31 2009

Andrei Alexandrescu wrote:Ary Borenszweig wrote:In BLADE, what I did was provide an error message as an alternate return value from the inner templates. This is then passed down through the higher-level functions. At the user level, instead of mixing in code to invoke the function, it mixes in a static assert(0, errormsg) instead. Then there is an error ONLY on the line of user code. You can only achieve these perfect error messages if you have a mixin statement in the user code, unfortunately. Of course, using return values to indicate errors is so 1970's. Compile-time assert exception catching would be so much better... But a simple change to the static assert handling would get us most of the way there.Andrei Alexandrescu escribi: Nice! :-) I showed the Fibonacci example to a friend of mine and he said "that string stuff scares me a little". The same happens to me. What kind of error do you get if you mistype something in that string expression?Let me see. Say I made the mistake of using "b": auto fib = series!("a[n-1] + b[n]")(1, 1); std/functional.d(185): static assert "Bad binary function: a[n] + b[n-1] for types Cycle!(int[]) and uint. You need to use an expression using symbols a and n." Heck, that's even better than compiler's own error messages. Unfortunately, the line where the actual instantiation was invoked is not shown. I think that's entirely doable though.Say I forget to close a bracket: auto fib = series!("a[n] + a[n-1")(1, 1); The compiler penalizes that by never finishing compiling. That's a bug.There's a few cases in bugzilla about mismatched brackets. Some of them cause segfaults.Can you pass a delegate instead of a string? Something like: auto fib = series!((Range a, int n) { return a[n-1] + a[n]; })(1, 1);Not right now because delegate literals can't be templates. But I talked about that with Walter and he'll make it work.That seems much safe and will probably give a reasonable error if you mistype something. I know, it's longer than the previous one. But it would be nice if D had the following rule (or something similar to it): "if a delegate doesn't return, the last statement is converted to a return" (and you can ommit the semicolon). So now you can write: auto fib = series!((Range a, int n) { a[n-1] + a[n] })(1, 1); And if you could just ommit the types in the delegate... auto fib = series!((a, n) { a[n-1] + a[n] })(1, 1); Still a little longer than the original, but you get all the benefits of not using a string.Incidentally, I was talking to Walter about the shorter delegate form and he convinced me that it's too risky to have semantics depend on only one semicolon. But omitting the type names from a literal delegate is something we're mulling over. The truth is, the reasons against using strings for short functions are shrinking. I mean, you don't want to not use strings just to not use strings, right? I hope I convinced you that strings are unbeatable for short functions that don't need access to local state, their efficiency is exemplary, and their error messages are not half bad. Andrei

Jan 31 2009

Andrei Alexandrescu wrote:The truth is, the reasons against using strings for short functions are shrinking. I mean, you don't want to not use strings just to not use strings, right? I hope I convinced you that strings are unbeatable for short functions that don't need access to local state, their efficiency is exemplary, and their error messages are not half bad.Yes, but they don't interact with an IDE.

Jan 31 2009

Christopher Wright wrote:Andrei Alexandrescu wrote:It's the IDE that doesn't yet interact with them. AndreiThe truth is, the reasons against using strings for short functions are shrinking. I mean, you don't want to not use strings just to not use strings, right? I hope I convinced you that strings are unbeatable for short functions that don't need access to local state, their efficiency is exemplary, and their error messages are not half bad.Yes, but they don't interact with an IDE.

Jan 31 2009

Andrei Alexandrescu escribi:Christopher Wright wrote:Hmm... How can the IDE tell that some T in a template, if it's a string, must have "a" and "n" as their parameters in expressions, their type, etc.? Anyway, I like the usage of strings if it's short and doesn't local state, you've convinced me. :-) As for the errors, the compiler should hold a stack of template instances invocations (same for string mixins), and add those in any error message report. I'll try to do that in Descent to see if it's enough.Andrei Alexandrescu wrote:It's the IDE that doesn't yet interact with them.The truth is, the reasons against using strings for short functions are shrinking. I mean, you don't want to not use strings just to not use strings, right? I hope I convinced you that strings are unbeatable for short functions that don't need access to local state, their efficiency is exemplary, and their error messages are not half bad.Yes, but they don't interact with an IDE.

Jan 31 2009

On Sat, 31 Jan 2009 07:22:17 -0800, Andrei Alexandrescu wrote:

Jan 31 2009

Derek Parnell wrote:On Sat, 31 Jan 2009 07:22:17 -0800, Andrei Alexandrescu wrote:The language can help here. q{stuff} is a "token string" which presumably contains code, whereas the other strings presumably don't. In my editor, q{code} comes off as highlighted. So I think in the future it's a good bet for both programmers and editors to consider q{} quotes as containing code. Andrei

Jan 31 2009

On Sat, 31 Jan 2009 16:26:08 -0800, Andrei Alexandrescu wrote:The language can help here. q{stuff} is a "token string"I was not aware of the q{} syntax. That should work for smart editors. -- Derek Parnell Melbourne, Australia skype: derek.j.parnell

Jan 31 2009

On 2009-01-31 19:26:08 -0500, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> said:The language can help here. q{stuff} is a "token string" which presumably contains code, whereas the other strings presumably don't. In my editor, q{code} comes off as highlighted. So I think in the future it's a good bet for both programmers and editors to consider q{} quotes as containing code.Hum, but since it's a string, shouldn't text editors highlight it as if it was a string? I was going to do that in D for Xcode at some point... perhaps I shouldn't. -- Michel Fortin michel.fortin michelf.com http://michelf.com/

Jan 31 2009

Michel Fortin wrote:On 2009-01-31 19:26:08 -0500, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> said:I think it might be a nice idea to syntax-highlight those like regular code, but with a different background color. For instance white background for regular code, light yellow for q{}, and successively darker shades for nested q{q{q{}}} (up to some limit). You'd have to make sure it stays readable though, so the background color should be a color that has sufficient contrast with foreground colors used for the code (e.g. don't pick the color used for regular strings(!) or keywords). Just a thought...So I think in the future it's a good bet for both programmers and editors to consider q{} quotes as containing code.Hum, but since it's a string, shouldn't text editors highlight it as if it was a string? I was going to do that in D for Xcode at some point... perhaps I shouldn't.

Jan 31 2009

Andrei Alexandrescu Wrote:Derek Parnell wrote:I have never seen an std.algorithm example using q{}. I'd also expect such an example to lose some of its apeal.On Sat, 31 Jan 2009 07:22:17 -0800, Andrei Alexandrescu wrote:The language can help here. q{stuff} is a "token string" which presumably contains code, whereas the other strings presumably don't. In my editor, q{code} comes off as highlighted. So I think in the future it's a good bet for both programmers and editors to consider q{} quotes as containing code. Andrei

Jan 31 2009

Andrei Alexandrescu wrote:Ary Borenszweig wrote:Awesome :-) I think that proves the efficacy of the approach all by itself. Sean

Feb 03 2009

On Tue, 03 Feb 2009 21:25:21 +0300, Sean Kelly <sean invisibleduck.org> wrote:Andrei Alexandrescu wrote:I wonder how efficent it is? Does it store last few sequence elements or re-compute then again and again? I wouldn't use it in the latter case.Ary Borenszweig wrote:Awesome :-) I think that proves the efficacy of the approach all by itself. SeanAndrei Alexandrescu escribió:Thanks! Constant-space factorial is just a line away: auto fact = series!("a[n] * (n + 1)")(1); foreach (e; take(10, fact)) writeln(e);

Feb 03 2009

"Denis Koroskin" wroteOn Tue, 03 Feb 2009 21:25:21 +0300, Sean Kelly <sean invisibleduck.org> wrote:Factorial series is defined in terms of the last term, so you only need to remember the last term. i.e. 5! = 4! * 5. So constant space, constant time per iteration. One thing I was confused about, you are defining in the function how to calculate a[n+1]? I find it more intuitive to define what a[n] is. For example, auto fib = series!("a[n - 2] + a[n - 1]")(1, 1); // reads a[n] = a[n-2] + a[n-1] It's even less confusing in the factorial example (IMO): auto fact = series!("a[n - 1] * n")(1); Of course, I don't know how the template-fu works, so I'm not sure if it's possible ;) -SteveAndrei Alexandrescu wrote:I wonder how efficent it is? Does it store last few sequence elements or re-compute then again and again? I wouldn't use it in the latter case.Ary Borenszweig wrote:Awesome :-) I think that proves the efficacy of the approach all by itself. Sean

Feb 03 2009

Steven Schveighoffer wrote:One thing I was confused about, you are defining in the function how to calculate a[n+1]? I find it more intuitive to define what a[n] is. For example, auto fib = series!("a[n - 2] + a[n - 1]")(1, 1); // reads a[n] = a[n-2] + a[n-1] It's even less confusing in the factorial example (IMO): auto fact = series!("a[n - 1] * n")(1); Of course, I don't know how the template-fu works, so I'm not sure if it's possible ;)It's entirely possible, and I think it's a good idea. I'll look into changing the code. Thanks! Andrei

Feb 03 2009

On Tue, 03 Feb 2009 22:43:06 +0300, Steven Schveighoffer <schveiguy yahoo.com> wrote:"Denis Koroskin" wroteOf course, but does it *really* discard old values? That's what I doubt. Ok, Factorial/Fibonacci is easy. How would you implement, say, the following sequence: a[n] = a[0] + a[n / 8]; // ? Now it is log(n) to compute from scratch but you should store O(n) elements to make it constant time. I mean, the algorithm ought to have very good heuristics. And sometimes it is better to re-compute elements instead of caching them.On Tue, 03 Feb 2009 21:25:21 +0300, Sean Kelly <sean invisibleduck.org> wrote:Factorial series is defined in terms of the last term, so you only need to remember the last term. i.e. 5! = 4! * 5. So constant space, constant time per iteration.Andrei Alexandrescu wrote:I wonder how efficent it is? Does it store last few sequence elements or re-compute then again and again? I wouldn't use it in the latter case.Ary Borenszweig wrote:Awesome :-) I think that proves the efficacy of the approach all by itself. SeanAndrei Alexandrescu escribió:Thanks! Constant-space factorial is just a line away: auto fact = series!("a[n] * (n + 1)")(1); foreach (e; take(10, fact)) writeln(e);One thing I was confused about, you are defining in the function how to calculate a[n+1]? I find it more intuitive to define what a[n] is. For example, auto fib = series!("a[n - 2] + a[n - 1]")(1, 1); // reads a[n] = a[n-2] + a[n-1] It's even less confusing in the factorial example (IMO): auto fact = series!("a[n - 1] * n")(1); Of course, I don't know how the template-fu works, so I'm not sure if it's possible ;) -SteveI agree.

Feb 03 2009

"Denis Koroskin" wroteOn Tue, 03 Feb 2009 22:43:06 +0300, Steven Schveighoffer <schveiguy yahoo.com> wrote:I don't think such a series is definable with Andrei's template. I think his series template is only usable in situations where computing a[n] depends only on n and the elements a[n-X]..a[n-1], where X is a constant. I'm not really a mathemetician, so I don't know the technical term for the differences, I'm sure there is one. -Steve"Denis Koroskin" wroteOf course, but does it *really* discard old values? That's what I doubt. Ok, Factorial/Fibonacci is easy. How would you implement, say, the following sequence: a[n] = a[0] + a[n / 8]; // ?On Tue, 03 Feb 2009 21:25:21 +0300, Sean Kelly <sean invisibleduck.org> wrote:Factorial series is defined in terms of the last term, so you only need to remember the last term. i.e. 5! = 4! * 5. So constant space, constant time per iteration.Andrei Alexandrescu wrote:I wonder how efficent it is? Does it store last few sequence elements or re-compute then again and again? I wouldn't use it in the latter case.Ary Borenszweig wrote:Awesome :-) I think that proves the efficacy of the approach all by itself. Sean

Feb 03 2009

Steven Schveighoffer wrote:I don't think such a series is definable with Andrei's template. I think his series template is only usable in situations where computing a[n] depends only on n and the elements a[n-X]..a[n-1], where X is a constant. I'm not really a mathemetician, so I don't know the technical term for the differences, I'm sure there is one.Time-invariant, or shift-invariant.

Feb 03 2009

Joel C. Salomon wrote:Steven Schveighoffer wrote:Great! I didn't know (haven't learned college-level Math in English; sometimes I wonder how I fumbled through grad school without major misunderstandings). By the way, I might have been wrong with the name "series" itself. I thought "series" is something like a_n = f(a_{n-1},...,f_a{n-k}). However, according to Wikipedia: http://en.wikipedia.org/wiki/Infinite_series series is really what I thought is called "partial sums", i.e. s_n is the sum of elements of a sequence a_n up to the nth element. So should I change "series" with "sequence"? How about what I called "ClosedFormSeries"? By that I meant a series, (pardon, sequence), in which there is no recurrence formula - the nth element a_n can be expressed in terms of n and a[0], ..., a[k] (a sort of "random access" for a sequence). So, what names should I use? English-speaking mathematicians across the newsgroup, unite! AndreiI don't think such a series is definable with Andrei's template. I think his series template is only usable in situations where computing a[n] depends only on n and the elements a[n-X]..a[n-1], where X is a constant. I'm not really a mathemetician, so I don't know the technical term for the differences, I'm sure there is one.Time-invariant, or shift-invariant.

Feb 03 2009

On Wed, Feb 4, 2009 at 8:26 AM, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:Joel C. Salomon wrote:My digital signal processing textbook refers to "discrete-time sequences", not series. But I'm pretty sure I've heard "discrete-time series" used too. So I'd say either sequence or series is just fine. But that's just the EE perspective. Pure math guys might have a different take. --bbSteven Schveighoffer wrote:Great! I didn't know (haven't learned college-level Math in English; sometimes I wonder how I fumbled through grad school without major misunderstandings). By the way, I might have been wrong with the name "series" itself. I thought "series" is something like a_n = f(a_{n-1},...,f_a{n-k}). However, according to Wikipedia: http://en.wikipedia.org/wiki/Infinite_series series is really what I thought is called "partial sums", i.e. s_n is the sum of elements of a sequence a_n up to the nth element. So should I change "series" with "sequence"? How about what I called "ClosedFormSeries"? By that I meant a series, (pardon, sequence), in which there is no recurrence formula - the nth element a_n can be expressed in terms of n and a[0], ..., a[k] (a sort of "random access" for a sequence). So, what names should I use? English-speaking mathematicians across the newsgroup, unite!I don't think such a series is definable with Andrei's template. I think his series template is only usable in situations where computing a[n] depends only on n and the elements a[n-X]..a[n-1], where X is a constant. I'm not really a mathemetician, so I don't know the technical term for the differences, I'm sure there is one.Time-invariant, or shift-invariant.

Feb 03 2009

On Tue, 03 Feb 2009 15:26:45 -0800, Andrei Alexandrescu wrote:So, what names should I use? English-speaking mathematicians across the newsgroup, unite!I'm not a mathemetician, but to me elements in a series cannot necessarily be predicted by knowing the values of existing elements, whereas in a sequence an element can be predicted using only the existing element values. -- Derek Parnell Melbourne, Australia skype: derek.j.parnell

Feb 03 2009

"Andrei Alexandrescu" wroteSo should I change "series" with "sequence"? How about what I called "ClosedFormSeries"? By that I meant a series, (pardon, sequence), in which there is no recurrence formula - the nth element a_n can be expressed in terms of n and a[0], ..., a[k] (a sort of "random access" for a sequence). So, what names should I use? English-speaking mathematicians across the newsgroup, unite!http://en.wikipedia.org/wiki/Recurrence_relation I'd say recurrence!(...) possibly? But definitely a range is analagous to a sequence defined in math (as defined by wikipedia). -Steve

Feb 03 2009

Andrei Alexandrescu wrote:Great! I didn't know (haven't learned college-level Math in English; sometimes I wonder how I fumbled through grad school without major misunderstandings). By the way, I might have been wrong with the name "series" itself. I thought "series" is something like a_n = f(a_{n-1},...,f_a{n-k}). However, according to Wikipedia: http://en.wikipedia.org/wiki/Infinite_series series is really what I thought is called "partial sums", i.e. s_n is the sum of elements of a sequence a_n up to the nth element. So should I change "series" with "sequence"? How about what I called "ClosedFormSeries"? By that I meant a series, (pardon, sequence), in which there is no recurrence formula - the nth element a_n can be expressed in terms of n and a[0], ..., a[k] (a sort of "random access" for a sequence). So, what names should I use? English-speaking mathematicians across the newsgroup, unite!I believe the mathematically correct terms would be RecursiveSequence and ClosedFormSequence. If I were to use just Sequence, it would in fact be for the latter. A series is, as you said, the sum of all the terms in a sequence, whereas summing only a finite set of terms gives a partial sum. (The latter could be implemented as a range.) A recurrence relation is an expression that recursively defines a sequence (i.e. the string argument of the template). I prefer MathWorld to Wikipedia when it comes to these things. Here are some (possibly) useful links: Recursive sequences: http://mathworld.wolfram.com/RecursiveSequence.html Some sequences that could possibly be rangeified: http://mathworld.wolfram.com/Sequence.html Series: http://mathworld.wolfram.com/Series.html Partial sums (and other sums) of sequences: http://mathworld.wolfram.com/PartialSum.html -Lars

Feb 04 2009

Andrei Alexandrescu wrote:So should I change "series" with "sequence"? How about what I called "ClosedFormSeries"? By that I meant a series, (pardon, sequence), in which there is no recurrence formula - the nth element a_n can be expressed in terms of n and a[0], ..., a[k] (a sort of "random access" for a sequence). So, what names should I use? English-speaking mathematicians across the newsgroup, unite!These are sequences. (Or, in an EE context, “signals”, but let’s not go there… ☺) Except: a sequence might be the coefficients {α₀, α₁, α₂, …} of the power _series_ α₀x⁰ + α₁x¹ + α₂x² + ⋯, in which case the sequence is just a representation of the power series. There are some cool tricke to be played with power series represented this way; e.g., see Doug McIlroy’s “Squinting at Power Series” at <http://plan9.bell-labs.com/who/rsc/thread/squint.pdf>. —Joel Salomon

Feb 04 2009

Denis Koroskin wrote:Of course, but does it *really* discard old values? That's what I doubt.It really discards old values.Ok, Factorial/Fibonacci is easy. How would you implement, say, the following sequence: a[n] = a[0] + a[n / 8]; // ?Very simple (assuming a[0] = 1): auto s = series("cast(uint) (log(n) / 3) + 2")(1); At least that's what I got through expansion :o). What I'm saying is that series() does not do the work for you to either have unbounded state, backtrack as needed, or do algebraic manipulation. The series must come in analytic form. It's a good point. The current implementation defines a series as k initial elements and a method of computing a_{n} given a_{n-1} through a_{n-k}. Most series come in this form. Few interesting series don't, but they are rare and tricky anyway; they are not supported as of yet. I will note that your formula above shouldn't compile (it currently does and runs with erratic results).Now it is log(n) to compute from scratch but you should store O(n) elements to make it constant time. I mean, the algorithm ought to have very good heuristics. And sometimes it is better to re-compute elements instead of caching them.There's no heuristics and no computation vs. storage tradeoff. It's as cut and dried as it gets. Given k initial elements and a formula to compute an element from the past k elements, series() implements an infinite range. But it would be great to extend this to more non-analytic series. Andrei

Feb 03 2009

Denis Koroskin wrote:On Tue, 03 Feb 2009 21:25:21 +0300, Sean Kelly <sean invisibleduck.org> wrote:I wouldn't use it either, in fact I have a dim view of all books, articles, and courses that promote exponential-time Fibonacci and linear-space factorial. It just promotes sloppy algorithmic thinking under the pretense that recursion is cool. (I also have a dim view of the FP proponents who promote the quicksort that actually doesn't sort in place and returns new arrays by value every iteration, consuming O(n log n) extra memory. But I digress.) The size of the state held by a series is equal to the number of initial arguments passed when it is constructed. The arguments are stored in a fixed-size array sitting in the series object. So: auto fib = series!("a[n-1] + a[n]")(1, 1); holds an int[2], initialized with [1, 1]. The current index in the series (a size_t initialized to 0) completes the state size. When fib.next is called, the ((n+1) % 2)th element in the array is overwritten with the result of a[(n-1)%2] + a[n%2]. Then n is incremented. fib.head returns a[n%2]. In the factorial case it's simpler because the state size is 1. Since the state size is used as a compile-time constant, the compiler has the opportunity to optimize away calculations like n%1. Andrei

Feb 03 2009

Andrei Alexandrescu wrote:I've updated my code and documentation to include series (as in math) in the form of infinite ranges. Also series in closed form (given n can compute the nth value without iterating) are supported as random-access ranges.I've been thinking a little about the concepts involved in range endpoints. Most important ranges are homomorphic to ints; that is, given [x..y], there is some finite number n of elements in the range. And there is an ordering: successor(successor(x)) repeated n times will return y. As well as ints and many data structures, fixed-point and built-in floating-point arithmetic obey these properties. Interestingly this even applies to an "infinite" range: [1..real.infinity] has a limited number of elements. However, some other ranges do NOT behave this way. Mathematical real numbers defined symbollically, for example. More realistically, arbitrary-precision fractions. For these types of ranges, there is no successor function. Thus, they are not even input ranges; but they have some properties of random-access ranges. There are many algorithms which work on these non-quantised ranges. Now consider the range 5.0L..real.max, on a system where real is 128 bits. Is it a random-access range? Sort of. You can't provide an opIndex(), even with ulong as an index, because there are just too many entries. But there are many operations you can still do. predecessor and successor are nextDown(), nextUp(). My root-finding algorithm in std.numeric uses these functions as well as an approximate-midpoint-in-representation-space function. In any case, I think it would be good to come up with some standard names for the predecessor and successor functions.

Jan 31 2009