www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - "isDroppable" range trait for slicing to end

reply "monarch_dodra" <monarchdodra gmail.com> writes:
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...
Oct 29 2012
next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
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...
Oct 29 2012
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
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?
Oct 29 2012
prev sibling next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
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
Oct 29 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Oct 29 2012
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
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
Oct 29 2012
prev sibling next sibling parent reply "Peter Alexander" <peter.alexander.au gmail.com> writes:
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
Oct 29 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Oct 29 2012
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
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


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)

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]"?

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);"

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
Oct 29 2012
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
10/30/2012 6:53 AM, monarch_dodra пишет:
 On Monday, 29 October 2012 at 19:20:34 UTC, Dmitry Olshansky wrote:
 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)

Not *that* theoretical when you think about it. ascii's "digits" etc are all immutable ranges. They are a bad example, because they are strings (ergo un-sliceable), but as a rule of thumb, any global container can be saved as an immutable range. For example, I could define "first 10 integers" as an immutable range. That range would be slice-able, but would not verify "hasSlicing".

it. Ranges are means of iteration, they are mutable by the very definition - every time you call popFront/popBack iteration state *changes*. So you can't pop first item of "first 10 integers". It's an immutable entity that you can't manipulate. In that sense slicing such an entity (container) is the way of extracting a _mutable_ range from it. Yet numbers it cycles through are immutable.
 --------
 The way I see it, maybe a beter solution would be a refinement of:

 *hasSlicing:
 **r = r[0 .. 1]; MUST work (so infinite is out)
 *hasEndSlicing
 **r = r[1 .. $]; Must work (intended for infinite, or to verify opDollor)

I suggest to stop there. In other words introduce hasEndSlicing (awful name) and check self-assignabliity of both.
 To which we could add "limited" variants: "hasLimitedSlicing" and
 "hasLimitedEndSlicing", which would *just* mean we can extract a slice,
 but not necessarily re-assign it.

This repeats the same argument of extractSlice albeit differently.
 This seems like a simple but efficient solution. Thoughts?

It's not simple. I suggest we drop the no self-assignable slicing altogether. I claim that *if* you can't self assign a slice of a range it basically means that you are slicing something that is not meant to be a range but rather a container (adapter etc.).
 --------
 The issue that I still have with slicing (between to indexes) infinite
 ranges is that even on an implementation stand point, it makes little
 sense. There is little other way to implement it other than "return
 this[i .. $].takeExactly(j - i);" In which case, it would make little
 sense to require it as a primitive.

- Infinite range just plain can't support slicing on 2 indexes (they have limited slicing, or one side slicing not full slicing) It's just I suggested to exclude opSlice(x,y) from primitives unlike in my first post where I didn't think of solving self-assigning problem.
 I'd rather have a global function in range.d, that would provide the
 implementation for any infinite range that provides has[Limited]EndSlicing.

-- Dmitry Olshansky
Oct 30 2012
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
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
Oct 29 2012
prev sibling next sibling parent "Peter Alexander" <peter.alexander.au gmail.com> writes:
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...
Oct 29 2012
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
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

The only point he contested was the optimization opportunities in std.algorithm. 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) -------- 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? - 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]"? And still, that'd be if anybody actually used opDollar... *cough* -------- The solution I'm proposing barely requires anything new we don't already have (popFrontN). 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);" **Extract a slice, but with the explicit notion you *won't* get back-assignability "auto myNewSlice = r.extractSlice(0, 10);" 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...
Oct 29 2012
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Monday, 29 October 2012 at 19:20:34 UTC, Dmitry Olshansky 
wrote:
 [SNIP]

I'll need some time to fully digest your points. Thank you for the full reply. I'd like Jonathan's opinions on this too, he is knee deep in hasSlicing right now...
Oct 29 2012
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Monday, October 29, 2012 20:26:38 Dmitry Olshansky wrote:
 Need to ping Jonathon about it and work out something.

