Do sorted ranges have any special properties?

[Philippe Sigaud]

> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20100726/3fa7b865/attachment.html>