The documentation for std.range states

http://dlang.org/phobos/std_range.html
"This module defines the notion of range (by the membership tests isInputRange, isForwardRange, isBidirectionalRange, isRandomAccessRange), range capability tests (such as hasLength or hasSlicing), and a few useful range incarnations."

But that intro doesn't describe what a range actually is.

Here's what I've made out so far:

- Ranges are basically a generalised API for accessing a container or stream that is linear in logical structure and can have any element type.

- What is a range and what isn't is determined by compile-time duck typing - testing whether it implements certain methods.

- A range over a finite data structure is essentially equivalent to a start/end iterator pair as used by various C++ STL functions.

- Where a function in std.range is described as iterating through ranges in a particular way, what this function does is to return a range that delivers the resulting sequence.

Have I got all this right?


Things I'm confused by:

- One of the expansions of put is
    r.front = e; r.popFront();

What has putting something at the front of a range and then popping it to do with outputting to the range?

- Why is a range that can save checkpoints called a "forward" range?


Stewart.

On 03/24/2012 11:19 AM, Stewart Gordon wrote:
> The documentation for std.range states
>
> http://dlang.org/phobos/std_range.html
> "This module defines the notion of range (by the membership tests
> isInputRange, isForwardRange, isBidirectionalRange,
> isRandomAccessRange), range capability tests (such as hasLength or
> hasSlicing), and a few useful range incarnations."
>
> But that intro doesn't describe what a range actually is.

Apparently the library relies on the definition elsewhere. [1]

> Here's what I've made out so far:
>
> - Ranges are basically a generalised API for accessing a container or
> stream that is linear in logical structure and can have any element type.

Yes. Some ranges can also provide random access.

> - What is a range and what isn't is determined by compile-time duck
> typing - testing whether it implements certain methods.

Yes.

> - A range over a finite data structure is essentially equivalent to a
> start/end iterator pair as used by various C++ STL functions.

Yes.

> - Where a function in std.range is described as iterating through ranges
> in a particular way, what this function does is to return a range that
> delivers the resulting sequence.

Yes. Almost always lazily.

> Have I got all this right?

Yes.

> Things I'm confused by:
>
> - One of the expansions of put is
> r.front = e; r.popFront();
>
> What has putting something at the front of a range and then popping it
> to do with outputting to the range?

Iterating an output range is also by popFront(). So what it says is, put this element to the output range and advance the range. There is a gotcha about this when the output range is a slice: Whatever is just put into the range is popped right away! :) [2]

> - Why is a range that can save checkpoints called a "forward" range?

I agree. Here is my guess: The name of the ForwardRange comes from the fact that it is not double-ended. It can go only in one direction.

> Stewart.

Ali

[1] http://www.informit.com/articles/printerfriendly.aspx?p=1407357

[2] http://ddili.org/ders/d.en/ranges.html

On 24.03.2012 22:19, Stewart Gordon wrote:
> The documentation for std.range states
>
> http://dlang.org/phobos/std_range.html
> "This module defines the notion of range (by the membership tests
> isInputRange, isForwardRange, isBidirectionalRange,
> isRandomAccessRange), range capability tests (such as hasLength or
> hasSlicing), and a few useful range incarnations."
>
> But that intro doesn't describe what a range actually is.
>
> Here's what I've made out so far:
>
> - Ranges are basically a generalised API for accessing a container or
> stream that is linear in logical structure and can have any element type.
>
> - What is a range and what isn't is determined by compile-time duck
> typing - testing whether it implements certain methods.
>
> - A range over a finite data structure is essentially equivalent to a
> start/end iterator pair as used by various C++ STL functions.
>
> - Where a function in std.range is described as iterating through ranges
> in a particular way, what this function does is to return a range that
> delivers the resulting sequence.
>
> Have I got all this right?
>

More or less fine.

>
> Things I'm confused by:
>
> - One of the expansions of put is
> r.front = e; r.popFront();

Strange looking this one, but it allows, for instance, to output things to a container that defines range over it's elements.
>
> What has putting something at the front of a range and then popping it
> to do with outputting to the range?
>
> - Why is a range that can save checkpoints called a "forward" range?
>

It's not truly checkpoints, but rather the whole state can copied.
I believe, in some use cases checkpoints can be much smaller then the whole state, and we haven't got a checkpoint range yet. Could be a nice addition if proposal is sound.


-- 
Dmitry Olshansky

