www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - range and algorithm-related stuff

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
I'm working on the new range stuff and the range-based algorithm. In all 
likelihood, you all might be pleased with the results.

I wanted to gauge opinions on a couple of issues. One is, should the 
empty() member function for ranges be const? On the face of it it 
should, but I don't want that to be a hindrance. I presume non-const 
empty might be necessary sometimes, e.g. figuring out if a stream is 
empty effectively means fetching an element off it.

Second, there are arguably some range-related constructs that do not 
really qualify as "algorithms" (some of these are inspired from 
Haskell's standard library):

1. repeat(x) => returns an infinite range consisting of the element x 
repeated.

http://www.zvon.org/other/haskell/Outputprelude/repeat_f.html

2. take(n, range) => takes at most n elements out of a range (very 
useful with infinite ranges!)

http://www.zvon.org/other/haskell/Outputprelude/take_f.html

3. cycle(range)

http://www.zvon.org/other/haskell/Outputprelude/cycle_f.html

and a few others. I defined a new module called std.range that contains 
range fundamentals. Should I put these functions in there, or in 
std.algorithm? Or should I just merge them both to avoid confusion? If 
not, where to I draw the line between "it's an algorithm" and "it's a 
range utility"?


Thanks,

Andrei
Jan 24 2009
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 I'm working on the new range stuff and the range-based algorithm. In all
 likelihood, you all might be pleased with the results.
 I wanted to gauge opinions on a couple of issues. One is, should the
 empty() member function for ranges be const? On the face of it it
 should, but I don't want that to be a hindrance. I presume non-const
 empty might be necessary sometimes, e.g. figuring out if a stream is
 empty effectively means fetching an element off it.

Play devil's advocate with me. Given that making empty() non-const would make the internal implementation of things more flexible, and that next() has to be non-const, so the range interface as a whole is non-const, what is the practical advantage to making empty() const?
 Second, there are arguably some range-related constructs that do not
 really qualify as "algorithms" (some of these are inspired from
 Haskell's standard library):
 1. repeat(x) => returns an infinite range consisting of the element x
 repeated.
 http://www.zvon.org/other/haskell/Outputprelude/repeat_f.html
 2. take(n, range) => takes at most n elements out of a range (very
 useful with infinite ranges!)
 http://www.zvon.org/other/haskell/Outputprelude/take_f.html
 3. cycle(range)
 http://www.zvon.org/other/haskell/Outputprelude/cycle_f.html
 and a few others. I defined a new module called std.range that contains
 range fundamentals. Should I put these functions in there, or in
 std.algorithm? Or should I just merge them both to avoid confusion? If
 not, where to I draw the line between "it's an algorithm" and "it's a
 range utility"?

I think these Haskell inspired functions belong in std.range. To me an algorithm is something that manipulates the contents of a range, i.e. the actual values contained in the range. A range utility is something that doesn't care what's in the range, and just affects the way the range is iterated over, etc. A good test for this would be to assume that the contents of the range are null references. A range utility would still work because it doesn't care what the actual contents are. An algorithm (at least one that does anything useful other than initialize the references) could not work in this case.
Jan 24 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
dsimcha wrote:
 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 I'm working on the new range stuff and the range-based algorithm. In all
 likelihood, you all might be pleased with the results.
 I wanted to gauge opinions on a couple of issues. One is, should the
 empty() member function for ranges be const? On the face of it it
 should, but I don't want that to be a hindrance. I presume non-const
 empty might be necessary sometimes, e.g. figuring out if a stream is
 empty effectively means fetching an element off it.

Play devil's advocate with me. Given that making empty() non-const would make the internal implementation of things more flexible, and that next() has to be non-const, so the range interface as a whole is non-const, what is the practical advantage to making empty() const?

If empty, head, toe, opIndex, and length are const, there's plenty you can do with the const range. The problem is that there are higher-order range that need to make assumptions about the underlying range. Consider a simple range Retro that iterates another range in reverse order: struct Retro(R) { private R _original; ... bool empty() { return _original.empty; } } Should Retro make empty const or non-const? If it does, then ranges that make const non-empty won't work with Retro. If it doesn't, then users can't use empty for a const Retro.
 Second, there are arguably some range-related constructs that do not
 really qualify as "algorithms" (some of these are inspired from
 Haskell's standard library):
 1. repeat(x) => returns an infinite range consisting of the element x
 repeated.
 http://www.zvon.org/other/haskell/Outputprelude/repeat_f.html
 2. take(n, range) => takes at most n elements out of a range (very
 useful with infinite ranges!)
 http://www.zvon.org/other/haskell/Outputprelude/take_f.html
 3. cycle(range)
 http://www.zvon.org/other/haskell/Outputprelude/cycle_f.html
 and a few others. I defined a new module called std.range that contains
 range fundamentals. Should I put these functions in there, or in
 std.algorithm? Or should I just merge them both to avoid confusion? If
 not, where to I draw the line between "it's an algorithm" and "it's a
 range utility"?

I think these Haskell inspired functions belong in std.range. To me an algorithm is something that manipulates the contents of a range, i.e. the actual values contained in the range. A range utility is something that doesn't care what's in the range, and just affects the way the range is iterated over, etc. A good test for this would be to assume that the contents of the range are null references. A range utility would still work because it doesn't care what the actual contents are. An algorithm (at least one that does anything useful other than initialize the references) could not work in this case.

That's an excellent principle! Range functions deal with the range's topology, algorithms deal with the range's content. Thanks a lot. Andrei
Jan 24 2009
parent Daniel Keep <daniel.keep.lists gmail.com> writes:
Andrei Alexandrescu wrote:
 dsimcha wrote:
 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s
 article
 I'm working on the new range stuff and the range-based algorithm. In all
 likelihood, you all might be pleased with the results.
 I wanted to gauge opinions on a couple of issues. One is, should the
 empty() member function for ranges be const? On the face of it it
 should, but I don't want that to be a hindrance. I presume non-const
 empty might be necessary sometimes, e.g. figuring out if a stream is
 empty effectively means fetching an element off it.

Play devil's advocate with me. Given that making empty() non-const would make the internal implementation of things more flexible, and that next() has to be non-const, so the range interface as a whole is non-const, what is the practical advantage to making empty() const?

If empty, head, toe, opIndex, and length are const, there's plenty you can do with the const range. The problem is that there are higher-order range that need to make assumptions about the underlying range. Consider a simple range Retro that iterates another range in reverse order: struct Retro(R) { private R _original; ... bool empty() { return _original.empty; } } Should Retro make empty const or non-const? If it does, then ranges that make const non-empty won't work with Retro. If it doesn't, then users can't use empty for a const Retro.

Couldn't you do something like this? struct Retro(R) { private R _original; ... // Don't know how to write the isMemberConst test... static if( isMemberConst!( R, "empty" ) ) { const bool empty() { return _original.empty; } } else { bool empty() { return _original.empty; } } } Propogate const-ness where possible, but don't prevent it from functioning otherwise. Incidentally, I'd have proposed something like: protectionOf!(_original.empty) bool empty() { return _original.empty; } But I doubt that's possible with templates :P
 [snip]

I'm with dsimcha on the distinction between std.algorithm and std.range. -- Daniel
Jan 24 2009
prev sibling next sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2009-01-24 20:09:07 -0500, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:

 I'm working on the new range stuff and the range-based algorithm. In 
 all likelihood, you all might be pleased with the results.
 
 I wanted to gauge opinions on a couple of issues. One is, should the 
 empty() member function for ranges be const? On the face of it it 
 should, but I don't want that to be a hindrance. I presume non-const 
 empty might be necessary sometimes, e.g. figuring out if a stream is 
 empty effectively means fetching an element off it.

Another case where you want to propagate the constness depending on the arguments... do we need something akin equivariant templates, with constness propagation?
 Second, there are arguably some range-related constructs that do not 
 really qualify as "algorithms" (some of these are inspired from 
 Haskell's standard library):
 
 1. repeat(x) => returns an infinite range consisting of the element x repeated.
 
 http://www.zvon.org/other/haskell/Outputprelude/repeat_f.html
 
 2. take(n, range) => takes at most n elements out of a range (very 
 useful with infinite ranges!)
 
 http://www.zvon.org/other/haskell/Outputprelude/take_f.html
 
 3. cycle(range)
 
 http://www.zvon.org/other/haskell/Outputprelude/cycle_f.html
 
 and a few others.

I'd add a second optional argument to repeat and cycle where you can specify how many times you want to loop. When argument is omitted, it's infinite.
 I defined a new module called std.range that contains range 
 fundamentals. Should I put these functions in there, or in 
 std.algorithm? Or should I just merge them both to avoid confusion? If 
 not, where to I draw the line between "it's an algorithm" and "it's a 
 range utility"?

I'd go with std.range. In fact, I'd remove std.algorithm and put everything into std.range. After all, all those algorithms apply to ranges. After all, if we are going to have algorithms for other thing than ranges -- like tuples -- then they should be in their own module -- like std.tuple -- no? -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Jan 24 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Michel Fortin wrote:
 On 2009-01-24 20:09:07 -0500, Andrei Alexandrescu 
 <SeeWebsiteForEmail erdani.org> said:
 
 I'm working on the new range stuff and the range-based algorithm. In 
 all likelihood, you all might be pleased with the results.

 I wanted to gauge opinions on a couple of issues. One is, should the 
 empty() member function for ranges be const? On the face of it it 
 should, but I don't want that to be a hindrance. I presume non-const 
 empty might be necessary sometimes, e.g. figuring out if a stream is 
 empty effectively means fetching an element off it.

Another case where you want to propagate the constness depending on the arguments... do we need something akin equivariant templates, with constness propagation?
 Second, there are arguably some range-related constructs that do not 
 really qualify as "algorithms" (some of these are inspired from 
 Haskell's standard library):

 1. repeat(x) => returns an infinite range consisting of the element x 
 repeated.

 http://www.zvon.org/other/haskell/Outputprelude/repeat_f.html

 2. take(n, range) => takes at most n elements out of a range (very 
 useful with infinite ranges!)

 http://www.zvon.org/other/haskell/Outputprelude/take_f.html

 3. cycle(range)

 http://www.zvon.org/other/haskell/Outputprelude/cycle_f.html

 and a few others.

I'd add a second optional argument to repeat and cycle where you can specify how many times you want to loop. When argument is omitted, it's infinite.

Repeat a finite number of times is called replicate in Haskell, and the D implementation is eerily close to Haskell's: auto replicate(T)(size_t n, T value) { return take(n, repeat(value)); } It even compiles and runs. Just you can't document it because ddoc doesn't work with "auto" functions :o).
 I defined a new module called std.range that contains range 
 fundamentals. Should I put these functions in there, or in 
 std.algorithm? Or should I just merge them both to avoid confusion? If 
 not, where to I draw the line between "it's an algorithm" and "it's a 
 range utility"?

I'd go with std.range. In fact, I'd remove std.algorithm and put everything into std.range. After all, all those algorithms apply to ranges. After all, if we are going to have algorithms for other thing than ranges -- like tuples -- then they should be in their own module -- like std.tuple -- no?

I guess, but today there are algorithms that don't operate on ranges inside std.algorithm, such as move and swap. Andrei
Jan 24 2009
prev sibling next sibling parent reply Sergey Gromov <snake.scaly gmail.com> writes:
Sat, 24 Jan 2009 17:09:07 -0800, Andrei Alexandrescu wrote:

 I'm working on the new range stuff and the range-based algorithm. In all 
 likelihood, you all might be pleased with the results.
 
 I wanted to gauge opinions on a couple of issues. One is, should the 
 empty() member function for ranges be const? On the face of it it 
 should, but I don't want that to be a hindrance. I presume non-const 
 empty might be necessary sometimes, e.g. figuring out if a stream is 
 empty effectively means fetching an element off it.

I have a hard time imagining a use for a const range. They're supposed to be structs, right? Const value argument is not a very useful idiom. Also you cannot do much with a const range. OTOH you never know what downs will invent next time. Supporting const transparency as much as possible seems to be the right solution.
Jan 25 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Sergey Gromov wrote:
 Sat, 24 Jan 2009 17:09:07 -0800, Andrei Alexandrescu wrote:
 
 I'm working on the new range stuff and the range-based algorithm. In all 
 likelihood, you all might be pleased with the results.

 I wanted to gauge opinions on a couple of issues. One is, should the 
 empty() member function for ranges be const? On the face of it it 
 should, but I don't want that to be a hindrance. I presume non-const 
 empty might be necessary sometimes, e.g. figuring out if a stream is 
 empty effectively means fetching an element off it.

I have a hard time imagining a use for a const range.

Read-only arrays for example.
 They're supposed
 to be structs, right?

Yah.
 Const value argument is not a very useful idiom.

Not in C++ you mean! In D the ballgame is rather different.
 Also you cannot do much with a const range.

If it has random access, it's effectively a read-only array.
 OTOH you never know what downs will invent next time.  Supporting const
 transparency as much as possible seems to be the right solution.

Yah. And (as I also discovered yesterday without joy) ref transparency as well... Andrei
Jan 25 2009
parent reply Christopher Wright <dhasenan gmail.com> writes:
Andrei Alexandrescu wrote:
 Sergey Gromov wrote:
 Sat, 24 Jan 2009 17:09:07 -0800, Andrei Alexandrescu wrote:

 I'm working on the new range stuff and the range-based algorithm. In 
 all likelihood, you all might be pleased with the results.

 I wanted to gauge opinions on a couple of issues. One is, should the 
 empty() member function for ranges be const? On the face of it it 
 should, but I don't want that to be a hindrance. I presume non-const 
 empty might be necessary sometimes, e.g. figuring out if a stream is 
 empty effectively means fetching an element off it.

I have a hard time imagining a use for a const range.

Read-only arrays for example.

A range is essentially an iterator. It has to change its internal state to move to the next element. So a const range will not allow you to iterate over the members of a const array. It will allow you to iterate over a single element, either once or an infinite number of times. You could change ranges to have "Range next()" rather than "void next()", and that would allow you to use a const Range for reasons other than checking whether it's empty. Iterating over a range would then look like: for (auto range = getRange(); !range.empty; range = range.next) {} I don't see much purpose to this. If you want polymorphic ranges, you're going to use a class for ranges. This will incur a lot of allocations, which will be dog slow. The current design would only allocate once if your range is a class.
Jan 25 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Christopher Wright wrote:
 Andrei Alexandrescu wrote:
 Sergey Gromov wrote:
 Sat, 24 Jan 2009 17:09:07 -0800, Andrei Alexandrescu wrote:

 I'm working on the new range stuff and the range-based algorithm. In 
 all likelihood, you all might be pleased with the results.

 I wanted to gauge opinions on a couple of issues. One is, should the 
 empty() member function for ranges be const? On the face of it it 
 should, but I don't want that to be a hindrance. I presume non-const 
 empty might be necessary sometimes, e.g. figuring out if a stream is 
 empty effectively means fetching an element off it.

I have a hard time imagining a use for a const range.

Read-only arrays for example.

A range is essentially an iterator. It has to change its internal state to move to the next element. So a const range will not allow you to iterate over the members of a const array. It will allow you to iterate over a single element, either once or an infinite number of times.

A range offering random access can give me any element without the range actually changing.
 You could change ranges to have "Range next()" rather than "void 
 next()", and that would allow you to use a const Range for reasons other 
 than checking whether it's empty. Iterating over a range would then look 
 like:
 for (auto range = getRange(); !range.empty; range = range.next) {}
 
 I don't see much purpose to this. If you want polymorphic ranges, you're 
 going to use a class for ranges. This will incur a lot of allocations, 
 which will be dog slow. The current design would only allocate once if 
 your range is a class.

I agree. Range.next currently mutates the range in-place. Andrei
Jan 25 2009
parent reply Sergey Gromov <snake.scaly gmail.com> writes:
Sun, 25 Jan 2009 13:53:43 -0800, Andrei Alexandrescu wrote:

 Christopher Wright wrote:
 Andrei Alexandrescu wrote:
 Sergey Gromov wrote:
 Sat, 24 Jan 2009 17:09:07 -0800, Andrei Alexandrescu wrote:

 I'm working on the new range stuff and the range-based algorithm. In 
 all likelihood, you all might be pleased with the results.

 I wanted to gauge opinions on a couple of issues. One is, should the 
 empty() member function for ranges be const? On the face of it it 
 should, but I don't want that to be a hindrance. I presume non-const 
 empty might be necessary sometimes, e.g. figuring out if a stream is 
 empty effectively means fetching an element off it.

I have a hard time imagining a use for a const range.

Read-only arrays for example.

A range is essentially an iterator. It has to change its internal state to move to the next element. So a const range will not allow you to iterate over the members of a const array. It will allow you to iterate over a single element, either once or an infinite number of times.

A range offering random access can give me any element without the range actually changing.

This restricts you to algorithms working exclusively with random-access ranges. Any more generic algos won't work with const ranges. How many of those do you have?
Jan 26 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Sergey Gromov wrote:
 Sun, 25 Jan 2009 13:53:43 -0800, Andrei Alexandrescu wrote:
 
 Christopher Wright wrote:
 Andrei Alexandrescu wrote:
 Sergey Gromov wrote:
 Sat, 24 Jan 2009 17:09:07 -0800, Andrei Alexandrescu wrote:

 I'm working on the new range stuff and the range-based algorithm. In 
 all likelihood, you all might be pleased with the results.

 I wanted to gauge opinions on a couple of issues. One is, should the 
 empty() member function for ranges be const? On the face of it it 
 should, but I don't want that to be a hindrance. I presume non-const 
 empty might be necessary sometimes, e.g. figuring out if a stream is 
 empty effectively means fetching an element off it.



to move to the next element. So a const range will not allow you to iterate over the members of a const array. It will allow you to iterate over a single element, either once or an infinite number of times.

actually changing.

This restricts you to algorithms working exclusively with random-access ranges. Any more generic algos won't work with const ranges. How many of those do you have?

Stable partition, everything related to binary search, heap functions, and radial iteration come to mind. Anyhow, for now let's go with requiring ref returns and we'll see how that fares. I'm almost done with std.algorithm. (I am cheating because Walter emailed me a fixed dmd that allows ref returns from template funs.) Very exciting. I will post the documentation as soon as I'm done. Andrei
Jan 26 2009
prev sibling next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Sun, 25 Jan 2009 23:32:13 +0300, Christopher Wright <dhasenan gmail.com>
wrote:

 Andrei Alexandrescu wrote:
 Sergey Gromov wrote:
 Sat, 24 Jan 2009 17:09:07 -0800, Andrei Alexandrescu wrote:

 I'm working on the new range stuff and the range-based algorithm. In  
 all likelihood, you all might be pleased with the results.

 I wanted to gauge opinions on a couple of issues. One is, should the  
 empty() member function for ranges be const? On the face of it it  
 should, but I don't want that to be a hindrance. I presume non-const  
 empty might be necessary sometimes, e.g. figuring out if a stream is  
 empty effectively means fetching an element off it.

I have a hard time imagining a use for a const range.


A range is essentially an iterator. It has to change its internal state to move to the next element. So a const range will not allow you to iterate over the members of a const array. It will allow you to iterate over a single element, either once or an infinite number of times. You could change ranges to have "Range next()" rather than "void next()", and that would allow you to use a const Range for reasons other than checking whether it's empty. Iterating over a range would then look like: for (auto range = getRange(); !range.empty; range = range.next) {} I don't see much purpose to this. If you want polymorphic ranges, you're going to use a class for ranges. This will incur a lot of allocations, which will be dog slow. The current design would only allocate once if your range is a class.

I belive he was talking about random-access ranges. A range.subrange() could also be const, though.
Jan 25 2009
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Andrei Alexandrescu" wrote
 I'm working on the new range stuff and the range-based algorithm. In all 
 likelihood, you all might be pleased with the results.

 I wanted to gauge opinions on a couple of issues. One is, should the 
 empty() member function for ranges be const? On the face of it it should, 
 but I don't want that to be a hindrance. I presume non-const empty might 
 be necessary sometimes, e.g. figuring out if a stream is empty effectively 
 means fetching an element off it.

Ranges are structs. It should not matter if you want to make some const and some non-const. Basically, it depends on the range implementation. If you can make it const, make it const, if not, don't make it const. It shouldn't break any APIs. For example, an array range might have empty be const, but a stream range might not. What matters is what functions you can use those ranges in, but those are generally templated functions, so the compiler will tell you whether it can be used or not when it tries to compile it. Personally, I see no benefit to having empty() be const. What benefits do you gain by specifically making empty const and the other functions not const? Presumably, the underlying container must be not const in order for head, next, etc. to work properly, so there is no requirement there. -Steve
Jan 26 2009
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Steven Schveighoffer wrote:
 "Andrei Alexandrescu" wrote
 I'm working on the new range stuff and the range-based algorithm. In all 
 likelihood, you all might be pleased with the results.

 I wanted to gauge opinions on a couple of issues. One is, should the 
 empty() member function for ranges be const? On the face of it it should, 
 but I don't want that to be a hindrance. I presume non-const empty might 
 be necessary sometimes, e.g. figuring out if a stream is empty effectively 
 means fetching an element off it.

Ranges are structs. It should not matter if you want to make some const and some non-const. Basically, it depends on the range implementation. If you can make it const, make it const, if not, don't make it const. It shouldn't break any APIs.

The problem is "higher-order" ranges - ranges that take other ranges as argument. For example, consider Retro, a range that iterates another range backwards. struct Retro(Range) { Range _input; ... bool empty() { return _input.empty; } } If Retro.empty is const and Range.empty is not, that won't compile. If Retro.empty is non-const and Range.empty is const, it will compile, but passing a const Retro won't work as well as passing a const Range.
 For example, an array range might have empty be const, but a stream range 
 might not.  What matters is what functions you can use those ranges in, but 
 those are generally templated functions, so the compiler will tell you 
 whether it can be used or not when it tries to compile it.
 
 Personally, I see no benefit to having empty() be const.  What benefits do 
 you gain by specifically making empty const and the other functions not 
 const?  Presumably, the underlying container must be not const in order for 
 head, next, etc. to work properly, so there is no requirement there.

If you have a constant range with random access, empty, length, and opIndex should be enough for you to look at anything you want without altering the range itself. Andrei
Jan 26 2009
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Andrei Alexandrescu" wrote
 Steven Schveighoffer wrote:
 "Andrei Alexandrescu" wrote
 I'm working on the new range stuff and the range-based algorithm. In all 
 likelihood, you all might be pleased with the results.

 I wanted to gauge opinions on a couple of issues. One is, should the 
 empty() member function for ranges be const? On the face of it it 
 should, but I don't want that to be a hindrance. I presume non-const 
 empty might be necessary sometimes, e.g. figuring out if a stream is 
 empty effectively means fetching an element off it.

Ranges are structs. It should not matter if you want to make some const and some non-const. Basically, it depends on the range implementation. If you can make it const, make it const, if not, don't make it const. It shouldn't break any APIs.

The problem is "higher-order" ranges - ranges that take other ranges as argument. For example, consider Retro, a range that iterates another range backwards. struct Retro(Range) { Range _input; ... bool empty() { return _input.empty; } } If Retro.empty is const and Range.empty is not, that won't compile. If Retro.empty is non-const and Range.empty is const, it will compile, but passing a const Retro won't work as well as passing a const Range.

Hm... you need the template code to take the place of the designer who looks at code and decides that something should or should not be const. For the case of Retro, you'd need some sort of const detection on Range's empty function. But in general, when is it necessary for Range.empty to be const (and therefore Retro.empty to be const)? If Range is working with a const container, wouldn't you expect that Range itself would not be const, just the reference to the container is const? A range that doesn't mutate doesn't seem like a very useful idiom.
 For example, an array range might have empty be const, but a stream range 
 might not.  What matters is what functions you can use those ranges in, 
 but those are generally templated functions, so the compiler will tell 
 you whether it can be used or not when it tries to compile it.

 Personally, I see no benefit to having empty() be const.  What benefits 
 do you gain by specifically making empty const and the other functions 
 not const?  Presumably, the underlying container must be not const in 
 order for head, next, etc. to work properly, so there is no requirement 
 there.

If you have a constant range with random access, empty, length, and opIndex should be enough for you to look at anything you want without altering the range itself.

Why not just pass the container itself if the range isn't going to mutate? The container probably already has opIndex, and length (empty AFAIK plays no role here). If it doesn't it seems like a bad design to me. If you have a good example where this is useful, I'd like to hear it. -Steve
Jan 26 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Steven Schveighoffer wrote:
 "Andrei Alexandrescu" wrote
 If Retro.empty is const and Range.empty is not, that won't compile. If 
 Retro.empty is non-const and Range.empty is const, it will compile, but 
 passing a const Retro won't work as well as passing a const Range.

Hm... you need the template code to take the place of the designer who looks at code and decides that something should or should not be const. For the case of Retro, you'd need some sort of const detection on Range's empty function.

Exactly. A sort of "auto-qualify". But I guess at that point some people will throw their hands in the air, and those who'd thrown their hands already will now throw their feet too. :o)
 But in general, when is it necessary for Range.empty to be const (and 
 therefore Retro.empty to be const)?  If Range is working with a const 
 container, wouldn't you expect that Range itself would not be const, just 
 the reference to the container is const?  A range that doesn't mutate 
 doesn't seem like a very useful idiom.

I agree, but then I don't want to make many assumptions about future designs. In general I'm not sure we can always assume the type of the range and the environment make it easy to obtain mutable ranges for immutable elements. Probably many people would expect to just write this: void foo(in SomeRange range) { ... } and have foo look at the range and its elements no problem, without actually iterating through the range.
 For example, an array range might have empty be const, but a stream range 
 might not.  What matters is what functions you can use those ranges in, 
 but those are generally templated functions, so the compiler will tell 
 you whether it can be used or not when it tries to compile it.

 Personally, I see no benefit to having empty() be const.  What benefits 
 do you gain by specifically making empty const and the other functions 
 not const?  Presumably, the underlying container must be not const in 
 order for head, next, etc. to work properly, so there is no requirement 
 there.

opIndex should be enough for you to look at anything you want without altering the range itself.

Why not just pass the container itself if the range isn't going to mutate? The container probably already has opIndex, and length (empty AFAIK plays no role here). If it doesn't it seems like a bad design to me. If you have a good example where this is useful, I'd like to hear it.

I need to think that through. Andrei
Jan 26 2009
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Andrei Alexandrescu" wrote
 Probably many people would expect to just write this:

 void foo(in SomeRange range) { ... }

 and have foo look at the range and its elements no problem, without 
 actually iterating through the range.

Consider that some type const Range!(T), where T is a reference that contains the data to be iterated can be copied without casting to a Range!(const T) I think you even filed an enhancement on this, if I'm not mistaken. So a void foo(in SomeRange range) can be rewritten as void foo(ConstSomeRange), and you should technically be able to pass a const(SomeRange) into it. This is because a range is a struct, and aside from the reference to the data, everything else is stack local. Assuming ConstSomeRange is the same as SomeRange but with the data reference being const. -Steve
Jan 26 2009
prev sibling next sibling parent reply Denis Koroskin <2korden gmail.com> writes:
Steven Schveighoffer Wrote:

 "Andrei Alexandrescu" wrote
 I'm working on the new range stuff and the range-based algorithm. In all 
 likelihood, you all might be pleased with the results.

 I wanted to gauge opinions on a couple of issues. One is, should the 
 empty() member function for ranges be const? On the face of it it should, 
 but I don't want that to be a hindrance. I presume non-const empty might 
 be necessary sometimes, e.g. figuring out if a stream is empty effectively 
 means fetching an element off it.

Ranges are structs. It should not matter if you want to make some const and some non-const. Basically, it depends on the range implementation. If you can make it const, make it const, if not, don't make it const. It shouldn't break any APIs. For example, an array range might have empty be const, but a stream range might not. What matters is what functions you can use those ranges in, but those are generally templated functions, so the compiler will tell you whether it can be used or not when it tries to compile it. Personally, I see no benefit to having empty() be const. What benefits do you gain by specifically making empty const and the other functions not const? Presumably, the underlying container must be not const in order for head, next, etc. to work properly, so there is no requirement there. -Steve

Checking if a range is empty() prior to accessing its head is useful. If empty() is const, you can't do that.
Jan 26 2009
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Denis Koroskin" wrote
 On Mon, 26 Jan 2009 23:37:25 +0300, Denis Koroskin <2korden gmail.com> 
 wrote:
 Checking if a range is empty() prior to accessing its head is useful. If 
 empty() is const, you can't do that.

Err.. if empty() is not const and you have a const range reference.

empty not being const does not imply that you can't access a const member. Empty not being const allows all access. The question is whether a wrapping range (or any range for that matter) should implement empty as const, as an empty that IS const cannot call a non-const function of a member. -Steve
Jan 26 2009
next sibling parent Christopher Wright <dhasenan gmail.com> writes:
Denis Koroskin wrote:
 My point is, if empty() returns false (and you can't know it because 
 empty() is not const) you may get either an invalid result, access 
 violation or an exception on member access:
 
 void foo(Range)(const Range r)
 {
    // is r empty? can I /safely/ access its head?
    // let's cross our fingers and try it
    // hoping that it is either not empty or throws an exception
    auto head = r.head;
    ...
 }
 

Then it's good design to implement empty() as const. In some cases, you might not be able to (I believe someone mentioned IO streams as such a case). There, empty() might also throw.
Jan 27 2009
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Denis Koroskin" wrote
 On Tue, 27 Jan 2009 05:13:31 +0300, Steven Schveighoffer 
 <schveiguy yahoo.com> wrote:

 "Denis Koroskin" wrote
 On Mon, 26 Jan 2009 23:37:25 +0300, Denis Koroskin <2korden gmail.com>
 wrote:
 Checking if a range is empty() prior to accessing its head is useful. 
 If
 empty() is const, you can't do that.

Err.. if empty() is not const and you have a const range reference.

empty not being const does not imply that you can't access a const member. Empty not being const allows all access. The question is whether a wrapping range (or any range for that matter) should implement empty as const, as an empty that IS const cannot call a non-const function of a member. -Steve

I didn't say non-const empty restricts any member access, did I?

Sorry, I sort of misinterpreted what you said. You said, "If empty() is const you can't do that." and then sent out a followup email saying "Err.. if empty() is not const and you have a const range reference." I interpreted that as you replacing the statement "If empty() is const" with "if empty() is not const and you have a const range reference," making the complete statement "if empty() is not const and you have a const range reference, you can't do that." Which means I thought you meant, if you have an empty that is not const and a const range reference (which I interpreted as the reference to the data inside the range), then empty cannot access the const member. I see now what you were saying. However, I don't think this is a common situation. A range is a struct so it can be a value type. Having a const reference to a range means you can easily copy everything out of the const range to a non-const range with a const reference to the data. Note that if I parameterize my range based on the data type, const Range!(T) should be implicitly convertable to Range!(const T), where the range itself is made mutable, but the data reference is const. So there is little point to making a range itself const. That being said, I'll also point out that creating a const range reference to access a single element from a range is a very questionable practice, the design might be better served to just access that element directly from the data container itself. Similarly with random access, any container that provides a random access range to its data will most likely also provide an opIndex to get the data directly. Ranges being structs, they are only really useful in functions that already know the data type, or template functions which are told the data type. I don't see any reason why you can't substitute the data structure itself that supplies a length and opIndex member instead of the range. -Steve
Jan 27 2009
prev sibling next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Mon, 26 Jan 2009 23:37:25 +0300, Denis Koroskin <2korden gmail.com> wrote:

 Steven Schveighoffer Wrote:

 "Andrei Alexandrescu" wrote
 I'm working on the new range stuff and the range-based algorithm. In  

 likelihood, you all might be pleased with the results.

 I wanted to gauge opinions on a couple of issues. One is, should the
 empty() member function for ranges be const? On the face of it it  

 but I don't want that to be a hindrance. I presume non-const empty  

 be necessary sometimes, e.g. figuring out if a stream is empty  

 means fetching an element off it.

Ranges are structs. It should not matter if you want to make some const and some non-const. Basically, it depends on the range implementation. If you can make it const, make it const, if not, don't make it const. It shouldn't break any APIs. For example, an array range might have empty be const, but a stream range might not. What matters is what functions you can use those ranges in, but those are generally templated functions, so the compiler will tell you whether it can be used or not when it tries to compile it. Personally, I see no benefit to having empty() be const. What benefits do you gain by specifically making empty const and the other functions not const? Presumably, the underlying container must be not const in order for head, next, etc. to work properly, so there is no requirement there. -Steve

Checking if a range is empty() prior to accessing its head is useful. If empty() is const, you can't do that.

Err.. if empty() is not const and you have a const range reference.
Jan 26 2009
prev sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Tue, 27 Jan 2009 05:13:31 +0300, Steven Schveighoffer <schveiguy yahoo.com>
wrote:

 "Denis Koroskin" wrote
 On Mon, 26 Jan 2009 23:37:25 +0300, Denis Koroskin <2korden gmail.com>
 wrote:
 Checking if a range is empty() prior to accessing its head is useful.  
 If
 empty() is const, you can't do that.

Err.. if empty() is not const and you have a const range reference.

empty not being const does not imply that you can't access a const member. Empty not being const allows all access. The question is whether a wrapping range (or any range for that matter) should implement empty as const, as an empty that IS const cannot call a non-const function of a member. -Steve

I didn't say non-const empty restricts any member access, did I? My point is, if empty() returns false (and you can't know it because empty() is not const) you may get either an invalid result, access violation or an exception on member access: void foo(Range)(const Range r) { // is r empty? can I /safely/ access its head? // let's cross our fingers and try it // hoping that it is either not empty or throws an exception auto head = r.head; ... }
Jan 27 2009