Requirements for Slicing Ranges

[Jonathan M Davis]

On Monday, September 2, 2024 6:04:08 AM MDT Paul Backus via Digitalmars-d 
wrote:
> On Monday, 2 September 2024 at 02:47:16 UTC, Jonathan M Davis
>
> wrote:
> > 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).
>
> Infinite forward ranges can implement slicing, but can't be
> random-access ranges because they don't support `r.back`.

Well, with the current rules, infinite ranges don't require back in order to
be random-access ranges. You can have an infinite range which implements
indexing - and therefore is a random-access range - and it is of course also
a forward range, but it's not a bidirectional range, because it doesn't
implement back. That corner case probably does cause occasional problems
(since finite random-access ranges do have to be bidirectional ranges),
because there's probably code that checks for random-access ranges without
checking whether the range is infinite and then decides to use back, but you
wouldn't usually try to use an infinite range with something that needed
back anyway, because it wouldn't even make sense to try. Either way, I
suspect that there are a variety of bugs out there with range-based code
that doesn't actually take infinite ranges into account but which hasn't
been a problem simply because infinite ranges aren't all that common.

As for slicing an infinite range, if you slice it with two indices, you get
a finite range (which probably causes problems for some code, because the
type isn't the same, but it's obviously not possible to return the same type
in that case), whereas if you slice it with an index and $, you get the same
range type, just like you would when slicing a finite range.

So, with regards to infinite ranegs, the question is whether it's possible
to implement range[1 .. 5] (which gives a finite range) or range[5 .. $]
(which gives the same type of range) in O(1) without being able to implement
range[5] in O(1) - or if it's possible to implement range[5] in O(1), but
it's not possible to implement range[1 .. 5] or range[5 .. $] in O(1). I'm
pretty sure that they're inextricably linked and that if you can implement
slicing, you can implement random-access (and vice-versa), but again, I
could be missing something.

Regardless, random-access and slicing infinite ranges gets a bit weird,
because the "end" has to be treated differently, and you can't get a finite
slice of the same type as the infinite range when slicing, since the lack of
end is part of the type itself.

- Jonathan M Davis