www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - On Iteration

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
I consider changing a bit D's range model following the better 
understanding reflected in this article:

http://erdani.com/publications/on-iteration.html

If you have any thoughts and if you can help with the implementation, 
please let us know.


Andrei
Nov 09 2009
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 I consider changing a bit D's range model following the better
 understanding reflected in this article:
 http://erdani.com/publications/on-iteration.html
 If you have any thoughts and if you can help with the implementation,
 please let us know.
 Andrei

Can you detail a little more what you're proposing? I read your article this morning, though admittedly I skimmed over some of the examples that looked like things I had already been using in my code since ranges were released. The only thing I noticed was the save() function for forward ranges. This resolves the old wart that input ranges vs. forward ranges are strictly a convention, and I think it's a good idea. Other than that, again, please distill what you're proposing.
Nov 09 2009
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
dsimcha wrote:
 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 I consider changing a bit D's range model following the better
 understanding reflected in this article:
 http://erdani.com/publications/on-iteration.html
 If you have any thoughts and if you can help with the implementation,
 please let us know.
 Andrei

Can you detail a little more what you're proposing? I read your article this morning, though admittedly I skimmed over some of the examples that looked like things I had already been using in my code since ranges were released. The only thing I noticed was the save() function for forward ranges. This resolves the old wart that input ranges vs. forward ranges are strictly a convention, and I think it's a good idea. Other than that, again, please distill what you're proposing.

One is indeed save(), the other is separation of iteration from access. These are the only major changes. The second is quite hefty. BTW, just saw on the announce group that the article was reddited - please vote up: http://www.reddit.com/r/programming/comments/a2hv3/ Andrei
Nov 09 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Bill Baxter wrote:
 On Mon, Nov 9, 2009 at 6:17 PM, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:
 dsimcha wrote:
 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s
 article
 I consider changing a bit D's range model following the better
 understanding reflected in this article:
 http://erdani.com/publications/on-iteration.html
 If you have any thoughts and if you can help with the implementation,
 please let us know.
 Andrei

this morning, though admittedly I skimmed over some of the examples that looked like things I had already been using in my code since ranges were released. The only thing I noticed was the save() function for forward ranges. This resolves the old wart that input ranges vs. forward ranges are strictly a convention, and I think it's a good idea. Other than that, again, please distill what you're proposing.

These are the only major changes. The second is quite hefty. BTW, just saw on the announce group that the article was reddited - please vote up: http://www.reddit.com/r/programming/comments/a2hv3/ Andrei

I'm not sure why this one is staying so far under the radar. Just marketing? The title of the previous reddit story "Iterators must die" got a lot more attention. I'd hate to think it just comes down to picking deliberately inflammatory titles. --bb

For one thing I couldn't even see the article on the "Programming" page after only a few hours after posting. I guess if it doesn't stay there for a couple of hours after posting to get primed, it never buoys to attention. Andrei
Nov 10 2009
prev sibling next sibling parent Bill Baxter <wbaxter gmail.com> writes:
On Mon, Nov 9, 2009 at 6:17 PM, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:
 dsimcha wrote:
 =3D=3D Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s
 article
 I consider changing a bit D's range model following the better
 understanding reflected in this article:
 http://erdani.com/publications/on-iteration.html
 If you have any thoughts and if you can help with the implementation,
 please let us know.
 Andrei

Can you detail a little more what you're proposing? =A0I read your artic=


 this
 morning, though admittedly I skimmed over some of the examples that look=


 like
 things I had already been using in my code since ranges were released.
 =A0The only
 thing I noticed was the save() function for forward ranges. =A0This reso=


 the old
 wart that input ranges vs. forward ranges are strictly a convention, and=


 think
 it's a good idea. =A0Other than that, again, please distill what you're
 proposing.

One is indeed save(), the other is separation of iteration from access. These are the only major changes. The second is quite hefty. BTW, just saw on the announce group that the article was reddited - pleas=

 vote up: http://www.reddit.com/r/programming/comments/a2hv3/


 Andrei

