range and algorithm-related stuff

[Andrei Alexandrescu]

Michel Fortin wrote:
> On 2009-01-24 20:09:07 -0500, Andrei Alexandrescu 
> <SeeWebsiteForEmail at 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