Do sorted ranges have any special properties?

[Andrei Alexandrescu]

Philippe Sigaud wrote:
> 
>     Andrei Alexandrescu wrote:
> 
>      > I'm trying to find justifications for keeping assumeSorted and
>     friends
>      > within Phobos. Background: assumeSorted(r) where r is some range
>     returns
>      > a value that wraps r and clarifies to the caller that it can assume r
>      > has been sorted.
> 
>  
> 
>      > advantageous for sorted ranges. Question is: what are those? What
>     kind
>      > of cool primitives could a sorted range define?
>      >
>      > Here are a few I can think of:
>      >
>      > find -> uses binary search if random-access, or at least early
>     stopping
>      > otherwise.
>      >
>      > minElement -> r.front
>      >
>      > maxElement -> r.back
>      >
>      > topN -> essentially does nothing
>      >
>      > median -> r[r.length / 2]
> 
> 
> 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.
> 
> * slicing a sorted range should produce a sorted range. so your wrapper 
> range opIndex must be modified to account for this.

Cool, makes sense.

> * ditto for .save()

Yah.

> * Take(sortedRange, 5) should indicate it's also sorted.

Fortunately take already returns the type of the slice if the range 
supports slice, so that's in place already.

> * The same for retro(sorted), but with a predicate being Not!pred (or 
> something akin to this anyway)

Whoa, interesting.

> * filter ! predicate (sortedRange) is also sorted
> * stride
> etc, etc.

Yah... that is all cool. My only reservations are that with what we have 
right now this looks like a lot of manual special casing. By the way, 
chain() with ranges sorted with the same predicate is also sorted...

Then, such an effort would be much better motivated if sorted ranges had 
some really interesting properties. Aside from those discussed - there's 
not a lot of them!

>      > Such functions could have free counterparts in std.algorithm. The
>     free
>      > functions check whether the range already implements the fast
>     functions
>      > and uses them transparently if present. So then we have e.g. find()
>      > which works in linear time for most ranges, but logarithmic time on
>      > random-access sorted ranges.
>      >
> 
> 
> 
> * Warning, daydreaming ahead *
> 
> 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.
> 
> 
> But, in general, it would be nice to have a way to add flags/properties 
> as side-cars to an input type. 
> 
> something like:
> 
> struct WithProperty(Original, alias property)
> {
>      Original _original;
>      /+ insert here some alias this-like magic to make WithProperty melt 
> into an Original and expose _original most of the time +/
>      /+ expose property (SortedBy!pred, ConvergesTo!someValue, etc) with 
> an alias.
> }
> 
> 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.
> 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.
> 
> 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.
> 
> * Convergence to a certain value => expose a .limit() primitive.
> * 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.
> 
> 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.

Sounds like fun - of both the hacking and family kind. Keep those ideas 
coming, this is very interesting and something terse and usable could 
come out of it.


Andrei