I believe that Microsoft did something stupid with one of their functions which makes it function slightly differently around a DST switch on Windows 8 than it used to, so the unit tests fail when verifying that the times come out correctly around a DST switch (since they don't anymore on Windows 8). But I haven't had time yet to thoroughly investigate what exactly is causing it. Microsoft definitely sucks when it comes to time-handling stuff, but they're usually better about backwards compatibility than they appear to have been here. - Jonathan M Davis
Oct 29 2012
prev sibling next sibling parent Jens Mueller <jens.k.mueller gmx.de> writes:
Jonathan M Davis wrote:
 On Monday, October 29, 2012 20:26:38 Dmitry Olshansky wrote:
 Need to ping Jonathon about it and work out something.

I believe that Microsoft did something stupid with one of their functions which makes it function slightly differently around a DST switch on Windows 8 than it used to, so the unit tests fail when verifying that the times come out correctly around a DST switch (since they don't anymore on Windows 8). But I haven't had time yet to thoroughly investigate what exactly is causing it. Microsoft definitely sucks when it comes to time-handling stuff, but they're usually better about backwards compatibility than they appear to have been here.

I find it amazing how many bugs your unittests catch. Jens
Oct 29 2012
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Monday, October 29, 2012 21:56:36 Jens Mueller wrote:
 I find it amazing how many bugs your unittests catch.

That's why they're there. It's far too easy to miss a corner case and end up with mostly working but still buggy code (especially with date/time stuff). At one point, I had a bug with B.C. years that ended in 99 that I only caught when I made some of the tests more thorough. Being thorough seems to be the only way to catch all those sorts of problems. And in spite of all of that, I've still had a bug or two in the calculations when it was merged into Phobos (long since fixed). DST switches are particularly nasty though, particularly since Microsoft absolutely sucks at time stuff, including the fact that it has a pitifully small number of time zones, and most of them are wrong. Testing that stuff across platforms is a major PITA, but I've tried very hard to guarantee that the behavior is the same across systems. Unfortunately, it looks like I'm going to have to spend some time figuring out how to hack around Windows 8's stupidity though. - Jonathan M Davis
Oct 29 2012
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Monday, 29 October 2012 at 19:20:34 UTC, Dmitry Olshansky 
wrote:
 **Extract a slice, but with the explicit notion you *won't* get
 back-assignability "auto myNewSlice = r.extractSlice(0, 10);"


That's just UFCS, not another primitive.
 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)

Yes, that's a good point.
 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)

Not *that* theoretical when you think about it. ascii's "digits" etc are all immutable ranges. They are a bad example, because they are strings (ergo un-sliceable), but as a rule of thumb, any global container can be saved as an immutable range. For example, I could define "first 10 integers" as an immutable range. That range would be slice-able, but would not verify "hasSlicing". -------- The way I see it, maybe a beter solution would be a refinement of: *hasSlicing: **r = r[0 .. 1]; MUST work (so infinite is out) *hasEndSlicing **r = r[1 .. $]; Must work (intended for infinite, or to verify opDollor) To which we could add "limited" variants: "hasLimitedSlicing" and "hasLimitedEndSlicing", which would *just* mean we can extract a slice, but not necessarily re-assign it. This seems like a simple but efficient solution. Thoughts? -------- The issue that I still have with slicing (between to indexes) infinite ranges is that even on an implementation stand point, it makes little sense. There is little other way to implement it other than "return this[i .. $].takeExactly(j - i);" In which case, it would make little sense to require it as a primitive. I'd rather have a global function in range.d, that would provide the implementation for any infinite range that provides has[Limited]EndSlicing.
Oct 29 2012
prev sibling next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, October 29, 2012 15:33:00 monarch_dodra wrote:
 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.

As already pointed out, this is solved by opDollar. We don't have a trait for it, but it can be tested for easily enough by doing something like typeof(is(r[0 .. $])) or __traits(compiles, r[0 .. $]). We may still want to create a trait for it though (e.g. hasOpDollar).
 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.

They can do so already, and if UFCS is used, then their version will be used. We _could_ go a step further and make it so that popFrontN calls a range's popFrontN if it has one to make it so that it's always used if it exists. The main problem is that you can't rely on the complexity of popFrontN being better than O(n), because that's what it's going to be with non-sliceable ranges. A trait such as isDroppable would fix that, but it's really only an issue with infinite ranges. Finite ranges which could have n elements popped in O(1) would be sliceable anyway, meaning that popFrontN would be O(1) for them already and that if a function requires popping n elements in O(1), it can just slice the range. So, isDroppable buys us nothing for finite ranges. The only gain that I really see here is that it would provide a way for infinite ranges to pop off their first n elements and still be infinite. As it stands, the best that you can do is slice them, but that has to result in another range type, because a finite slice can't be infinite. However, if we take advantage of opDollar, then I think we can solve the problem that way. By using opDollar when slicing an infinite range, you should be able to keep the original range type. That being the case, I don't think that isDroppable is really necessary. Howevere, it _does_ mean that I should probably adjust my pull for hasSlicing so that it tests that slicing an infinite range with opDollar returns the original type (assuming that opDollar compiles for it). Of course, once opDollar works (I don't know what it's current state is), it would be desirable to require it to work with slicing anyway, so maybe hasSlicing should have that requirement added at a later date. - Jonathan M Davis
Oct 30 2012
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
10/31/2012 4:48 AM, Jonathan M Davis пишет:
 On Monday, October 29, 2012 15:33:00 monarch_dodra wrote:
 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.

