On Monday, 22 January 2024 at 05:22:44 UTC, Paul Backus wrote:
>You have N data structures and M algorithms, and by using this common interface you can implement all N*M combinations in O(N+M) code. Each data structure implements the range API once, and each algorithm is implemented once using the range API.
If you split the API in two, by making input streams (basic input ranges) and forward ranges completely disjoint, you undermine this goal. Now, each data structure has to implement two APIs, and each algorithm has to be implemented twice, once for input streams and once for forward ranges.
Not necessarily. First, any algorithm requiring a forward range wouldn’t be implemented twice. And, most importantly, a data structure would not offer input range iteration if it can offer forward range. Why would it?
>In practice, what's going to happen is library authors will simply not bother to implement both, and we will end up with gaps where many (data structure, algorithm) pairs are not covered.
The only realistic concern I see with the proposal is algorithms being implemented requiring forward ranges when they could (also) work with basic input ranges. Overconstraining input is not specific to ranges, though.
What Jonathan never mentioned in his proposal, but something that, as far as I see, is true: One can wrap any forward range to be an input range. Heck, the pointer to any forward range is an input range, assuming there is a global next(ForwardRange*)
function utilizing the forward range primitives. If you pass &forwardRange
to an input range algorithm, it may copy it around as it pleases, it will change the underlying range just like an input range should; and you’d have the &
for an indication that it does.
A problem I see with this is composition. Requiring the lifting to a pointer requires lvalues, and composition lives on not having those. The issue will generally be negligible, as most range algorithms returning a range will for the most part want to preserve as many of the abilities of the original range as possible. The difference in the algorithm would be that, instead of:
// implement input range
static if (/* base range is forward range */)
// implement forward range
static if (/* base range is bidi range */
// implement bidi range
// etc.
You would have:
static if (/* base range is input range */)
// implement input range
else:
static if (/* base range is forward range */)
// implement forward range
static if (/* base range is bidi range */)
// implement bidi range
// etc.