range and algorithm-related stuff

[Andrei Alexandrescu]

dsimcha wrote:
> == Quote from Andrei Alexandrescu (SeeWebsiteForEmail at 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