Do sorted ranges have any special properties?

[Philippe Sigaud]

On Tue, Jul 27, 2010 at 15:48, Andrei Alexandrescu <
SeeWebsiteForEmail at erdani.org> wrote:

>
>> Another thing, though I'm not sure it's a good idea, it to have them
>> define an opIndex[ElementType!R e], that would just either forward to
>> .find() or do a simple binary search by itself: O(lg(n)) is quite good.
>>  Yeah, isAssociativeRange!R  ;)
>> But that's blurring the line between container and range, I guess.
>>
>
> One issue is dealing with sorted random-access ranges of size_t. Then
> there's ambiguity - which [] did you mean, searching on straight indexing?
>
>
You're right. And I cannot discard the notion of size_t ranges, because
ranges of indices are quite useful.
OK, carry on.



>
>  In the same vein, a sorted range could optionally define opIn_r that also
>> promises O(lg(n)) complexity.
>>
>
> This is a strong argument for putting sorted range functionality inside
> Sorted!Range.
>
>
 agree. Does that also means that in that case, an algorithm trying to
determine if its argument range is sorted will not use compile-time duck
typing, with a isSortedRange!R, but will just see if the input is a
Sorted!T?

In that case, indicate quite clearly in Sorted docs that if the user knows a
range is sorted, then she really ought to wrap it in Sorted.

Anyway, Sorted will be an interesting example of a wrapper struct that
transmits type-encoded information, like I wanted to have. Seeing how it
works in practice will be interesting. It's really a way to provide at
compile-time information on the (runtime) values.

Though what I wanted is a proper subtype, whereas in Sorted!R case, Sorted
is parallel to R, but due to the duck typing used everywhere, it will get
along.
I'm making any sense there?


As a little brother to Sorted, you could have Bounded!R, that signifies the
ranges values won't take all possible values of their element type: a range
producing doubles, but all positive, for example, or a char range with all
values in the 'a'-'z' range...
Exposed methods: minBound, maxBound

These do not tell you what is the max or the min of the range, they may not
even exist if the range is infinite. It just tell you that all values will
be between minBound and maxBound)
Filter may be enough for this, but it's complicated to extract the min and
max values.

Another one I like is Periodic... (or, Cyclic). Right now, some of my
algorithms, like rotateWhile!predicate(range) detect Cycle!R and Repeat!R
and deal with it accordingly.
I do not want

rotateWhile!"a<6"(cycle([0,1,2,3]))

to rotate without stopping.



>
>  As for taking ideas from other languages: in Clojure, data structures for
>> which it makes sense (maps, sets?) are functions of their element and return
>> true if the provided value is in the structure. That allows one to use them
>> as predicate for finding and such, which makes for very clean code, as they
>> also have encoded literal values.
>>
>
> Not getting it, could you please expand/insert a link?



http://clojure.org/data_structures  (maps are functions of their keys, sets
are functions of their elements)

and

http://clojure.org/sequences
<http://clojure.org/data_structures>
That will fail in D, due to your remark on range with size_t elements that
prevents using opIndex to make a range an associative range. But the idea is
that if you want to filter a sequence to find all vowels for example:

auto vowels = set("aeiou");
auto vowelsInMyText = filter!vowels(myText);

vowels act as a predicate: if you call it with a char, it will returns true
iff the char is in vowels. In Clojure, it produces very clean code. I guess
in D, you'd do:

auto vowelsInMyText!((dchar d) { return d in vowels;})(myText);

or even:

auto vowelsInMyText = filter ! q{a in assumeSorted("aeiou")} (myText);

And I just convinced myself that the D way is good enough :)


Philippe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20100728/4a7ec330/attachment.html>