The last changes to range

[Andrei Alexandrescu]

On 05/30/2010 05:11 AM, Philippe Sigaud wrote:
> On Sat, May 29, 2010 at 23:30, Andrei Alexandrescu
> <SeeWebsiteForEmail at erdani.org <mailto: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.

Sounds great!

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

Yah. Essentially R r2 = r1; is not a guarantee that r2 is independent 
from r1. (The obvious case: R is a class or interface type.) You'll need 
to call R r2 = r1.save; to make sure that now you have two 
independently-moving ranges. So yes, save must be a member of all 
forward ranges. isForwardRange will yield false if it doesn't find save.

>             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 input range can be initialized from another input range, with the 
mention that it doesn't leave the original range independent from the 
copy. So Map works as it is.

> 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;
>      }
> }

Lazy and input ranges are not incompatible.

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

More detail please.

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

Yah. A previous attempt at naming was sameHead but I don't want to add 
too many notions.

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

That's a bug in the compiler.


Andrei