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
