"isDroppable" range trait for slicing to end

[Dmitry Olshansky]

10/29/2012 5:40 PM, monarch_dodra пишет:
> On Monday, 29 October 2012 at 15:48:47 UTC, Andrei Alexandrescu wrote:
>> On 10/29/12 11:43 AM, monarch_dodra wrote:
>>>
>>> I think you missed the point
>>
>> ... which I think Dmitry destroyed.
>>
>> Andrei
>
I'd clarify that I'm not against the _trait_ itself. isDroppable.
The name doesn't sit well with me but the idea to test if range supports 
limited form of slicing i.e. a[x..$]  is a good idea.
I'd call it limited slicing or one-side slicing.

Everything else in the post - a distinctive no.

> The only point he contested was the optimization opportunities in
> std.algorithm.
>

That was an observation. I'm curious how many things you can sensibly do 
with infinite range directly (no take, takeExactly) that would benefit 
from being able to iterate them by common index. I have reasons to 
believe the set is small at best.

> I agree that optimization opportunities are not enough to warrant new
> concepts, but that wasn't my main point. But they are there is what I
> was saying.
>
> (PS: There is currently a pull request for making copy exploit doubly RA
> ranges)
Yeah, that's mine...

Now the challenge.
Quick! How many infinite RA ranges with assignable elements we have in 
Phobos presently?

> --------
> My main point is that slicing a range to its end *is* something
> important, and we currently have nothing to provide this functionality,
> when we could (easily).
>
> The argument: "I'm thinking that simply defining an opDollar to return
> special marker type and overloading opSlice should work", works, but
> brings its own issues to the table.
>
> Inside template code, it would render hasSlicing *even more* complex: If
> an infinite range indeed has slicing, then what exactly does it mean?

Basically it wasn't defined precisely. And I don't see how problematic 
it is to refine the definition.

> - Does it mean you can slice between two indexes?
> - Does it guarantee you can slice to the end with opDollar?
> - Does it mean you can do both?
> - Would it imply that "r[0 .. 1]" would have a different type from "r[0
> .. $]" ?;
> - Would it imply that "r = r[0 .. $]" is legal?
> - What about that "r = r[0 .. 10]"?
>
I'll comment more on these at the bottom. The gist is:

All of this boils down to one question adding a popFrontN can't solve: 
semantics of slicing an Infinite range on 2 indexes. Everything else is 
trivial to nail down.

> And still, that'd be if anybody actually used opDollar... *cough*

Introducing a new hook for programmers to implement because currently 
opDollar isn't used (and I told you why) is a bad idea. It is making a 
new *convention* that is bypassing an existing one built-in into the 
language.

> --------
> The solution I'm proposing barely requires anything new we don't already
> have (popFrontN).

It requires something new from users. Implement another way to slice a 
range. While presently popFrontN already works in O(1) for stuff that 
has [x..$] slicing.
Put it another way: library solutions arenice and usable as long as it 
blends with the core language. Let's not repeat the (few) mistakes of STL.

>
> I'm saying we can exploit the existence of this method to clearly
> separate the two (currently conflicting) notions of slicing we currently
> have:
>
> *On one hand, we can have the "hasSlicing" ranges, where can clearly
> write "r = r[0 .. 10];" any day of the week, no matter the range.
>
> *On the other end, we'd have "isDroppable", which would give you two
> limited features for those ranges that don't satisfy hasSlicing:
> **Slice to end with guaranteed assignability to original "r = r.drop(10);"

So all of the above can be put into the following 2 statements:
- all RA ranges have $ that is the end of range
- a slice is self-assignable in any case
- Infinite range just plain can't support slicing on 2 indexes (they 
have limited slicing, or one side slicing not full slicing)

I'd argue that any RA range can support slicing simply because 
supporting popFront/popBack is required. I believe there are no 
precedents where implementing these won't avail to:
a) adding a start, end indexes on top of the underlying RA payload
b) using some kind of random access pointer(s) provided natively

For Infinite ranges hasSlicing is false, limitedSlicing (isDropable) is 
true.

So I suggest we make the function popFrontN more clever w.r.t infinite 
ranges with limited form of slicing. That's all. And you are correct to 
notice it's misses an optimization in this case. And the constraint 
should be fixed to isDroppable/limitedSlicing.

It's a losing battle to add fixed range slicing to InfiniteRange.
Arguably for infinite ranges the way to slice is:
a[x..y] ---> a.drop(x).takeExactly(y-x)

Because it doesn't have full slicing that is hasSlicing. Clear as a day.
Note that drop(x) will get the speed up.

> **Extract a slice, but with the explicit notion you *won't* get
> back-assignability "auto myNewSlice = r.extractSlice(0, 10);"
>
Another primitive or is that UFCS in the work? Now when to use it? I'd 
hate to see everything turning from
a[x..y]
to
a.extractSlice(x, y)
in generic code. Just because a lot of code doesn't need a slice to have 
the exact same type.
(I'm just following the simple rule of generic programming: if you don't 
require something - avoid using it)

> Note that this "extractSlice" notion would save a bit of functionality
> for immutable ranges which *would* have slicing, but since they don't
> support assign, don't actually verify hasSlicing...

immutable ranges is purely a theoretical notion. (immutable elements are 
on the contrary are ubiquitous)

-- 
Dmitry Olshansky