As already pointed out, this is solved by opDollar. We don't have a trait for it, but it can be tested for easily enough by doing something like typeof(is(r[0 .. $])) or __traits(compiles, r[0 .. $]). We may still want to create a trait for it though (e.g. hasOpDollar).

I just wanted to point out that we may as well require all RA ranges to have opDollar. Finite already have length, infinite would have marker. Just need some migration path so that current RA won't lose their title over night. [snip]
 Finite ranges which could have n elements popped in O(1) would be sliceable
 anyway, meaning that popFrontN would be O(1) for them already and that if a
 function requires popping n elements in O(1), it can just slice the range. So,
 isDroppable buys us nothing for finite ranges. The only gain that I really see
 here is that it would provide a way for infinite ranges to pop off their first
n
 elements and still be infinite. As it stands, the best that you can do is slice
 them, but that has to result in another range type, because a finite slice
 can't be infinite.

Yes, the whole argument started with infinite ranges.
 However, if we take advantage of opDollar, then I think we can solve the
 problem that way. By using opDollar when slicing an infinite range, you should
 be able to keep the original range type. That being the case, I don't think
 that isDroppable is really necessary.

I said elsewhere I have feeling that hasSlicing should really check for x = x[a..b]; Whereas for infinite ranges we need a weaker trait isDropable/hasSlicingToEnd(??): x = [a..$];
 Howevere, it _does_ mean that I should
 probably adjust my pull for hasSlicing so that it tests that slicing an
 infinite range with opDollar returns the original type (assuming that opDollar
 compiles for it). Of course, once opDollar works (I don't know what it's
 current state is), it would be desirable to require it to work with slicing
 anyway, so maybe hasSlicing should have that requirement added at a later
 date.

Indeed, alternatively we can check for both hasSlicing and isInfinite. Then in case of Infinite = true slicing only works up to $, this could be a better idea. -- Dmitry Olshansky
Oct 31 2012
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
10/31/2012 10:37 AM, monarch_dodra пишет:
 On Wednesday, 31 October 2012 at 08:58:18 UTC, Jonathan M Davis wrote:
 I agree, but for that to be realistic, I think that issue# 7177 needs
 to be
 implemented first. You should check out the pull request that I have for
 improving hasSlicing. I just updated it according to some of the
 discussion
 here, and it now checks the behavior of opDollar when it works with
 the range
 being sliced. For finite ranges, it essentially enforces that they
 function
 like arrays do, and for infinite ranges, it comes as close to that as
 it can:

 https://github.com/D-Programming-Language/phobos/pull/854

 As of the latest state of that pull request, hasSlicing looks like

 template hasSlicing(R)
 {
     enum bool hasSlicing = !isNarrowString!R && is(typeof(
     (inout int _dummy=0)
     {
         R r = void;

         static if(isInfinite!R)
             typeof(take(r, 1)) s = r[1 .. 2];
         else
             R s = r[1 .. 2];

         s = r[1 .. 2];

         static if(is(typeof(r[0 .. $])))
         {
             R t = r[0 .. $];
             t = r[0 .. $];

             static if(!isInfinite!R)
             {
                 R u = r[0 .. $ - 1];
                 u = r[0 .. $ - 1];
             }
         }

         static assert(isForwardRange!(typeof(r[1 .. 2])));
         static assert(hasLength!(typeof(r[1 .. 2])));
     }));
 }


 - Jonathn M Davis

I'm not a huge fan of the "opDollar" check, because essentially, it doesn't really buy you anything: if hasSlicing!R, then is "r = r[1..$]" legal? Who knows! You as a developer need to check manually that "r[0 .. $]" is legal first anyways...

