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 reply "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
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 reply 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
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 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 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 "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
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 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 "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
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




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
Oct 29 2012
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 parent reply "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);"


 Another primitive or is that UFCS in the work?


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
parent reply 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".


You do make a common mistake of confusing a container and a 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.


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


Yup like I told:
- 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.


Maybe though the utility of such a helper is limited (pun intended).


-- 
Dmitry Olshansky
Oct 30 2012
parent reply "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".


 You do make a common mistake of confusing a container and a 
 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
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 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 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 reply 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.



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
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 31 October 2012 at 08:58:18 UTC, Jonathan M Davis 
wrote:


 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
next sibling 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:


 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 parent reply "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 

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

 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