"isDroppable" range trait for slicing to end

[Dmitry Olshansky]

29/10/2012 14:33, monarch_dodra пишет:
> More often than not, we want to slice a range all the way to the end,
> and we have to use the clumsy "r[0 .. r.length]" syntax.

That supposed to be r[].

>
> What's worst is that when a range is infinite, there is no real way to
> "slice to the end", unless you just repeatedly popFront.

Slice to the end was meant to be this:
r[x..$]

>
> This is a real shame, because a lot of infinite ranges (sequence, cycle,
> repeat, ...) support random access, but not slice to end. They *could*
> slice to end if the language allowed it.

The real shame is a compiler bug that prevented $ from ever working 
except in a few special cases. (that and special meaning of length 
inside of []).

>
> --------
> I'd like to introduce a new primitive: "popFrontN". You may recognize
> this as a standalone function if range.d: It is. I propose we improve
> this semantic by allowing ranges to directly implement this function
> themselves. Then, popFrontN will defer to that function's
> implementation. This would allow certain infinite ranges (such as
> sequence) to provide a popFrontN implementation, even though they aren't
> sliceable.
>

Introducing new things as part of range definition (capability) is a 
costly move. Paying that cost to address a vague special case - not 
worth it.

>  From there, I'd like to introduce a new trait "isDroppable": This trait
> will answer true if a range naturally supports the popFrontN primitive
> (or is already sliceable).
>
> --------
> So what makes this so interesting? Not only does it give new performance
> possibilities, it also unlocks new possibilities for the implementation
> of algorithms:

Where? I thought it was about unlocking certain pattern for infinite RA 
ranges, not that much of benefit elsewhere.

> A LOT of algorithm take a special quick route when the input ranges are
> sliceable, random access, and hasLength. Blatant examples of this are
> "find", "copy", or as a general rule, anything that iterates on two
> ranges at once. The thing though is that they never actually *really*
> require sliceability, nor querying length. All they want is to be able
> to write "return r[i .. r.length]", but "return r.drop(i)" would work
> *just* as well.

Your drop(i) would still have to know length for anything finite.

TBH all stuff that is (if ever) specialized in std.algorithm:
a) tries to optimize with strings
b) tries to optimize with arrays
c) sometimes catches general RA or slicing

I'm pushing 2 things of c) type in one pull, yet I don't see it as a 
common thing at all, e.g. presently copy doesn't care about RA/slicing, 
only for built-in arrays.

Most of the time things are "downgraded" to Input/ForwardRange
and worked from that - simple, slow and generic.

> --------
> Another thing which makes this "isDropable" notion interesting is that
> the dropped range guarantees the returned range's type is that of the
> original ranges, unlike hasSlicing, which doesn't really guarantee it:
> some infinite ranges can be sliced, but the returned slice (obviously)
> is not infinite...

Interesting. I'm thinking that simply defining an opDollar to return 
special marker type and overloading opSlice should work:

struct InfRange{
...
EndMarker opDollar();
InfRange opSlice(size_t start, EndMarker dummy);
SomeOtherRangeType opSlice(size_t start, size_t end);
...
}

And if you omit second overload it doesn't have normal slicing.
isDropable then tests specifically slicing with dollar.

-- 
Dmitry Olshansky