Infinite BidirectionalRange?

[Tomek Sowiński]

Ali Çehreli <acehreli at yahoo.com> wrote:
> Andrei Alexandrescu wrote:
> > On 12/24/10 4:19 PM, Ali Çehreli wrote:
> >> isRandomAccessRange at
> >>
> >> http://digitalmars.com/d/2.0/phobos/std_range.html#isRandomAccessRange
> >>
> >> describes what a RandomAccessRange is:
> >>
> >> <quote>
> >>
> >> A random-access range is a bidirectional range that also offers the
> >> primitive opIndex, OR an infinite forward range that offers
> > > opIndex. In
> >> either case, the range must either offer length or be infinite. The
> >> following code should compile for any random-access range.
> >>
> >> R r;
> >> static assert(isForwardRange!(R)); // range is forward
> >> static assert(isBidirectionalRange!(R) || isInfinite!(R));
> >> // range is bidirectional or infinite
> >> auto e = r[1]; // can index
> >>
> >> </quote>
> >>
> >> The part that starts with "In either case" does not make sense to
> > > me
> >> (and the sample code does not cover all possible cases). It seems
> > > to
> >> suggest that a RandomAccessRange may be an infinite
> > > BidirectionalRange.
> >>
> >> Since a BidirectionalRange defines both front() and back(), its
> > > being
> >> infinite can only come from asymptoting at one or more points in
> > > between
> >> the two ends. Is that useful?
> >>
> >> Does the document need correction or my understanding? :)
> >>
> >> Ali
> >
> > The document I think. Essentially I meant to define the conceptual
> > hierarchy as in this figure:
> >
> > http://ptgmedia.pearsoncmg.com/images/art_alexandrescu3_iterators/elementLinks/alexandrescu3_fig03.jpg
> > 
> 
> As I've been playing with ranges recently I kept thinking that
> DoubleEndedRange fit better than BidirectionalRange. I wonder why it
> ended up being named BidirectionalRange.

My fav. is DuplexRange. But bidirectional ain't bad either. I guess past
the suck point, it's an explorer's right to name an island.

> > and as described in the associated article
> > http://www.informit.com/articles/printerfriendly.aspx?p=1407357
> >
> > So what would be a better formulation?
> 
> The spec page sounds as if all of the following make a
> RandomAccessRange, but two of them don't make sense:
> 
> a) BidirectionalRange + opIndex + length
> 
> b) infinite BidirectionalRange + opIndex (doesn't sound useful;
> although Simen gives a plausible example)
> 
> c) infinite ForwardRange + opIndex
> 
> d) infinite ForwardRange + opIndex + length (doesn't make sense)
> 
> Would the following proposed definition be correct?
> 
> <proposed>
> 
> A random-access range is a bidirectional range OR an infinite forward
> range that offers the primitive opIndex.
> 
> </proposed>
> 
> I can't be sure whether the former should also provide the primitive
> 'length'.

I think so. If you got random access and know the end, you should also
know how far is the end element. At least I can't think of a counter
example.

> That would make sense, but having the hasLength helper makes it also
> feel like 'length' is an optional property of ranges.

Length in general is an optional feature of ranges.

Taking a look back, I wonder if the notion RandomAccessRange is useful
at all. Where elements are accessed randomly (e.g. sorting, viewing),
one doesn't really need the thing to be a range. That suggests a loose
feature rather than a place in hierarchy. Was hasRandomAccess and
hasSafeRandomAccess considered? (the latter has random access and
(length (x)or infinity))

-- 
Tomek