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

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

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/

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

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

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

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.

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

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.

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

I belive he was talking about random-access ranges.
A range.subrange() could also be const, though.