That's a temporary thing because otherwise it'll break all of current RA. The idea is that if there is $ then it's tested
 Under those circumstances, why not cleanly splice the two notions?

 //----
 template hasSlicing(R)
 {
      enum bool hasSlicing = !isNarrowString!R && is(typeof(
      (inout int _dummy=0)
      {
          R r = void;

          static if(isInfinite!R)
              typeof(take(r, 1)) s = r[1 .. 2];
          else
              R s = r[1 .. 2];

          s = r[1 .. 2];

          static assert(isForwardRange!(typeof(r[1 .. 2])));
          static assert(hasLength!(typeof(r[1 .. 2])));
      }));
 }

 template hasSlicingToEnd(R)
 {
      enum bool hasSlicingToEnd = !isNarrowString!R && is(typeof(
      (inout int _dummy=0)
      {
          R r = void;

          static if(is(typeof(r[0 .. $])))
          {
              R t = r[0 .. $];
              t = r[0 .. $];

              static if(!isInfinite!R)
              {
                  R u = r[0 .. $ - 1];
                  u = r[0 .. $ - 1];
              }
          }
      }));
 }
 //----

 IMO, this makes a clean distinction between both "types" of slicing. An
 added bonus is that (for now) it also correctly supports finite RA
 ranges that don't define opDollar.

Jonathon's version also supports RA without opDollar.
 //----
 PS: Do we really have to force that infinite slice to be of a type of
 "take"? Does that mean we can't imagine an infinite range that defines
 it's own finite slice type?

 if we change the code to:

 //----
          static if(isInfinite!R)
              auto s = r[1 .. 2]; //HERE1
          else
              R s = r[1 .. 2];

          s = r[1 .. 2]; //HERE2
 //----

 Then we force nothing on the slice's type (HERE1), but do verify that
 subsequent slices will be assignable back to the original slice (HERE2)...

Well I'd rather never check that infinite range has 1..2 form of slicing to begin with. If we have some that do then we'd have to keep it. -- Dmitry Olshansky
Oct 31 2012
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
----
On Tuesday, 30 October 2012 at 17:49:20 UTC, Dmitry Olshansky
wrote:
 10/30/2012 6:53 AM, monarch_dodra пишет:
 Not *that* theoretical when you think about it. ascii's 
 "digits" etc are
 all immutable ranges. They are a bad example, because they are 
 strings
 (ergo un-sliceable), but as a rule of thumb, any global 
 container can be
 saved as an immutable range.
 For example, I could define "first 10
 integers" as an immutable range. That range would be 
 slice-able, but
 would not verify "hasSlicing".

range over it. Ranges are means of iteration, they are mutable by the very definition - every time you call popFront/popBack iteration state *changes*. So you can't pop first item of "first 10 integers". It's an immutable entity that you can't manipulate. In that sense slicing such an entity (container) is the way of extracting a _mutable_ range from it. Yet numbers it cycles through are immutable.

Yes, that is quite true. Although in this case, the slice is both container and range.
 --------
 The way I see it, maybe a beter solution would be a refinement 
 of:

 *hasSlicing:
 **r = r[0 .. 1]; MUST work (so infinite is out)
 *hasEndSlicing
 **r = r[1 .. $]; Must work (intended for infinite, or to 
 verify opDollor)

I suggest to stop there. In other words introduce hasEndSlicing (awful name) and check self-assignabliity of both.
 To which we could add "limited" variants: "hasLimitedSlicing" 
 and
 "hasLimitedEndSlicing", which would *just* mean we can extract 
 a slice,
 but not necessarily re-assign it.

This repeats the same argument of extractSlice albeit differently.

Well, in my mind, the argument was the opposite, it would mean you'd be able to write r[i..j] simply (as opposed to r.extractSlice(i, j)).
 This seems like a simple but efficient solution. Thoughts?

It's not simple. I suggest we drop the no self-assignable slicing altogether. I claim that *if* you can't self assign a slice of a range it basically means that you are slicing something that is not meant to be a range but rather a container (adapter etc.).

That *would* make things simpler. I guess that's a good way of seeing it. ---- On Wednesday, 31 October 2012 at 04:53:00 UTC, Jonathan M Davis wrote:
 As already pointed out, this is solved by opDollar. We don't 
 have a trait for
 it, but it can be tested for easily enough by doing something 
 like
 typeof(is(r[0 .. $])) or __traits(compiles, r[0 .. $]). We may 
 still want to
 create a trait for it though (e.g. hasOpDollar).

