<div class="gmail_quote">On Tue, Nov 10, 2009 at 02:53, Andrei Alexandrescu <span dir="ltr"><<a href="mailto:SeeWebsiteForEmail@erdani.org">SeeWebsiteForEmail@erdani.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
I consider changing a bit D's range model following the better understanding reflected in this article:<br>
<br>
<a href="http://erdani.com/publications/on-iteration.html" target="_blank">http://erdani.com/publications/on-iteration.html</a><br>
<br>
If you have any thoughts and if you can help with the implementation, please let us know.<font color="#888888"></font></blockquote><div><br>Very nice article, and a pleasure to read!<br>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.<br>
For example, this bothers me immensely:<br><br>auto m = map!"a*a"([0,1,2,3][]); // right-o, a lazy map, cool!<br>auto c = cycle(m); // boom! Doesn't work. Because map.front is not a lvalue and cycle returns by ref.<br>
<br>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?<br><br>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 falls over itself to provide 'ref T front'. It makes for some interesting-to-study code, but some ugly one 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 = ByRef.ByRef) if (isForwardRange!(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 comments:<br><br>p.5:<br>"When calling an algorithm with ranges, you write:
<pre>vector<int> v;<br>...<br><em>// implicitly take the "all" range of v</em><br>sort(v);"</pre><br>Do you think containers shall routinely expose a .all method, returning their content as a range, as simply as possible?<br>
<br>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:<br><br>auto m = map!"a*a"([0,1,2,3]); // Though I know [0,1,2,3] is _not_ a range. Maybe instead of isInputRange!R, having isInputRange!(AsRange!R) ?<br>
or:<br>auto aa = ["a":1, "b":2, "cde":33];<br>auto someVal = filter!"a.value>3"(aa.all); // Or whatever, I'm all for aa.all returning a lazy range with tuple(key.value) as elements.<br>
<br><br>p.7:<br><br>"The <tt>save</tt> method serves two purposes. First, in a language with reference semantics (such as Java), <tt>lookIMadeACopy</tt> is not a copy at all—it's an alias, another reference to the same underlying <tt>Range</tt> object. Copying the actual object requires a method call. "<br>
<br>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 = input.dup or _input. Doing _input=input.save() could help me there.<br>
<br>Also p.7:<br><br>"So a random access range extends different concepts, depending on its finiteness."<br><br>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.<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 smile :-)<br><br>p.9:<br><br>"Other, more exotic range capabilities are primitives such as <tt>lookahead</tt> or <tt>putback</tt>."<br>
<br>I'd have liked to have lookahead sometimes...<br>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?<br><br>p. 10:<br>
<br>"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."<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 may be a bit too pretentious.<br>
<br>p. 10:<br><br>"As a rule, a higher-order range must offer the highest capability that it can, subject to what the original range can offer."<br><br>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...<br>
<br>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 will 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.<br>
<br>p. 10:<br>"If all contained ranges offer random access <em>and</em> length, then <tt>Chain</tt> offers random access as well."<br><br>Yes, but it's an 'if', not an 'iff'. I was bitten by this. A common test range for me was:<br>
<br>auto c = 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'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!<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>"I happen to think that <tt>bring_to_front</tt> would be a much more intuitive name than <tt>rotate</tt>."<br><br>Indeed. rotate would be something like:<br><br>auto rotate(R)(size_t n, R range) {<br>
returns chain(range[n..$], range[0..n]); // for a random-access range.<br>}<br><br>rotate(3, [0,1,2,3,4,56][]) -> [3,4,5,6,0,1,2][]<br><br>p.12:<br><br>"Fortunately, this problem is easily solved by defining a new range type, <tt>Until</tt>. <tt>Until</tt> is a range that takes another 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() == v</tt> (or at the natural end of <tt>r</tt> if <tt>v</tt> is not to be found). Lazy computation for the win!"<br>
<br>Nice. Is Until part of std.algo? (Gosh, this module is so big I can'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't know if that's really one) is for higher-order ranges that produce/contains two or more ranges.<br>
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<br><br>auto separate(alias pred, R) (R range) {<br> 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 index) method: front(0) returns subrange_0's front, front(1) for the second one and so on...<br>
<br> Philippe<br><br></div></div>