View mode: basic / threaded / horizontal-split · Log in · Help
October 29, 2012
"isDroppable" range trait for slicing to end
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...
October 29, 2012
Re: "isDroppable" range trait for slicing to end
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...
October 29, 2012
Re: "isDroppable" range trait for slicing to end
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?
October 29, 2012
Re: "isDroppable" range trait for slicing to end
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
October 29, 2012
Re: "isDroppable" range trait for slicing to end
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
October 29, 2012
Re: "isDroppable" range trait for slicing to end
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
October 29, 2012
Re: "isDroppable" range trait for slicing to end
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...
October 29, 2012
Re: "isDroppable" range trait for slicing to end
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
October 29, 2012
Re: "isDroppable" range trait for slicing to end
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
October 29, 2012
Re: "isDroppable" range trait for slicing to end
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
« First   ‹ Prev
1 2 3
Top | Discussion index | About this forum | D home