I'm not sure why this one is staying so far under the radar. Just marketing? The title of the previous reddit story "Iterators must die" got a lot more attention. I'd hate to think it just comes down to picking deliberately inflammatory titles. --bb
Nov 10 2009
prev sibling parent Moritz Warning <moritzwarning web.de> writes:
On Tue, 10 Nov 2009 06:59:31 -0800, Bill Baxter wrote:

 On Mon, Nov 9, 2009 at 6:17 PM, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:
 dsimcha wrote:
 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s
 article
 I consider changing a bit D's range model following the better
 understanding reflected in this article:
 http://erdani.com/publications/on-iteration.html If you have any
 thoughts and if you can help with the implementation, please let us
 know.
 Andrei

Can you detail a little more what you're proposing?  I read your article this morning, though admittedly I skimmed over some of the examples that looked like things I had already been using in my code since ranges were released.  The only thing I noticed was the save() function for forward ranges.  This resolves the old wart that input ranges vs. forward ranges are strictly a convention, and I think it's a good idea.  Other than that, again, please distill what you're proposing.

One is indeed save(), the other is separation of iteration from access. These are the only major changes. The second is quite hefty. BTW, just saw on the announce group that the article was reddited - please vote up: http://www.reddit.com/r/programming/comments/a2hv3/ Andrei

marketing? The title of the previous reddit story "Iterators must die" got a lot more attention. I'd hate to think it just comes down to picking deliberately inflammatory titles. --bb

I think it's another case of "Iterators? Again?". The announcement to finish the topic is likely to have a better perception.
Nov 10 2009
prev sibling next sibling parent reply Lutger <lutger.blijdestijn gmail.com> writes:
Andrei Alexandrescu wrote:

 I consider changing a bit D's range model following the better
 understanding reflected in this article:
 
 http://erdani.com/publications/on-iteration.html
 
 If you have any thoughts and if you can help with the implementation,
 please let us know.
 
 
 Andrei

I thoroughly enjoyed the article, thank you in particular for making this material accessible to non computer scientists like myself. More questions than thoughts if I may, do feel free to ignore them, these are just things I wonder about: - how to do ranges over a tree? My first thought was that a tree would define preorder / inorder / postorder ranges, and then perhaps visitors for more complex algorithms. But in the 'iterators must go' keynote you mentioned implementing traversal over trees by popFront() taking a parameter indicating the branch to go to. Can you or anybody else shed more light on how this will work out? What about graphs? - ranges over immutable data structures I tried making an immutable linked list and stack (not as simple as I thought) with range support. Ranges must be mutable though. So I take it that ranges are not usually supposed to be shared, rather they be consumable, local views into immutable data structures instead? This leads to a broader question: is it possible to model some support for concurrency in ranges? So that algorithms can possibly choose a particular implementation based on the concurrent properties of a range? Perhaps this relates to the separation between iteration and access as well. - why is a UTF-string iterator bidirectional and why is that unexpected? - Is there already a standard way to implement a default range for a container? I have tons more questions, but I'll try to work them out for myself first or post them in .learn.
Nov 10 2009
next sibling parent BLS <windevguy hotmail.de> writes:
On 10/11/2009 11:18, Lutger wrote:
 Andrei Alexandrescu wrote:

 I consider changing a bit D's range model following the better
 understanding reflected in this article:

 http://erdani.com/publications/on-iteration.html


Very good read.
 - how to do ranges over a tree?
 My first thought was that a tree would define preorder / inorder / postorder
 ranges, and then perhaps visitors for more complex algorithms.

I asked the same question quit a while ago... I think we have to imagine a tree's branch as sub range. ( In other words, treat them like linear structures) How to implement it? I dunno. IMO it would make sense to implement some basic data structures for std.mutable.dtl. (Tree like structures) ...not production ready, just as Range "proof of product" test. atm I am implementing two of them : skip lists and left leaning rb trees. Would be nice to have some support btw.
Nov 10 2009
prev sibling next sibling parent "Phil Deets" <pjdeets2 gmail.com> writes:
On Tue, 10 Nov 2009 05:18:59 -0500, Lutger <lutger.blijdestijn gmail.com>  
wrote:

 - why is a UTF-string iterator bidirectional and why is that unexpected?

