RFC on range design for D2

[Bill Baxter]

On Thu, Sep 11, 2008 at 10:46 AM, Steven Schveighoffer
<schveiguy at yahoo.com> wrote:
> "Bill Baxter" wrote
>> So far though we don't seem to be able to come up with a good example
>> other of where ranges are weak than traversing a list back and forth.
>> Note that "move back and forth according to some user input" is not
>> clearly not an "algorithm" that would be in std.algorithm.  But it
>> does come up often enough in applications.  I don't think the fact
>> that it's not strictly an Algorithm-with-a-captial-A makes it any less
>> important.
>>
>> But it is a little fishy that we can't come up with any other example
>> besides sliding a bead on a wire back and forth.
>
> Any structure that might change topology doesn't lend itself well to
> persistant ranges.

But they often don't lend themselves to iterators either.

> Ranges are fine for iterating over a constant version of
> the container.  i.e., if you want to implement a search function, where you
> are assuming that during the search, the container doesn't change, that
> should take a range as an argument.  But storing references to individual
> elements for later use (such as O(1) lookup or quick removal), and modifying
> the container inbetween getting the reference and using the reference makes
> it difficult to guarantee the behavior.

Lots of algorithms on containers using iterators have this property too.

> The only range type that seems like
> it would be immune to such changes would be the empty range where both ends
> point to the same element.  In fact, this can be reduced to a single
> reference, just copied for the sake of calling it a 'range'.

Or a here-to-end range where one end points to a special "end"
sentinel.  Like with a linked list.
You can't change the sentinel by mutating the contents so it remains
valid.  I think this would be a more common/useful form than the empty
range.  Because you can dereference the range from here-to-end, but
you can't dereference the range from here to here.

Probably the cursor idiom should also use "all" and "here-to-end"
rather than "all" and "here-to-here".  Then the
all.after(center).value ugliness isn't needed, just center.value.  (I
prefer ".value" to ".first")

> Arrays are really a special case where the ranges unequivocally work because
> once you get a range, all of it is guaranteed not to disappear or change
> topology.  i.e. a slice always contains valid data, no matter what you do to
> the original array.  I think this is the model Andrei is trying to achieve
> for all containers/iterables, and I think it's just not the same.  I think
> passing the range around as one entity is a very helpful thing, especially
> for algorithms which generally take ranges in the form of 2 iterators, but I
> don't think it solves all problems.

Well it solves them, but is it worth the tradeoffs you have to make.
You say no.  I say I now have a reasonable way to handle the only
example I could think of that seemed really cumbersome.  Lacking
further evidence it seems the main problem remaining is just having to
carry around an extra value when you just want to refer to one value.

However, those pointers to "single values" can also move, so for
safety's sake why not keep the fence post with it?

--bb