www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Infinite BidirectionalRange?

reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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
Dec 24 2010
next sibling parent =?UTF-8?Q?Tomek=20Sowi=C5=84ski?= <just ask.me> writes:
Ali Çehreli <acehreli yahoo.com> 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? :)


I think the docs silently assume bidir ranges can't be infinite. Then
again, infinity is defined as empty being false at compile-time, so
technically it's possible... I'm also curious what earthly mechanism
could be modeled by such a range.

-- 
Tomek
Dec 25 2010
prev sibling next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Ali =C3=87ehreli <acehreli yahoo.com> wrote:


 Since a BidirectionalRange defines both front() and back(), its being =


 =


 infinite can only come from asymptoting at one or more points in betwe=


en  =


 the two ends. Is that useful?


Consider Cycle[1]. cycle([1,2]) may very well be a bidirectional range,
but it is clearly also infinite. (Currently, it is not bidirectional, bu=
t
it is random-access for ranges that support that.)

[1]: http://www.digitalmars.com/d/2.0/phobos/std_range.html#Cycle

-- =

Simen
Dec 25 2010
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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

and as described in the associated article 
http://www.informit.com/articles/printerfriendly.aspx?p=1407357

So what would be a better formulation?


Andrei
Dec 25 2010
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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/ale
andrescu3_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.


 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'. That would make sense, but having the hasLength helper makes 
it also feel like 'length' is an optional property of ranges.

Ali
Dec 25 2010
parent reply =?UTF-8?Q?Tomek=20Sowi=C5=84ski?= <just ask.me> writes:
Ali Çehreli <acehreli 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
Dec 25 2010
parent spir <denis.spir gmail.com> writes:
On Sun, 26 Dec 2010 00:36:26 +0000 (UTC)
Tomek Sowi=C5=84ski <just ask.me> wrote:


 <proposed>
=20
 A random-access range is a bidirectional range OR an infinite forward
 range that offers the primitive opIndex.
=20
 </proposed>
=20
 I can't be sure whether the former should also provide the primitive
 'length'. =20


=20
 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.


Same for me. And that's why I think '$' should map to a length attribute or=
 property, and not to a not-yet-implemented opDollar. Make 'length partiall=
y magic for that case. Simpler, and would work in 90% cases, since 'length'=
 is the _de facto_ conventional D name.


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


=20
 Length in general is an optional feature of ranges.
=20
 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))


I agree. Or, conversely, make structs/classes that implement random-access =
(opIndom+length) be automatically considered as input/forwar/bidi without h=
aving to overload with 6 additional methods. Anyway, rewriting the loops ma=
y be different for such random-access ranges.

Denis
-- -- -- -- -- -- --
vit esse estrany =E2=98=A3

spir.wikidot.com
Dec 26 2010