<div class="gmail_quote"><br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class="im">Andrei Alexandrescu wrote:<br>
<br>
> I'm trying to find justifications for keeping assumeSorted and friends<br>
> within Phobos. Background: assumeSorted(r) where r is some range returns<br>
> a value that wraps r and clarifies to the caller that it can assume r<br>
> has been sorted.</div></blockquote><div> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class="im">> advantageous for sorted ranges. Question is: what are those? What kind<br>
> of cool primitives could a sorted range define?<br>
><br>
> Here are a few I can think of:<br>
><br>
> find -> uses binary search if random-access, or at least early stopping<br>
> otherwise.<br>
><br>
> minElement -> r.front<br>
><br>
> maxElement -> r.back<br>
><br>
> topN -> essentially does nothing<br>
><br>
> median -> r[r.length / 2]<br>
</div></blockquote><div><br>It's not exactly what you're asking for, but my first thought was: "propagation". When
you have a sorted range, it's rich, it's something you worked for to
get. You don't want to waste it. So higher-order ranges and some other functions should take care to propagate the information.<br>
<br>
* slicing a sorted range should produce a sorted range. so your wrapper range opIndex must be modified to account for this.<br>* ditto for .save()<br><br>
* Take(sortedRange, 5) should indicate it's also sorted.<br>
* The same for retro(sorted), but with a predicate being Not!pred (or
something akin to this anyway) <br>
* filter ! predicate (sortedRange) is also sorted<br>* stride<br>
etc, etc.<br>
<br><br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class="im">><br>
> Such functions could have free counterparts in std.algorithm. The free<br>
> functions check whether the range already implements the fast functions<br>
> and uses them transparently if present. So then we have e.g. find()<br>
> which works in linear time for most ranges, but logarithmic time on<br>
> random-access sorted ranges.<br>
><br></div></blockquote><div><br><br>* Warning, daydreaming ahead * <br><br></div></div>As a side note, I'm playing with a Graph struct. And (generic) trees are just graphs, statically speaking. I can encode trees as graphs. The only difference is at runtime: no loop, one ancestor per node, etc. So, it's a bit like the standard range/sorted range problem: in general, being sorted is a runtime property. Being able to define this at the type level is quite interesting and that's what your assumeSorted does.<br>
<br><br>But, in general, it would be nice to have a way to add flags/properties as side-cars to an input type. <br><br>something like:<br><br>struct WithProperty(Original, alias property)<br>{<br> Original _original;<br>
/+ insert here some alias this-like magic to make WithProperty melt into an Original and expose _original most of the time +/<br> /+ expose property (SortedBy!pred, ConvergesTo!someValue, etc) with an alias. <br>
}<br><br>Of course, it should be recursive: calling WithProperty on a WithProperty!(SomeType, OtherProperties) should add the new property to a CT-list, maybe a type-tuple.<br>And there should be a way to disable some properties. As I said before, filter ! pred (some sorted range) is sorted, so it should indicate it. But map ! fun (sorted range) is _not_ sorted in general, and should 'off' this particular property.<br>
<br>What you're doing is defining 'interfaces', a sort of CT duck-typing, and your constraints templates check for the presence or absence of those new functions. I now realize much of what I longed for could be encoded in this way. <br>
<br>* Convergence to a certain value => expose a .limit() primitive.<br>* every value in the range occupy a certain 'range', smaller than what allows ElementType!Range (constraining values between 0.0 and 1.0 for a double-producing range, for example) => expose minValue/maxValue methods. <br>
<br>OK, it's past midnight around here, tomorrow my daughters will want to jump in the Mediterranean for hours, again. I'll shut up and go to bed.<br><br><br>Philippe<br><br>