In my defense, I started thinking about this back when opDollar didn't work at all.
 However, if we take advantage of opDollar, then I think we can 
 solve the
 problem that way. By using opDollar when slicing an infinite 
 range, you should
 be able to keep the original range type. That being the case, I 
 don't think
 that isDroppable is really necessary.

Yes, in that context, that would also work (but had not thought of this). BTW: Once you are done, maybe you could present here what it means exactly to be slice-able? AFAIK, your current proposal allows for infinite ranges to verify "hasSlicing", if they can be sliced between [a ... b], whereas Dmitry seems to think that should not be so. At all. ---- Well in conclusion, sorry to have brought a crappy solution :/ I guess we had something simple all along... ---- Whilst were on the subject of opDollar, and how it can solve all of our problems, could one of you two maybe answer the questions in this thread? http://forum.dlang.org/thread/ehywdvmcmgyawgzfpytn forum.dlang.org
Oct 31 2012
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, October 31, 2012 08:13:08 monarch_dodra wrote:
 BTW: Once you are done, maybe you could present here what it
 means exactly to be slice-able? AFAIK, your current proposal
 allows for infinite ranges to verify "hasSlicing", if they can be
 sliced between [a ... b], whereas Dmitry seems to think that
 should not be so. At all.

It works now, but I'm open to removing it, since it _is_ odd to be able to slice an infinite range and get a completely different type from out. opSlice with opDollar combined with take would give you the same effect: take(infRange[a .. $], b - a); But without at least having opSlice with opDollar, you'd be forced to use drop or popFrontN, which would be O(n) rather than O(1).
 Well in conclusion, sorry to have brought a crappy solution :/ I
 guess we had something simple all along...

Well, live and learn. It happens to us all from time to time. I'd forgotten about opDollar prior to this discussion (mostly because it wasn't working), and it's quite applicable to hasSlicing. - Jonathan M Davis
Oct 31 2012
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, October 31, 2012 12:37:10 Dmitry Olshansky wrote:
 I just wanted to point out that we may as well require all RA ranges to
 have opDollar. Finite already have length, infinite would have marker.
 Just need some migration path so that current RA won't lose their title
 over night.

I agree, but for that to be realistic, I think that issue# 7177 needs to be implemented first. You should check out the pull request that I have for improving hasSlicing. I just updated it according to some of the discussion here, and it now checks the behavior of opDollar when it works with the range being sliced. For finite ranges, it essentially enforces that they function like arrays do, and for infinite ranges, it comes as close to that as it can: https://github.com/D-Programming-Language/phobos/pull/854 As of the latest state of that pull request, hasSlicing looks like template hasSlicing(R) { enum bool hasSlicing = !isNarrowString!R && is(typeof( (inout int _dummy=0) { R r = void; static if(isInfinite!R) typeof(take(r, 1)) s = r[1 .. 2]; else R s = r[1 .. 2]; s = r[1 .. 2]; static if(is(typeof(r[0 .. $]))) { R t = r[0 .. $]; t = r[0 .. $]; static if(!isInfinite!R) { R u = r[0 .. $ - 1]; u = r[0 .. $ - 1]; } } static assert(isForwardRange!(typeof(r[1 .. 2]))); static assert(hasLength!(typeof(r[1 .. 2]))); })); } - Jonathn M Davis
Oct 31 2012
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 31 October 2012 at 08:58:18 UTC, Jonathan M Davis 
wrote:
 I agree, but for that to be realistic, I think that issue# 7177 
 needs to be
 implemented first. You should check out the pull request that I 
 have for
 improving hasSlicing. I just updated it according to some of 
 the discussion
 here, and it now checks the behavior of opDollar when it works 
 with the range
 being sliced. For finite ranges, it essentially enforces that 
 they function
 like arrays do, and for infinite ranges, it comes as close to 
 that as it can:

 https://github.com/D-Programming-Language/phobos/pull/854

 As of the latest state of that pull request, hasSlicing looks 
 like

 template hasSlicing(R)
 {
     enum bool hasSlicing = !isNarrowString!R && is(typeof(
     (inout int _dummy=0)
     {
         R r = void;

         static if(isInfinite!R)
             typeof(take(r, 1)) s = r[1 .. 2];
         else
             R s = r[1 .. 2];

         s = r[1 .. 2];

         static if(is(typeof(r[0 .. $])))
         {
             R t = r[0 .. $];
             t = r[0 .. $];

             static if(!isInfinite!R)
             {
                 R u = r[0 .. $ - 1];
                 u = r[0 .. $ - 1];
             }
         }

         static assert(isForwardRange!(typeof(r[1 .. 2])));
         static assert(hasLength!(typeof(r[1 .. 2])));
     }));
 }


 - Jonathn M Davis

