<div class="gmail_quote">On Tue, Jul 27, 2010 at 15:48, Andrei Alexandrescu <span dir="ltr"><<a href="mailto:SeeWebsiteForEmail@erdani.org" target="_blank">SeeWebsiteForEmail@erdani.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><br></div><div>
Another thing, though I'm not sure it's a good idea, it to have them define an opIndex[ElementType!R e], that would just either forward to .find() or do a simple binary search by itself: O(lg(n)) is quite good.<br>
Yeah, isAssociativeRange!R ;)<br>
But that's blurring the line between container and range, I guess.<br>
</div></blockquote>
<br>
One issue is dealing with sorted random-access ranges of size_t. Then there's ambiguity - which [] did you mean, searching on straight indexing?<div><br></div></blockquote><div><br></div><div>You're right. And I cannot discard the notion of size_t ranges, because ranges of indices are quite useful.</div>
<div>OK, carry on.</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
In the same vein, a sorted range could optionally define opIn_r that also promises O(lg(n)) complexity.<br>
</blockquote>
<br></div>
This is a strong argument for putting sorted range functionality inside Sorted!Range.<div><br></div></blockquote><div><br></div><div> agree. Does that also means that in that case, an algorithm trying to determine if its argument range is sorted will not use compile-time duck typing, with a isSortedRange!R, but will just see if the input is a Sorted!T?</div>
<div><br></div><div>In that case, indicate quite clearly in Sorted docs that if the user knows a range is sorted, then she really ought to wrap it in Sorted.</div><div><br></div><div>Anyway, Sorted will be an interesting example of a wrapper struct that transmits type-encoded information, like I wanted to have. Seeing how it works in practice will be interesting. It's really a way to provide at compile-time information on the (runtime) values.</div>
<div><br></div><div>Though what I wanted is a proper subtype, whereas in Sorted!R case, Sorted is parallel to R, but due to the duck typing used everywhere, it will get along. </div><div>I'm making any sense there?</div>
<div><br></div><div><br></div><div>As a little brother to Sorted, you could have Bounded!R, that signifies the ranges values won't take all possible values of their element type: a range producing doubles, but all positive, for example, or a char range with all values in the 'a'-'z' range...</div>
<div>Exposed methods: minBound, maxBound</div><div><br></div><div>These do not tell you what is the max or the min of the range, they may not even exist if the range is infinite. It just tell you that all values will be between minBound and maxBound)</div>
<div>Filter may be enough for this, but it's complicated to extract the min and max values.</div><div><br></div><div>Another one I like is Periodic... (or, Cyclic). Right now, some of my algorithms, like rotateWhile!predicate(range) detect Cycle!R and Repeat!R and deal with it accordingly. </div>
<div>I do not want</div><div><br></div><div>rotateWhile!"a<6"(cycle([0,1,2,3])) </div><div><br></div><div>to rotate without stopping. </div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
As for taking ideas from other languages: in Clojure, data structures for which it makes sense (maps, sets?) are functions of their element and return true if the provided value is in the structure. That allows one to use them as predicate for finding and such, which makes for very clean code, as they also have encoded literal values.<br>
</blockquote>
<br></div>
Not getting it, could you please expand/insert a link?</blockquote><div><br></div><div><br></div><div><a href="http://clojure.org/data_structures">http://clojure.org/data_structures</a> (maps are functions of their keys, sets are functions of their elements)</div>
<div><br></div><div>and</div><div><br></div><div><a href="http://clojure.org/sequences">http://clojure.org/sequences</a></div><div><a href="http://clojure.org/data_structures"></a> </div><div><div>That will fail in D, due to your remark on range with size_t elements that prevents using opIndex to make a range an associative range. But the idea is that if you want to filter a sequence to find all vowels for example:</div>
<div><br></div><div>auto vowels = set("aeiou");</div><div>auto vowelsInMyText = filter!vowels(myText);</div><div><br></div><div>vowels act as a predicate: if you call it with a char, it will returns true iff the char is in vowels. In Clojure, it produces very clean code. I guess in D, you'd do:</div>
<div><br></div><div>auto vowelsInMyText!((dchar d) { return d in vowels;})(myText);</div><div><br></div><div>or even:</div><div><br></div><div>auto vowelsInMyText = filter ! q{a in assumeSorted("aeiou")} (myText); </div>
</div><div><br></div><div>And I just convinced myself that the D way is good enough :)</div><div><br></div><div><br></div><div>Philippe</div><div><br></div></div><br>