Transience of .front in input vs. forward ranges

[Andrei Alexandrescu]

On 11/4/12 11:16 AM, H. S. Teoh wrote:
>> Fetching lines should be solved by using types; trafficking in
>> char[] does not offer guarantees about the preservation of the
>> content. In contrast, trafficking in string formalizes a binding
>> agreement between the range and its user that the content is
>> immutable.
> [...]
>
> I think that this may be oversimplifying the issue.

The express purpose here is to simplify instead of offering highly 
granular notions with many odd corner cases and combinations. So the 
risk of oversimplifying is indeed material.

> What about the
> example of a range of in-place permutations over an array? That range
> can be made a forward range, or even bidirectional (by reversing the
> sense of the comparison used by nextPermutation). But it is inherently a
> transient range.

That's an interesting example indeed. It would keep a T[] as its state 
and each popFront() would mutate that array to its next permutation. 
Implementing .save would be achieved by duplicating the array.

I would argue this is a tenuous range to characterize as a forward 
range. Invoking .save on a "usual" forward range means saving the 
iteration state, with an understanding that the saved range will go 
through the same iteration steps as the initial one. But nonono, 
actually the saved range goes through DUPLICATES of the states that the 
original goes through. Clearly there is an isomorphism of the two 
sequences of states, but they're not the same states - for example, 
someone looking at the original array will see the original changing the 
array, but not the .save.

So what you're looking at is a range that can define .dup, not one that 
can define .save.

> And this is merely one example. I have some non-trivial code that
> evaluates an expression tree, each node of which may generate multiple
> elements; one may take a range over all possible values that the tree
> may have. For efficiency reasons, each output value (which is
> vector-valued) reuses the same buffer. It is a forward range with a
> transient .front (it has to be a forward range, because otherwise one
> can't range over all combinations of multiple values that subtrees may
> produce).

I'm not sure about this example. Are we looking again at a .dup kind of 
thing?

> While I'm perfectly fine with the decision that such ranges shouldn't be
> considered proper ranges at all, it would greatly limit the
> applicability of std.algorithm in my code. Either I would have to
> artificially limit the range to an input range (which is a bit silly, as
> it amounts to renaming .save to something else just so std.algorithm
> wouldn't recognize it as a forward range), or I wouldn't be able to use
> std.algorithm to manipulate these ranges, but would have to roll my own.
> Of course, D makes it so that rolling my own isn't all that hard, but it
> would be a bit disappointing that the supposedly-generic algorithms in
> the standard library aren't that generic after all.

I understand. At the same time, there is a point where an abstraction 
can't comprehend all possible instances. There's already significant 
aggravation moveFront and hasLvalueElements etc., which I'd want to 
simplify given a chance. Continuing down that path seems risky to me.


Andrei