I'm not a huge fan of the "opDollar" check, because essentially, it doesn't really buy you anything: if hasSlicing!R, then is "r = r[1..$]" legal? Who knows! You as a developer need to check manually that "r[0 .. $]" is legal first anyways... Under those circumstances, why not cleanly splice the two notions? //---- template hasSlicing(R) { enum bool hasSlicing = !isNarrowString!R && is(typeof( (inout int _dummy=0) { R r = void; static if(isInfinite!R) typeof(take(r, 1)) s = r[1 .. 2]; else R s = r[1 .. 2]; s = r[1 .. 2]; static assert(isForwardRange!(typeof(r[1 .. 2]))); static assert(hasLength!(typeof(r[1 .. 2]))); })); } template hasSlicingToEnd(R) { enum bool hasSlicingToEnd = !isNarrowString!R && is(typeof( (inout int _dummy=0) { R r = void; static if(is(typeof(r[0 .. $]))) { R t = r[0 .. $]; t = r[0 .. $]; static if(!isInfinite!R) { R u = r[0 .. $ - 1]; u = r[0 .. $ - 1]; } } })); } //---- IMO, this makes a clean distinction between both "types" of slicing. An added bonus is that (for now) it also correctly supports finite RA ranges that don't define opDollar. //---- PS: Do we really have to force that infinite slice to be of a type of "take"? Does that mean we can't imagine an infinite range that defines it's own finite slice type? if we change the code to: //---- static if(isInfinite!R) auto s = r[1 .. 2]; //HERE1 else R s = r[1 .. 2]; s = r[1 .. 2]; //HERE2 //---- Then we force nothing on the slice's type (HERE1), but do verify that subsequent slices will be assignable back to the original slice (HERE2)...
Oct 31 2012
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Wednesday, October 31, 2012 11:37:13 monarch_dodra wrote:
 IMO, this makes a clean distinction between both "types" of
 slicing. An added bonus is that (for now) it also correctly
 supports finite RA ranges that don't define opDollar.

I don' think that such a distinction should be made at all. I think that all sliceable ranges should be required to implement opDollar. The problem is that it's unreasonable to require that when opDollar just got fixed, and arguably issue# 7177 should be implemented before it's reasonable to require it. But regardless, that means that creating a trait to test for opDollar working doesn't make sense. It would just have to be thrown away later.
 PS: Do we really have to force that infinite slice to be of a
 type of "take"? Does that mean we can't imagine an infinite range
 that defines it's own finite slice type?

I think that it's more valuable to make it consistent. What would a separate finite type even buy you? It would just be doing what take would do. I do kind of like the idea of just disallowing slicing without opDollar on infinite ranges though, in which case you'd have to use take yourself. I don't know what Andrei's take would be on that though. - Jonathan M Davis
Oct 31 2012
prev sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 31 October 2012 at 18:40:09 UTC, Jonathan M Davis
wrote:
 On Wednesday, October 31, 2012 11:37:13 monarch_dodra wrote:
 IMO, this makes a clean distinction between both "types" of
 slicing. An added bonus is that (for now) it also correctly
 supports finite RA ranges that don't define opDollar.

I don' think that such a distinction should be made at all. I think that all sliceable ranges should be required to implement opDollar. The problem is that it's unreasonable to require that when opDollar just got fixed, and arguably issue# 7177 should be implemented before it's reasonable to require it. But regardless, that means that creating a trait to test for opDollar working doesn't make sense. It would just have to be thrown away later.
 PS: Do we really have to force that infinite slice to be of a
 type of "take"? Does that mean we can't imagine an infinite 
 range
 that defines it's own finite slice type?

I think that it's more valuable to make it consistent. What would a separate finite type even buy you? It would just be doing what take would do. I do kind of like the idea of just disallowing slicing without opDollar on infinite ranges though, in which case you'd have to use take yourself. I don't know what Andrei's take would be on that though. - Jonathan M Davis

You are probably right. I think I've had my head too deep inside algorithm implementation detail, and got my focus on the wrong things. Most of the theoretical ranges I'm trying to support probably don't exist in real life anyways :/ Might as well keep things consistent.
Nov 01 2012