Requirements for Slicing Ranges

[Quirin Schroll]

On Monday, 2 September 2024 at 02:47:16 UTC, Jonathan M Davis 
wrote:
> One thing that I've been thinking about with regards to 
> improving the range API which I forgot to discuss previously is 
> the requirements for hasSlicing. Right now, for whatever 
> reason, slicing is divorced from random-access ranges. In 
> practice, random-access ranges have slicing (unless the 
> programmer just didn't bother to implement it), and other 
> ranges don't, but currently, hasSlicing is a separate trait 
> that can theoretically pass with a forward range, and it's not 
> guaranteed that a random-access range has slicing. So, my 
> question is:
>
> 1. Are there any realistic situations where a range could be a 
> forward or bidirectional range _and_ implement slicing in O(1), 
> but it _can't_ actually be implemented as a random-access 
> range? So, it would need to be possible to take slices of 
> elements of such a range by index in O(1) and yet somehow not 
> be possible to access individual elements by index in O(1).

I can answer this direction immediately and formally. If a range 
has O(1) slicing, it has O(1) indexing, even if an opIndex isn't 
implemented: If I want range[i], I can replace it by either 
range[i .. i + 1].front or range[i .. $].front. It's guaranteed 
to exist by virtue of the assumption that slicing exists and the 
slicing operation returns a range, and every range has a front.

> 2. Are there any realistic situations where a range could be a 
> random-access
> range but _can't_ implement slicing in O(1)? So, it would need 
> to be
> possible to access individual elements by index in O(1) and yet 
> somehow not
> be possible to take slices of elements by index in O(1).

For the other direction, i.e. has indexing, but you want slicing, 
I think you're really in the practical uses category. Maybe a 
sparse dynamic array using a splay tree as a backing structure is 
a counterexample to your idea. A splay tree is an established 
search tree that optimizes repeated adjacent accesses of the same 
element, i.e. if you seek x (average O(log n), worst case O(n)) 
and then x again, the second lookup (and any third, fourth, ...) 
will be O(1) guaranteed. I don't see how this thing can implement 
slicing. But, again, it may not be an actual counterexample.

I also remember that Judy arrays are supposedly really difficult 
to implement. Maybe they're a counterexample. I really don't know 
much about them. I looked some stuff up, but that wasn't enough 
to judge whether they can implement slicing or not.