On 24/03/2012 18:57, Ali Çehreli wrote:
<snip>
> Iterating an output range is also by popFront(). So what it says is, put this element to
> the output range and advance the range. There is a gotcha about this when the output range
> is a slice: Whatever is just put into the range is popped right away! :) [2]

I'm beginning to get it now: the purpose of an output range is to put new data into the underlying container.  So once you've put something in, the remaining range is what's left to be populated.  I had been thinking of outputting in terms of appending to the range, hence the confusion.

>> - Why is a range that can save checkpoints called a "forward" range?
>
> I agree. Here is my guess: The name of the ForwardRange comes from the fact that it is not
> double-ended. It can go only in one direction.
<snip>

Bidirectional ranges are forward ranges as well.

But I've just had a look at STL iterators, and it seems that the range category hierarchy has been lifted from that.  There, a "forward" iterator combines the functionality of an input iterator and an output iterator, hence it's your basic iterator that can move forwards and do what it likes with the data it walks over.  (It would seem that it's only an "output" iterator in that * returns an lvalue, which may or may not be actually assignable depending on the constancy of the element type.)

In D ranges, OTOH, the only thing that distinguishes a forward range from a general input range is the presence of a save method to make a copy of it.  Doesn't seem to have anything to do with either the "forward" name or the C++ origin thereof....

Something else I'm finding puzzling is moveFront, moveAt and moveBack.  Is D trying to be C++11 or something?  Move semantics don't seem to me to be useful in a language with GC.

Stewart.

On 03/25/2012 12:07 AM, Stewart Gordon wrote:
> On 24/03/2012 18:57, Ali Çehreli wrote:
> <snip>
>> Iterating an output range is also by popFront(). So what it says is,
>> put this element to
>> the output range and advance the range. There is a gotcha about this
>> when the output range
>> is a slice: Whatever is just put into the range is popped right away!
>> :) [2]
>
> I'm beginning to get it now: the purpose of an output range is to put
> new data into the underlying container. So once you've put something in,
> the remaining range is what's left to be populated. I had been thinking
> of outputting in terms of appending to the range, hence the confusion.
>
>>> - Why is a range that can save checkpoints called a "forward" range?
>>
>> I agree. Here is my guess: The name of the ForwardRange comes from the
>> fact that it is not
>> double-ended. It can go only in one direction.
> <snip>
>
> Bidirectional ranges are forward ranges as well.
>
> But I've just had a look at STL iterators, and it seems that the range
> category hierarchy has been lifted from that. There, a "forward"
> iterator combines the functionality of an input iterator and an output
> iterator, hence it's your basic iterator that can move forwards and do
> what it likes with the data it walks over. (It would seem that it's only
> an "output" iterator in that * returns an lvalue, which may or may not
> be actually assignable depending on the constancy of the element type.)
>
> In D ranges, OTOH, the only thing that distinguishes a forward range
> from a general input range is the presence of a save method to make a
> copy of it. Doesn't seem to have anything to do with either the
> "forward" name or the C++ origin thereof....
>
> Something else I'm finding puzzling is moveFront, moveAt and moveBack.
> Is D trying to be C++11 or something? Move semantics don't seem to me to
> be useful in a language with GC.
>
> Stewart.

The fact that the language has GC does not imply everything should go on the GC heap.

On 03/24/2012 04:07 PM, Stewart Gordon wrote:
> On 24/03/2012 18:57, Ali Çehreli wrote:
> <snip>
>> Iterating an output range is also by popFront(). So what it says is,
>> put this element to
>> the output range and advance the range. There is a gotcha about this
>> when the output range
>> is a slice: Whatever is just put into the range is popped right away!
>> :) [2]
>
> I'm beginning to get it now: the purpose of an output range is to put
> new data into the underlying container. So once you've put something in,
> the remaining range is what's left to be populated. I had been thinking
> of outputting in terms of appending to the range, hence the confusion.
>
>>> - Why is a range that can save checkpoints called a "forward" range?
>>
>> I agree. Here is my guess: The name of the ForwardRange comes from the
>> fact that it is not
>> double-ended. It can go only in one direction.
> <snip>
>
> Bidirectional ranges are forward ranges as well.
>
> But I've just had a look at STL iterators, and it seems that the range
> category hierarchy has been lifted from that. There, a "forward"
> iterator combines the functionality of an input iterator and an output
> iterator, hence it's your basic iterator that can move forwards and do
> what it likes with the data it walks over. (It would seem that it's only
> an "output" iterator in that * returns an lvalue, which may or may not
> be actually assignable depending on the constancy of the element type.)
>
> In D ranges, OTOH, the only thing that distinguishes a forward range
> from a general input range is the presence of a save method to make a
> copy of it.

