The last changes to range

[Philippe Sigaud]

On Sat, May 29, 2010 at 23:30, Andrei Alexandrescu <
SeeWebsiteForEmail at erdani.org> wrote:

> On 05/29/2010 03:05 PM, Philippe Sigaud wrote:
>
>>
>> Does that mean that you changed some other parts recently?
>>
>
> Not recently, I think I made the last changes before you joined the gang.
>

OK, I wondered whether std.container had reverberations I wasn't aware of.
Btw, I plan to play with trees and graphs and algorithms on them. I will
modify my code to respect your container interface and see what sticks.


    1. First, I want to define this:
>>
>>    // inside range type SomeRange
>>    @property SomeRange save();
>>
>>
>> vote++
>> That should make it clear you need a forward range for an algorithm.
>>
>
> Yah.
>

Will the definition of a forward range change to incorporate save, or do you
intend to distinguish ranges that can do

    R r2 = r1;
and those that have:
    auto r2 = r1.save;
?
Until now, they were one and the same to me.



>     The idea is that save() provides a guaranteed means to take a
>>    snapshot in a range's state. The notable absents are input ranges -
>>    they are unable to define save(), and therefore some algorithms
>>    won't apply to them.
>>
>>
>> I think many ranges and algorithm that you put in std have a constraint
>> on InputRange that should be changed to ForwardRange. Most (all?) of the
>> lazy ones should probably ask for a ForwardRange. Don't forget to update
>> that part.
>>
>
> I'm not sure about that. Could you give an example? Why would map() not
> work with an input range?
>

Because you make a copy of the input range in Map's constructor?

this(Range input) { _input = input; fillCache; }

I supposed _input = input was not possible with an input range? It's the
very definition of a forward range, no?

An eager version of map could use an InputRange as input:

template eagerMap(alias fun)
{
    typeof(unaryFun!fun(ElementType!R.init))[] eagerMap(R)(R r) if
(isInputRange!R && !isInfinite!R)
    {
        typeof(unaryFun!fun(ElementType!R.init))[] mapped;
        static if (hasLength!R)
        {
            mapped.length = r.length;
            foreach(i, elem; r) mapped[i] = unaryFun!fun(elem);
        }
        else
        {
            foreach(elem; r) mapped ~= unaryFun!fun(elem); // maybe with an
ArrayAppender?
        }
        return mapped;
    }
}



>     2. swapFront, swapBack, and swapAt methods
>>
>>    // inside range type SomeRange
>>    void swapFront(ref ElementType!SomeRange obj);
>>    void swapBack(ref ElementType!SomeRange obj);
>>    void swapAt(size_t i, ref ElementType!SomeRange obj);
>>
>> They will be methods because they must be primitive operations of the
> respective ranges. However, there will be wrappers like this:
>
> // at module scope
> void swapFront(Range)(Range r1, Range r2)
> {
>    static if (is(typeof(&(r1.front)) == ElementType!(Range)*)) {
>        swap(r1.front, r2.front);
>    } else {
>        static assert(is(typeof(&(r1.swapFront)), "Cannot swap ranges");
>        r1.swapFront(r2);
>    }
> }
>

OK. I really like this possibility to test for members and activate them
when possible. Maybe it could be abstracted away into a Select-like
template?


    3. sameFront()
>>
>>    The gnarly bringToFront() algorithm needs the primitive:
>>
>>    // inside range type SomeRange
>>    bool sameFront(SomeRange another);
>>
>>    I think it's necessary for future algorithms as well. It's an
>>    optional primitive. In particular, if front() returns by reference
>>    it's easy to infer that two ranges have the same front by comparing
>>    the addresses of their front()s.
>>
>> And if front does not return by ref? Do you then define the fronts to be
>> different or compare the values?
>>
>
> If front() does not return by ref, the range should define sameFront() as a
> member. If it doesn't, it won't have access to a number of algorithms.


OK. So it's really sameFront and not equalFront or somesuch.



 About returning by ref, did you try to use 'auto ref'? I think I tried
>> the day the feature appeared, without success, IIRC. Many ranges in
>> Phobos return by ref and won't compose with other ranges because of that.
>>
>
> Yah, auto ref was meant for that kind of work. But generally note that
> certain ranges actively refuse to return by ref in order to not expose
> addresses of their elements. Such ranges are fit for perfectly encapsulated
> containers.
>

I was thinking of frustrating obstacles like:

auto m = map!"a*a"([0,1,2,3]);
auto c = cycle(m); // won't compile, m.front is not an lvalue, whereas
c.front asks for one.

Putting auto ref front() {...} in Cycle does not change anything. Too bad.


Philippe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20100530/0b1a4a1e/attachment-0001.html>