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.

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.

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.


--------
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.

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:

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.

--------
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...

On Monday, 29 October 2012 at 14:33:01 UTC, monarch_dodra wrote:
> [SNIP]

Extension:

An extension to this proposal, is the function "extractSlice".
This function would *ONLY* require isDroppable. It would be
implemented as:

//----
auto extractSlice(R)(R r, size_t i, size_t j)
{
     static if (hasSlicing)
         return r[i .. j];
     else
         return r.drop(i).takeExactly(j - i);
}
//----

What makes this notion interesting, is that it works both on
sliceable ranges AND infinite ranges, but does not pretend to
have back-assignement to the original range. This is very
interesting, because it would allow "hasSlicing" to turn down
infinite ranges, but we'd still have a way to extract a range out
of those infinite ranges.

Another added bonus would be that certain non-infinite ranges, in
particular immutable ranges, are considered not-sliceable,
because they can't be back-assignabe. extractSlice would allow us
to extract a slice out of those ranges, even if we can't assign
them back...

On Monday, 29 October 2012 at 14:34:04 UTC, monarch_dodra wrote:
> [SNIP]

I have a preliminary Pull Request to illustrate my point here:
https://github.com/D-Programming-Language/phobos/pull/908

Currently, I only added popFrontN on the ranges on which it is most obvious, you should get the point.

----
I'm very sorry if I'm not very clear. Explaining thingsby writing is not my strong suit. What would you think of this proposal?

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

On Monday, 29 October 2012 at 14:33:01 UTC, monarch_dodra wrote:
> I'd like to introduce a new primitive: "popFrontN".

http://dlang.org/phobos/std_range.html#popFrontN

On Monday, 29 October 2012 at 15:41:23 UTC, Peter Alexander wrote:
> On Monday, 29 October 2012 at 14:33:01 UTC, monarch_dodra wrote:
>> I'd like to introduce a new primitive: "popFrontN".
>
> http://dlang.org/phobos/std_range.html#popFrontN

> On Monday, 29 October 2012 at 14:33:01 UTC, monarch_dodra wrote:
> You may recognize this as a standalone function if range.d

I think you missed the point

On Monday, 29 October 2012 at 15:43:47 UTC, monarch_dodra wrote:
> On Monday, 29 October 2012 at 15:41:23 UTC, Peter Alexander wrote:
>> On Monday, 29 October 2012 at 14:33:01 UTC, monarch_dodra wrote:
>>> I'd like to introduce a new primitive: "popFrontN".
>>
>> http://dlang.org/phobos/std_range.html#popFrontN
>
>> On Monday, 29 October 2012 at 14:33:01 UTC, monarch_dodra wrote:
>> You may recognize this as a standalone function if range.d
>
> I think you missed the point

Correct. Sorry about that :-)

Carry on...

On 10/29/12 11:43 AM, monarch_dodra wrote:
> On Monday, 29 October 2012 at 15:41:23 UTC, Peter Alexander wrote:
>> On Monday, 29 October 2012 at 14:33:01 UTC, monarch_dodra wrote:
>>> I'd like to introduce a new primitive: "popFrontN".
>>
>> http://dlang.org/phobos/std_range.html#popFrontN
>
>> On Monday, 29 October 2012 at 14:33:01 UTC, monarch_dodra wrote:
>> You may recognize this as a standalone function if range.d
>
> I think you missed the point

... which I think Dmitry destroyed.

Andrei

On 10/29/12 3:14 PM, Dmitry Olshansky wrote:
[snip]

3:14 PM? Since you're in the future, please let me know when the market opens :o).

Andrei

29/10/2012 15:50, Andrei Alexandrescu пишет:
> On 10/29/12 3:14 PM, Dmitry Olshansky wrote:
> [snip]
>
> 3:14 PM? Since you're in the future, please let me know when the market
> opens :o).

Just got Windows 8 Pro installed, my copy must have come with a time-machine addition. Need to read these feature charts more carefully next time :)

On a serious note I recall there is a problem with date/time functionality on Win8 that manifests itself as an assertion in std.datetime unittests.
Need to ping Jonathon about it and work out something.

-- 
Dmitry Olshansky