I think it is wouldn't support random access since accessing the nth code point (code points are similar to characters) is not a constant time operation since different code points can be made up of different numbers of bytes. That isn't necessarily intuitive since UTF-strings are stored contiguously in memory; so you might expect them to be random-accessible.
Nov 10 2009
prev sibling next sibling parent Bill Baxter <wbaxter gmail.com> writes:
On Tue, Nov 10, 2009 at 11:34 AM, Phil Deets <pjdeets2 gmail.com> wrote:
 On Tue, 10 Nov 2009 05:18:59 -0500, Lutger <lutger.blijdestijn gmail.com>
 wrote:

 - why is a UTF-string iterator bidirectional and why is that unexpected?

I think it is wouldn't support random access since accessing the nth code point (code points are similar to characters) is not a constant time operation since different code points can be made up of different numbers of bytes. That isn't necessarily intuitive since UTF-strings are stored contiguously in memory; so you might expect them to be random-accessible.

I thought the comment was about this: you might expect it to be just a forward iterator, but (surprise!) you can also find the previous codepoint in O(1) time, due to lead units being in values ranges distinct from following units. But I still don't find it particularly unexpected. It's probably only unexpected if you don't know anything about UTF other than the fact that each character is a variable number of bytes. --bb
Nov 10 2009
prev sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--0016e6dab11bb3520b04780b168a
Content-Type: text/plain; charset=ISO-8859-1

On Tue, Nov 10, 2009 at 16:07, BLS <windevguy hotmail.de> wrote:

 On 10/11/2009 11:18, Lutger wrote:

  - how to do ranges over a tree?
 My first thought was that a tree would define preorder / inorder /
 postorder
 ranges, and then perhaps visitors for more complex algorithms.

I asked the same question quit a while ago... I think we have to imagine a tree's branch as sub range. ( In other words, treat them like linear structures) How to implement it? I dunno.

I had a Tree (and Graph) struct some month ago. In another module, I defined depthFirst(Tree t) and breadthFirst(Tree t) functions, which just returned a lazy range (a struct, as always), iterating in a depth-first/breadth-first way on t. Except having them as methods of Tree/Graph, how would you do it? --0016e6dab11bb3520b04780b168a Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Tue, Nov 10, 2009 at 16:07, BLS <span dir=3D"= ltr">&lt;<a href=3D"mailto:windevguy hotmail.de">windevguy hotmail.de</a>&g= t;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"border-left:= 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex= ;"> <div class=3D"im">On 10/11/2009 11:18, Lutger wrote:<br> <br> <blockquote class=3D"gmail_quote" style=3D"border-left: 1px solid rgb(204, = 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> - how to do ranges over a tree?<br> My first thought was that a tree would define preorder / inorder / postorde= r<br> ranges, and then perhaps visitors for more complex algorithms.<br> </blockquote> <br> <br></div> I asked the same question quit a while ago... I think we have to imagine a = tree&#39;s branch as sub range. ( In other words, treat them like linear st= ructures)<br> <br> How to implement it? I dunno.<br></blockquote><div><br>I had a Tree (and Gr= aph) struct some month ago. In another module, I defined depthFirst(Tree t)= and breadthFirst(Tree t) functions, which just returned a lazy range (a st= ruct, as always), iterating in a depth-first/breadth-first way on t. Except= having them as methods of Tree/Graph, how would you do it?<br> <br></div></div> --0016e6dab11bb3520b04780b168a--
Nov 10 2009
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 09 Nov 2009 20:53:01 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 I consider changing a bit D's range model following the better  
 understanding reflected in this article:

 http://erdani.com/publications/on-iteration.html

 If you have any thoughts and if you can help with the implementation,  
 please let us know.

