Why must a bidirectional range also be a forward range?

Joseph Rushton Wakeling joseph.wakeling at webdrake.net
Fri Sep 20 13:08:03 UTC 2019

On Thursday, 19 September 2019 at 22:55:55 UTC, Jonathan M Davis 
> 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.
> [ ... ]

Thanks for the characteristically thorough description of both 
the design considerations and the history involved.

On reflection it occurs to me that the problem in my thinking may 
be the idea that `save` should result in a full deep copy.  If 
instead we go by how `save` is implemented for dynamic arrays, 
it's only ever a shallow copy: it's not possible to make valid 
assumptions of reproducible behaviour if the original copy is 
modified in any way.

If instead we assume that `save` is only suitable for temporary 
shallow-copies that are made under the hood of algorithms, then 
my problems go away.

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

It occurs to me that the distinction we're missing here might 
between "true" input ranges (i.e. which really come from IO of 
some kind), which indeed must be reference types, versus "pure" 
input ranges (which are deterministic, but which don't 
necessarily allow algorithms to rely on the ability to save and 
replay them).

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

Oh, I wasn't asking for any changes to the existing definition 
(at least not without much thought from everyone!).  I was just 
wanting to understand the reasons for the current situation.  But 
thanks for putting it on the list of things to consider.

I may have some follow-up to your other remarks but I think at 
least now I have a way forward with my code.  Thanks!

More information about the Digitalmars-d-learn mailing list