> 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. * ditto for .save() * Take(sortedRange, 5) should indicate it's also sorted. * The same for retro(sorted), but with a predicate being Not!pred (or something akin to this anyway) * filter ! predicate (sortedRange) is also sorted * stride etc, etc. > > > 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. Philippe