RFC on range design for D2

[Bill Baxter]

On Fri, Sep 12, 2008 at 1:24 AM, Steven Schveighoffer
<schveiguy at yahoo.com> wrote:
> "Bill Baxter" wrote
>>> Thus one can implement iterators on top of ranges, but I'd argue that
>>> ranges
>>> are much easier to implement on top of iterators.
>>
>> Ranges are safer and easier to work with in most cases so it's worth
>> it, or so the argument goes.  You don't buy it?
>
> I can define an iterator and it doesn't mean that it makes ranges any less
> safe.  Just give me the choice, if I think iterators are a better fit, I
> might choose iterators.  But having to shoehorn ranges into an iterator form
> so that I do not wince at the ugliness of my code seems like unnecessary
> baggage.

I think one thing to consider is what it will take to make a new
container support and "play nice" with the regime proposed.  This
touches on Andrei's point about being hard pressed to think of generic
algorithms to run on an HMM, too.

The first question is who do you want to "play nice" with?  If you're
going to be writing functions specifically for that container, then
you don't really have to play nice with anyone.  Your container just
needs to have the operations necessary to support those functions.

The question of "playing nice" with everyone is not an issue at all
until you start wanting to have one algorithm that works for lots of
different containers to that can do kinda similar sorts of things.

And that's exactly what std.algorithm is for.  Supporting those kinds
of operations that apply equally to a lot of different kinds of
containers.

So if you agree that ranges are good enough for std.algorithm, then
you should agree that a generic iterator concept is not really
necessary, since the places left where you really need an iterator are
those places where a generic algorithm are not really useful.  If they
were generic algorithms then they would be in std.algorithm.

The next thing that's worth thinking about, is how much do you have to
work to play nice with std.algorithm?  The easier it is to implement
that interface expected by std.algorthm the better.

So for one thing that means that you really want the std.algorithm
concepts to nest, for one to build on the next.  That way if you
implement the most generic level, then you've automatically
implemented all the more restricted levels.  This leads us to want to
have a names that make sense all the way up the hierarchy.  Like
isEmpty().  It pretty much makes sense no matter which direction or
how many degrees of freedom you have.  That's better than something
like atEnd() for that reason.  It is unbiased.   You wouldn't want to
have to provide an "atEnd" to work with forward ranges, and then an
"isEmpty" to work with random access even though they mean the same
thing.

So the levels of iterators and naming of their parts should nest as
much as possible.  Which seems to be pretty much the case with the
current proposal.  I think .value will be a better name for "the
current thing" than .left.  (Using the operator * may be better
still.)  But other than that, the direction the naming is taking here
on the NG seems good.  I say .value in part because if users like you
implement their own iterator types, then .value is a reasonable name
for getting the thing referred to.  So you could then write a function
that takes a range or your iterator and uses the distinguished value
referred to.  In that sense * would be even better because it would
let you pass in a pointer too.


So in the end, really what I'm saying is that I think you are right.
Iterators are useful sometimes and it would be nice to design ranges
in such a way that the range terminology makes sense for iterators
too.  An iterator would probably support the .next property just like
a range, for instance.  That's a good name that will work with either.
  Maybe it's worth codifying what the iterator concepts should be even
if std.algorithm won't use them.

> But I want to be able to
> construct ranges from pointers.

If iterators are up to you then you will be able to do this.  But
std.algorithm will only care about the ranges you construct, not the
iterators.

> I want to save pointers.  I want to use
> pointers to refer to elements in a collection.  I want to use pointers to
> move one-at-a-time along a node-based container.  I don't want to 'emulate'
> pointers using ranges.  I don't want the library to resist me doing what I
> find natural.

I don't think it will as long as you provide those
my-iterator-to-range functions.

> Anyways, I'm going to leave the discussion, I think I've said all I can
> about my views.  I'm not really good at explaining things anyways.  But I
> will update dcollections with what I think is the best compromise.  Then I
> might have a better understanding of how ranges fit into a collection
> package.  The good news is I don't have to worry about the language not
> providing iterators, everything is going to be library based, so we can
> easily try out both ways and see which is easier to use.

I think your comments have made a valuable addition to the
conversation, and have at least helped me get my thoughts together.
So thanks!  I'll be interested to see how the work on your lib turns
out.

--bb