"isDroppable" range trait for slicing to end

monarch_dodra monarchdodra at gmail.com
Mon Oct 29 07:33:00 PDT 2012


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


More information about the Digitalmars-d mailing list