Very good article. I think the idea of separating access from traversal is a very good one. I still don't like the idea of having a "save" method vs. just assignment but I don't have a better idea right now. One note: As you know I think iterators are still useful for keeping pointers to individual elements. One other drawback from storing 1-element ranges as a substitute is that they may not remain one-element ranges. For instance, if you had a sorted map, stored as a RB-tree, a one element range would undoubtedly consist of a begin element and an end element, which would be the next largest element. If you inserted an element that was between those two, suddenly your 1-element range becomes a 2-element range. Although you can simply say that all ranges are invalidated when the underlying container is modified, an iterator-based solution can say that iterators always remain valid when the container is added to. That allows certain types of logic that wouldn't be as efficient with ranges. What about adding a "marker" type that has the ability to reference the data but not to traverse to another element (except by assignment)? Basically a rebindable reference. You can always get a marker to a copyable range's front element, and then a container can use 2 markers to make a traversable range, or use it as the primitive for functions like remove or insert (as an insert location), and 3-legged functions that don't map easily into 2-range functions. I'm thinking this is how I'm going to implement ranges in dcollections. Currently I support cursors, which are akin to C++ iterators (my Iterator objects are akin to Java iterators, and support only foreach). But what I might do is change them into markers, and make ranges out of 2 of them. -Steve
Nov 10 2009
prev sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--0016e6d99ba7f8f42d04780aff60
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: quoted-printable

On Tue, Nov 10, 2009 at 02:53, Andrei Alexandrescu <
SeeWebsiteForEmail erdani.org> wrote:

 I consider changing a bit D's range model following the better
 understanding reflected in this article:

 http://erdani.com/publications/on-iteration.html

 If you have any thoughts and if you can help with the implementation,
 please let us know.

