Why must a bidirectional range also be a forward range?

[Jonathan M Davis]

On Thursday, September 19, 2019 3:31:32 AM MDT Joseph Rushton Wakeling via 
Digitalmars-d-learn wrote:
> Hello folks,
>
> A question that occurred to me while implementing a new data
> structure recently, which I'm not sure I've ever seen a reason
> for.
>
> Why must bidirectional ranges also be forward ranges (as opposed
> to just input ranges)?
>
> It doesn't seem to me that the `save` property is inherently
> required to iterate backwards over a range -- just the `back` and
> `popBack` methods.
>
> It makes sense that, for bidirectionality, the range needs to be
> deterministic, so that iterating backward gives the exact same
> elements as iterating forward, just in reverse order.  But it
> seems strange to require the `save` property in order to
> automatically assume deterministic behaviour.
>
> For context, the use-case I have is a data structure which stores
> an internal buffer as an array.  A robust `save` method would
> therefore have to duplicate the array (or at least the active
> subset of its contents).  This means a fresh heap allocation per
> `save`, which has some nasty implications for phobos algorithms
> that eagerly `.save` when they can.
>
> So, I'd rather not implement `save` in this case.  But there is
> nothing that blocks implementing `back` and `popBack`; yet I
> can't use these with any of the functionality that requires
> bidirectionality, because the current `isBidirectionalRange`
> check requires `save`.
>
> So what gives?  Are there some reasons for the `save` requirement
> on bidirectional ranges that I'm missing?  And regardless, any
> advice on how to handle my particular use-case?
>
> Thanks & best wishes,
>
>        -- Joe

For better or worse, ranges were more or less set up as a linear hierarchy,
and it's unlikely that use cases for bidirectional ranges which aren't
forward ranges are common. I expect that it's a bit like infinite,
bidirectional ranges. In theory, they could be a thing, but the use cases
for them are uncommon enough that we don't really support them. Also, I
expect that most range-based algorithms which operate on bidirectional
ranges would require save anyway. A lot of algorithms do to the point that
basic input ranges can be incredibly frustrating to deal with.

Assuming we were redesigning the range API (which may happen if we do indeed
end up doing a Phobos v2), then maybe we could make it so that bidirectional
ranges don't have to be forward ranges, but honestly _any_ ranges which
aren't forward ranges are a bit of a problem. We do need to support them on
some level for exactly the kind of reasons that you're looking to avoid save
with a bidirectional range, but the semantic differences between what makes
sense for a basic input range and a forward range really aren't the same (in
particular, it works far better for basic input ranges to be reference
types, whereas it works better for forward ranges to be value types).

As it stands, I don't think that we can change isBidirectionalRange, because
it's likely that most code using it relies on its check for isForwardRange.
So, I think that we're stuck for the moment, but it is food for thought in a
possible range API redesign. I'll add it to my notes on the topic. Some
aspects of a range API redesign should look like are pretty clear at this
point, whereas others are very much an open question.

Ideally, I'd like to force basic input ranges to be reference types, and
forward ranges to be value types, but I'm not sure that that's reasonable in
practice. It would really clean up some of the semantics of ranges, but it
would also likely require allocating a lot more stuff on the heap than would
be desirable. Either way, having bidirectional ranges not need to have the
equivalent of save would mean treating them as more of an add-on capability
(like length) rather than having the kind of hierarchy that we have now. I
don't know if that's ultimately a good or a bad thing.

- Jonathan M Davis