Requirements for Slicing Ranges

Jonathan M Davis newsgroup.d at jmdavisprog.com
Mon Sep 2 02:47:16 UTC 2024


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

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

As far as I can tell, the ability to index a range and the ability to slice
it are inextricably linked. If you can do range[5 .. 12] or range[7 .. $] in
O(1), then you should be able to do range[5] or range[12] in O(1).
Similarly, if you can do range[5] in O(1), it should be possible to do
range[5 .. 12] in O(1).

Does anyone know of a situation where that would not be the case? I would
love to just ditch the test for slicing in the updated range API and tie the
ability to random-access ranges, since it would be simplify things. If I had
to guess without digging through all of the history, I suspect that
random-access ranges were added before slicing was and that that's why they
weren't tied together, but in practice, they always seem to be, and I can't
think of a reason at the moment why they can't be.

Can anyone see something that I'm missing here?

- Jonathan M Davis





More information about the Digitalmars-d mailing list