Very nice article, and a pleasure to read! I'll try do do some comments, but right now what strikes me most is the Ref!T (well, Ref<T>) idea, this separation between traversal and access-mode. For example, this bothers me immensely: auto m =3D map!"a*a"([0,1,2,3][]); // right-o, a lazy map, cool! auto c =3D cycle(m); // boom! Doesn't work. Because map.front is not a lvalue and cycle returns by ref. Why can't I have my 0,1,4, 9,0,1,4, 9,0,1,4,9,... range? Must cycle.front really return by ref? I'd be delighted to have some ref-ranges for sorting, writing and such, but I use simple non-ref ranges 9 times out of ten. And it seems std.range fall= s over itself to provide 'ref T front'. It makes for some interesting-to-stud= y code, but some ugly one as well. So, could you elaborate on this idea ? Could this be a matter of policy? struct Cycle(R, ByRefPolicy br =3D ByRef.ByRef) if (isForwardRange!(R)) And then, I guess, either having different implementation of .front (ugh, but why not) or having something like: Ref!(T, br) front() { ...} // Is this even possible? Some comments: p.5: "When calling an algorithm with ranges, you write: vector<int> v; ... *// implicitly take the "all" range of v* sort(v);" Do you think containers shall routinely expose a .all method, returning their content as a range, as simply as possible? Btw, as an aside, std.range I guess should have some 'rangification' functions for common constructs in D, like AA and static arrays. It's a bit frustrating not to be able to write: auto m =3D map!"a*a"([0,1,2,3]); // Though I know [0,1,2,3] is _not_ a rang= e. Maybe instead of isInputRange!R, having isInputRange!(AsRange!R) ? or: auto aa =3D ["a":1, "b":2, "cde":33]; auto someVal =3D filter!"a.value>3"(aa.all); // Or whatever, I'm all for aa.all returning a lazy range with tuple(key.value) as elements. p.7: "The save method serves two purposes. First, in a language with reference semantics (such as Java), lookIMadeACopy is not a copy at all=97it's an ali= as, another reference to the same underlying Range object. Copying the actual object requires a method call. " vote++. I was bitten by this just a few days ago, not thinking that modifying an array inside a range struct would also modify the initial array. I had to use some static if to either have _input =3D input.dup or _input. Doing _input=3Dinput.save() could help me there. Also p.7: "So a random access range extends different concepts, depending on its finiteness." Yes indeed. It may be interesting to put this somewhere in the std.range docs. Hell, it's obvious the entire article is a must read before using std.algo and std.range. Though it was interesting to re-discover this by myself. The first time you start writing .back for an infinite range, you stop, frown, and then smile :-) p.9: "Other, more exotic range capabilities are primitives such as lookahead or putback." I'd have liked to have lookahead sometimes... What would putback do? Re-inject the last front value (and not some other arbitrary value) into the range, returning it to its 'pristine' state? p. 10: "In keeping with higher-order functions that take and return other functions, a higher-order range is one that aggregates and manipulates othe= r ranges, while itself still offering a range interface. Building ranges that decorate other ranges is easy, useful, and fun." Oh hell, yes! That has been the funniest coding I did this year. Higher-order ranges is a nice name btw. You could also call them meta-ranges, but it may be a bit too pretentious. p. 10: "As a rule, a higher-order range must offer the highest capability that it can, subject to what the original range can offer." Yes, but std.range/algo don't always do that. Would you be interested in putting some .back/length/opIndex into map for example? That would make it play nice with some other ranges/algorithms. I could put it into bugzilla..= . I was looking for a name for this kind of extensible range. It's a common pattern, and I'm tired having to write in docs that such and such range wil= l also have a length if the input ranges have one, etc. As these are also wrapper ranges, I call them 'tight wrappers', but will take any name provided. p. 10: "If all contained ranges offer random access *and* length, then Chain offer= s random access as well." Yes, but it's an 'if', not an 'iff'. I was bitten by this. A common test range for me was: auto c =3D chain([0,1,2][], cycle([3,4,5][])); // 0,1,2,3,4,5,3,4,5,3,4,5, = ... Except it doesn't work as Chain is written right now. It doesn't even compile: Chain.opIndex assumes all ranges have a length when they are random-access. But cycle is RA and infinite! The solution is trivial to code, obviously, but I routinely forget to make it a bugzilla request (with a patch). (Yes I know I should be putting it inside bugzilla right now. But one of my daughters is sick and weeping, so once more it will have to wait. But now a= t least Andrei knows it). p.11: "I happen to think that bring_to_front would be a much more intuitive name than rotate." Indeed. rotate would be something like: auto rotate(R)(size_t n, R range) { returns chain(range[n..$], range[0..n]); // for a random-access range. } rotate(3, [0,1,2,3,4,56][]) -> [3,4,5,6,0,1,2][] p.12: "Fortunately, this problem is easily solved by defining a new range type, Until. Until is a range that takes another range r and a value v, starts at the beginning of r, and ends just before r.front() =3D=3D v (or at the natu= ral end of r if v is not to be found). Lazy computation for the win!" Nice. Is Until part of std.algo? (Gosh, this module is so big I can't get i= t in my head). I personnaly use takeWhile or takeUntil. You ask for limitation, at the end. One other limitation (though I don't know if that's really one) is for higher-order ranges that produce/contains two or more ranges. Separate, for example, which separates a range into two sub-ranges, one created by filtering the input range with predicate pred, the other by not!pred auto separate(alias pred, R) (R range) { return tuple(filter!pred(range), filter!(not!pred)(range)); } I return a pair of ranges, but ideally would like a unique range, with a wa= y to address one subrange or another. Maybe with a front(size_t index) method: front(0) returns subrange_0's front, front(1) for the second one and so on... Philippe --0016e6d99ba7f8f42d04780aff60 Content-Type: text/html; charset=windows-1252 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Tue, Nov 10, 2009 at 02:53, Andrei Alexandres= cu <span dir=3D"ltr">&lt;<a href=3D"mailto:SeeWebsiteForEmail erdani.org">S= eeWebsiteForEmail erdani.org</a>&gt;</span> wrote:<br><blockquote class=3D"= gmail_quote" style=3D"border-left: 1px solid rgb(204, 204, 204); margin: 0p= t 0pt 0pt 0.8ex; padding-left: 1ex;"> I consider changing a bit D&#39;s range model following the better understa= nding reflected in this article:<br> <br> <a href=3D"http://erdani.com/publications/on-iteration.html" target=3D"_bla= nk">http://erdani.com/publications/on-iteration.html</a><br> <br> If you have any thoughts and if you can help with the implementation, pleas= e let us know.<font color=3D"#888888"></font></blockquote><div><br>Very nic= e article, and a pleasure to read!<br>I&#39;ll try do do some comments, but= right now what strikes me most is the Ref!T (well, Ref&lt;T&gt;) idea, thi= s separation between traversal and access-mode.<br> For example, this bothers me immensely:<br><br>auto m =3D map!&quot;a*a&quo= t;([0,1,2,3][]); =A0=A0 // right-o, a lazy map, cool!<br>auto c=A0 =3D cycl= e(m);=A0=A0 // boom! Doesn&#39;t work. Because map.front is not a lvalue an= d cycle returns by ref.<br> <br>Why can&#39;t I have my 0,1,4, 9,0,1,4, 9,0,1,4,9,... range? Must cycle= .front really return by ref?<br><br>I&#39;d be delighted to have some ref-r= anges for sorting, writing and such, but I use simple non-ref ranges 9 time= s out of ten. And it seems std.range falls over itself to provide &#39;ref = T front&#39;. It makes for some interesting-to-study code, but some ugly on= e as well.<br> <br>So, could you elaborate on this idea ? Could this be a matter of policy= ? <br><br>struct Cycle(R, ByRefPolicy br =3D ByRef.ByRef) if (isForwardRang= e!(R))<br><br>And then, I guess, either having different implementation of = .front (ugh, but why not) or having something like:<br> <br>Ref!(T, br) front() { ...} // Is this even possible?<br><br><br>Some co= mments:<br><br>p.5:<br>&quot;When calling an algorithm with ranges, you wri= te: <pre>vector&lt;int&gt; v;<br>...<br><em>// implicitly take the &quot;all&qu= ot; range of v</em><br>sort(v);&quot;</pre><br>Do you think containers shal= l routinely expose a .all method, returning their content as a range, as si= mply as possible?<br> <br>Btw, as an aside, std.range I guess should have some &#39;rangification= &#39; functions for common constructs in D, like AA and static arrays. It&#= 39;s a bit frustrating not to be able to write:<br><br>auto m =3D map!&quot= ;a*a&quot;([0,1,2,3]); // Though I know [0,1,2,3] is _not_ a range. Maybe i= nstead of isInputRange!R, having isInputRange!(AsRange!R) ?<br> or:<br>auto aa =3D [&quot;a&quot;:1, &quot;b&quot;:2, &quot;cde&quot;:33];<= br>auto someVal =3D filter!&quot;a.value&gt;3&quot;(aa.all); // Or whatever= , I&#39;m all for aa.all returning a lazy range with tuple(key.value) as el= ements.<br> <br><br>p.7:<br><br>&quot;The <tt>save</tt> method serves two purposes. Fir= st, in a language with reference semantics (such as Java), <tt>lookIMadeACo= py</tt> is not a copy at all=97it&#39;s an alias, another reference to the = same underlying <tt>Range</tt> object. Copying the actual object requires a= method call. &quot;<br> <br>vote++. I was bitten by this just a few days ago, not thinking that mod= ifying an array inside a range struct would also modify the initial array. = I had to use some static if to either have _input =3D input.dup or _input. = Doing _input=3Dinput.save() could help me there.<br> <br>Also p.7:<br><br>&quot;So a random access range extends different conce= pts, depending on its finiteness.&quot;<br><br>Yes indeed. It may be intere= sting to put this somewhere in the std.range docs. Hell, it&#39;s obvious t= he entire article is a must read before using std.algo and std.range.<br> <br>Though it was interesting to re-discover this by myself. The first time= you start writing .back for an infinite range, you stop, frown, and then s= mile :-)<br><br>p.9:<br><br>&quot;Other, more exotic range capabilities are= primitives such as <tt>lookahead</tt> or <tt>putback</tt>.&quot;<br> <br>I&#39;d have liked to have lookahead sometimes...<br>What would putback= do? Re-inject the last front value (and not some other arbitrary value) in= to the range, returning it to its &#39;pristine&#39; state?<br><br>p. 10:<b= r> <br>&quot;In keeping with higher-order functions that take and return other functions, a higher-order range is one that aggregates and manipulates other ranges, while itself still offering a range interface. Building ranges that decorate other ranges is easy, useful, and fun.&quot;<br><br>Oh= hell, yes! That has been the funniest coding I did this year. Higher-order= ranges is a nice name btw. You could also call them meta-ranges, but it ma= y be a bit too pretentious.<br> <br>p. 10:<br><br>&quot;As a rule, a higher-order range must offer the high= est capability that it can, subject to what the original range can offer.&q= uot;<br><br>Yes, but std.range/algo don&#39;t always do that. Would you be = interested in putting some .back/length/opIndex into map for example? That = would make it play nice with some other ranges/algorithms. I could put it i= nto bugzilla...<br> <br>I was looking for a name for this kind of extensible range. It&#39;s a = common pattern, and I&#39;m tired having to write in docs that such and suc= h range will also have a length if the input ranges have one, etc. As these= are also wrapper ranges, I call them &#39;tight wrappers&#39;, but will ta= ke any name provided.<br> <br>p. 10:<br>&quot;If all contained ranges offer random access <em>and</em=
 length, then <tt>Chain</tt> offers random access as well.&quot;<br><br>Ye=