I looked for rationale on Andrei's article. There is this bit about STL forward iterators:

<quote>
Input and forward iterators are syntactically identical but subtly different semantically—copying a forward iterator saves iteration state, but copying an input iterator just creates a new view of the same iteration state.
</quote>

I guess that's why 'save' is explicit on ForwardRange.

Ali

> Doesn't seem to have anything to do with either the
> "forward" name or the C++ origin thereof....
>
> Something else I'm finding puzzling is moveFront, moveAt and moveBack.
> Is D trying to be C++11 or something? Move semantics don't seem to me to
> be useful in a language with GC.
>
> Stewart.

On Saturday, March 24, 2012 18:14:46 Ali Çehreli wrote:
> I looked for rationale on Andrei's article. There is this bit about STL forward iterators:
> 
> <quote>
> Input and forward iterators are syntactically identical but subtly
> different semantically—copying a forward iterator saves iteration state,
> but copying an input iterator just creates a new view of the same
> iteration state.
> </quote>
> 
> I guess that's why 'save' is explicit on ForwardRange.

Yes. If a range is a reference type rather than a value type or a dynamic array, then you _must_ have save in order to get a copy of its current state. However, since most ranges are either dynamic arrays or value types, functions are often written without using save like they should and would end up consuming a forward range if it's a reference type (e.g. a class). But save was created primarily to make it possible to have classes which are ranges rather than relying on assignment making a copy (and not all structs are value types, so save can be required for them as well).

- Jonathan M Davis

On Sat, Mar 24, 2012 at 06:19:32PM +0000, Stewart Gordon wrote:
> The documentation for std.range states
> 
> http://dlang.org/phobos/std_range.html
> "This module defines the notion of range (by the membership tests
> isInputRange, isForwardRange, isBidirectionalRange,
> isRandomAccessRange), range capability tests (such as hasLength or
> hasSlicing), and a few useful range incarnations."
> 
> But that intro doesn't describe what a range actually is.
[...]

In a previous post long lost inside a rather large thread some time ago, I proposed a rewrite of the docs of std.range to make it clearer, at least on a basic level, what a range is, why we should care, and what the module offers.

This thread has further convinced me that std.range's docs *need* this rewrite. So here's my first attempt at it:

	https://github.com/quickfur/phobos/tree/stdrange_docs

It's not complete yet; I still have a few more range-creation templates to cover, and then list the auxiliary functions, etc., before it's ready for merging into Phobos. But I thought I should put it up for review here first, in case people have some comments/suggestions or further things that should be put into the docs. Better to put it all in a single pull request than waste the Phobos maintainers' time with multiple updates to the docs.

So, comments, suggestions, flames, etc., are hereby solicited. :-)


T

-- 
If lightning were to ever strike an orchestra, it'd always hit the conductor first.

On Sat, 24 Mar 2012 19:07:01 -0400, Stewart Gordon <smjg_1998@yahoo.com> wrote:

> On 24/03/2012 18:57, Ali Çehreli wrote:
> <snip>
>> Iterating an output range is also by popFront(). So what it says is, put this element to
>> the output range and advance the range. There is a gotcha about this when the output range
>> is a slice: Whatever is just put into the range is popped right away! :) [2]
>
> I'm beginning to get it now: the purpose of an output range is to put new data into the underlying container.  So once you've put something in, the remaining range is what's left to be populated.  I had been thinking of outputting in terms of appending to the range, hence the confusion.

The output range is almost an entirely orthogonal concept to an input range.  It basically defines a way to output elements.

How an output range directs its elements is up to the output range.  It may append, it may overwrite, it may prepend, it can do anything it wants.

The only commonality is that a *writable* input range can also be an output range (writable meaning r.front = x works).

-Steve

On Monday, 26 March 2012 at 00:50:32 UTC, H. S. Teoh wrote:

> This thread has further convinced me that std.range's docs *need* this
> rewrite. So here's my first attempt at it:
>
> 	https://github.com/quickfur/phobos/tree/stdrange_docs

I find that opening to be much better. Look forward to the improvement.