. A common test range for me was:<br> <br>auto c =3D chain([0,1,2][], cycle([3,4,5][])); // 0,1,2,3,4,5,3,4,5,3,4= ,5, ...<br><br>Except it doesn&#39;t work as Chain is written right now. It= doesn&#39;t even compile: Chain.opIndex assumes all ranges have a length w= hen they are random-access. But cycle is RA and infinite!<br> The solution is trivial to code, obviously, but I routinely forget to make = it a bugzilla request (with a patch).<br>(Yes I know I should be putting it= inside bugzilla right now. But one of my daughters is sick and weeping, so= once more it will have to wait. But now at least Andrei knows it).<br> <br>p.11:<br><br>&quot;I happen to think that <tt>bring_to_front</tt> would= be a much more intuitive name than <tt>rotate</tt>.&quot;<br><br>Indeed. r= otate would be something like:<br><br>auto rotate(R)(size_t n, R range) {<b= r> =A0=A0 returns chain(range[n..$], range[0..n]); // for a random-access rang= e.<br>}<br><br>rotate(3, [0,1,2,3,4,56][]) -&gt; [3,4,5,6,0,1,2][]<br><br>p= .12:<br><br>&quot;Fortunately, this problem is easily solved by defining a = new range type, <tt>Until</tt>. <tt>Until</tt> is a range that takes anothe= r range <tt>r</tt> and a value <tt>v</tt>, starts at the beginning of <tt>r= </tt>, and ends just before <tt>r.front() =3D=3D v</tt> (or at the natural = end of <tt>r</tt> if <tt>v</tt> is not to be found). Lazy computation for t= he win!&quot;<br> <br>Nice. Is Until part of std.algo? (Gosh, this module is so big I can&#3= 9;t get it in my head).<br><br>I personnaly use takeWhile or takeUntil.<br>= <br><br>You ask for limitation, at the end. One other limitation (though I = don&#39;t know if that&#39;s really one) is for higher-order ranges that pr= oduce/contains two or more ranges.<br> Separate, for example, which separates a range into two sub-ranges, one cre= ated by filtering the input range with predicate pred, the other by not!pre= d<br><br>auto separate(alias pred, R) (R range) {<br>=A0=A0=A0 return tuple= (filter!pred(range), filter!(not!pred)(range));<br> }<br>I return a pair of ranges, but ideally would like a unique range, with= a way to address one subrange or another.<br>Maybe with a front(size_t ind= ex) method: front(0) returns subrange_0&#39;s front, front(1) for the secon= d one and so on...<br> <br>=A0 Philippe<br><br></div></div> --0016e6d99ba7f8f42d04780aff60--
Nov 10 2009