www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - The last changes to range

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
I plan to make two more (hopefully the last two) changes to the range 
abstraction this morning.

1. First, I want to define this:

// inside range type SomeRange
 property SomeRange save();

That simply returns a copy of the range. Most implementations look like 
this:

// inside range type SomeRange
 property SomeRange save() { return this; }

If SomeRange is a class or interface, you'd write:

// inside range type SomeRange
 property SomeRange save() { return this->clone(); }

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.

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

All functions are optional and are needed if and only if front(), 
back(), and opIndex() return rvalues. The idea is to provide a cheap 
means to move elements in and out of ranges without creating extra 
copies. There's more detail about this of increased subtlety, please ask.

Of course, swapBack() only makes sense if back() exists and swapAt() 
only makes sense if opIndex exists.

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.

I've posted this to the phobos list as well.


Andrei
May 29 2010
next sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
--0016e6541cf6b18aba0487c12695
Content-Type: text/plain; charset=ISO-8859-1

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

 I plan to make two more (hopefully the last two) changes to the range
 abstraction this morning.

Does that mean that you changed some other parts recently?
 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.
 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.
 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);

 All functions are optional and are needed if and only if front(), back(),
 and opIndex() return rvalues. The idea is to provide a cheap means to move
 elements in and out of ranges without creating extra copies. There's more
 detail about this of increased subtlety, please ask.

Will that be associated with a constraint template? And why methods instead of free functions?
 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

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. Philippe --0016e6541cf6b18aba0487c12695 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <br><div class=3D"gmail_quote">On Sat, May 29, 2010 at 18:45, Andrei Alexan= drescu <span dir=3D"ltr">&lt;<a href=3D"mailto:SeeWebsiteForEmail erdani.or= g">SeeWebsiteForEmail erdani.org</a>&gt;</span> wrote:<br><blockquote class= =3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid= rgb(204, 204, 204); padding-left: 1ex;"> I plan to make two more (hopefully the last two) changes to the range abstr= action this morning.<br></blockquote><div><br>Does that mean that you chang= ed some other parts recently? <br></div><div>=A0</div><blockquote class=3D"= gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb= (204, 204, 204); padding-left: 1ex;"> 1. First, I want to define this:<br> <br> // inside range type SomeRange<br> property SomeRange save();<br></blockquote><div><br>vote++<br>That should = make it clear you need a forward range for an algorithm.<br><br>=A0<br></di= v><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; bor= der-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"> The idea is that save() provides a guaranteed means to take a snapshot in a= range&#39;s state. The notable absents are input ranges - they are unable = to define save(), and therefore some algorithms won&#39;t apply to them.<br=

have a constraint on InputRange that should be changed to ForwardRange. Mo= st (all?) of the lazy ones should probably ask for a ForwardRange. Don&#39;= t forget to update that part.<br> <br></div><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.= 8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"> <br> 2. swapFront, swapBack, and swapAt methods<br> <br> // inside range type SomeRange<br> void swapFront(ref ElementType!SomeRange obj);<br> void swapBack(ref ElementType!SomeRange obj);<br> void swapAt(size_t i, ref ElementType!SomeRange obj);<br> <br> All functions are optional and are needed if and only if front(), back(), a= nd opIndex() return rvalues. The idea is to provide a cheap means to move e= lements in and out of ranges without creating extra copies. There&#39;s mor= e detail about this of increased subtlety, please ask.<br> </blockquote><div><br>Will that be associated with a constraint template? A= nd why methods instead of free functions?<br>=A0<br><br></div><blockquote c= lass=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px s= olid rgb(204, 204, 204); padding-left: 1ex;"> <br> 3. sameFront()<br> <br> The gnarly bringToFront() algorithm needs the primitive:<br> <br> // inside range type SomeRange<br> bool sameFront(SomeRange another);<br> <br> I think it&#39;s necessary for future algorithms as well. It&#39;s an optio= nal primitive. In particular, if front() returns by reference it&#39;s easy= to infer that two ranges have the same front by comparing the addresses of= their front()s.<br> <br></blockquote><div>And if front does not return by ref? Do you then defi= ne the fronts to be different or compare the values?<br><br>About returning= by ref, did you try to use &#39;auto ref&#39;? I think I tried the day the= feature appeared, without success, IIRC. Many ranges in Phobos return by r= ef and won&#39;t compose with other ranges because of that.<br> <br>Philippe<br></div></div> --0016e6541cf6b18aba0487c12695--
May 29 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 05/29/2010 03:05 PM, Philippe Sigaud wrote:
 On Sat, May 29, 2010 at 18:45, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org <mailto:SeeWebsiteForEmail erdani.org>>
 wrote:

     I plan to make two more (hopefully the last two) changes to the
     range abstraction this morning.


 Does that mean that you changed some other parts recently?

Not recently, I think I made the last changes before you joined the gang.
     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.
     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?
     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);

     All functions are optional and are needed if and only if front(),
     back(), and opIndex() return rvalues. The idea is to provide a cheap
     means to move elements in and out of ranges without creating extra
     copies. There's more detail about this of increased subtlety, please
     ask.


 Will that be associated with a constraint template? And why methods
 instead of free functions?

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); } }
     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.
 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. Andrei
May 29 2010
next sibling parent reply Pelle <pelle.mansson gmail.com> writes:
On 05/30/2010 12:11 PM, Philippe Sigaud wrote:
 On Sat, May 29, 2010 at 23:30, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org <mailto:SeeWebsiteForEmail 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.

Worse: string r = "ab"; auto c = cycle(r); // doesn't compile.
May 30 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 05/30/2010 05:43 AM, Pelle wrote:
 string r = "ab";
 auto c = cycle(r); // doesn't compile.

That's a bug in Phobos. Andrei
May 30 2010
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 05/30/2010 05:11 AM, Philippe Sigaud wrote:
 On Sat, May 29, 2010 at 23:30, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org <mailto:SeeWebsiteForEmail 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
May 30 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 05/31/2010 02:20 PM, Philippe Sigaud wrote:
 On Sun, May 30, 2010 at 15:48, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org <mailto:SeeWebsiteForEmail erdani.org>>
 wrote:
         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.


 Out of curiosity, what algorithm did you have in mind?

bringToFront. Andrei
May 31 2010
prev sibling next sibling parent "Masahiro Nakagawa" <repeatedly gmail.com> writes:
On Sun, 30 May 2010 01:45:54 +0900, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 I plan to make two more (hopefully the last two) changes to the range  
 abstraction this morning.

 1. First, I want to define this:

 // inside range type SomeRange
  property SomeRange save();

 That simply returns a copy of the range. Most implementations look like  
 this:

 // inside range type SomeRange
  property SomeRange save() { return this; }

 If SomeRange is a class or interface, you'd write:

 // inside range type SomeRange
  property SomeRange save() { return this->clone(); }

 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 also want save. It allows you to treat some ranges in a unified way. Masahiro
May 29 2010
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--0016e659f444a200c40487ccf696
Content-Type: text/plain; charset=ISO-8859-1

On Sat, May 29, 2010 at 23:30, Andrei Alexandrescu <
SeeWebsiteForEmail 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

// 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 --0016e659f444a200c40487ccf696 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Sat, May 29, 2010 at 23:30, Andrei Alexandres= cu <span dir=3D"ltr">&lt;<a href=3D"mailto:SeeWebsiteForEmail erdani.org">S= eeWebsiteForEmail erdani.org</a>&gt;</span> wrote:<br><blockquote class=3D"= gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb= (204, 204, 204); padding-left: 1ex;"> On 05/29/2010 03:05 PM, Philippe Sigaud wrote:<br> <blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; borde= r-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"> <br><div class=3D"im"> Does that mean that you changed some other parts recently?<br> </div></blockquote> <br> Not recently, I think I made the last changes before you joined the gang.<b= r></blockquote><div><br>OK, I wondered whether std.container had reverberat= ions I wasn&#39;t aware of.<br>Btw, I plan to play with trees and graphs an= d algorithms on them. I will modify my code to respect your container inter= face and see what sticks.<br> <br><br> </div><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex;= border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><blockquote= class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px= solid rgb(204, 204, 204); padding-left: 1ex;"> <div class=3D"im"> =A0 =A01. First, I want to define this:<br> <br> =A0 =A0// inside range type SomeRange<br> =A0 =A0 property SomeRange save();<br> <br> <br></div><div class=3D"im"> vote++<br> That should make it clear you need a forward range for an algorithm.<br> </div></blockquote> <br> Yah.<br></blockquote><div><br>Will the definition of a forward range change= to incorporate save, or do you intend to distinguish ranges that can do<br=
<br>=A0=A0=A0 R r2 =3D r1;<br>and those that have:<br>=A0=A0=A0 auto r2 =

?<br>Until now, they were one and the same to me.<br><br>=A0<br></div><bloc= kquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; border-lef= t: 1px solid rgb(204, 204, 204); padding-left: 1ex;"> <blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; borde= r-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class=3D"im"=

=A0 =A0snapshot in a range&#39;s state. The notable absents are input rang= es -<br> =A0 =A0they are unable to define save(), and therefore some algorithms<br> =A0 =A0won&#39;t apply to them.<br> <br> <br></div><div class=3D"im"> I think many ranges and algorithm that you put in std have a constraint<br> on InputRange that should be changed to ForwardRange. Most (all?) of the<br=

e<br> that part.<br> </div></blockquote> <br> I&#39;m not sure about that. Could you give an example? Why would map() not= work with an input range?<br></blockquote><div><br>Because you make a copy= of the input range in Map&#39;s constructor?<br><br>this(Range input) { _i= nput =3D input; fillCache; }<br> <br>I supposed _input =3D input was not possible with an input range? It&#3= 9;s the very definition of a forward range, no?<br><br>An eager version of = map could use an InputRange as input:<br><br>template eagerMap(alias fun)<b= r> {<br>=A0=A0=A0 typeof(unaryFun!fun(ElementType!R.init))[] eagerMap(R)(R r) = if (isInputRange!R &amp;&amp; !isInfinite!R)<br>=A0=A0=A0 {<br>=A0=A0=A0=A0= =A0=A0=A0 typeof(unaryFun!fun(ElementType!R.init))[] mapped;<br>=A0=A0=A0= =A0=A0=A0=A0 static if (hasLength!R)<br> =A0=A0=A0=A0=A0=A0=A0 {<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 mapped.length = =3D r.length;<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 foreach(i, elem; r) mapp= ed[i] =3D unaryFun!fun(elem);<br>=A0=A0=A0=A0=A0=A0=A0 }<br>=A0=A0=A0=A0=A0= =A0=A0 else<br>=A0=A0=A0=A0=A0=A0=A0 {<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= foreach(elem; r) mapped ~=3D unaryFun!fun(elem); // maybe with an ArrayApp= ender?<br> =A0=A0=A0=A0=A0=A0=A0 }<br>=A0=A0=A0=A0=A0=A0=A0 return mapped;<br>=A0=A0= =A0 }<br>}<br><br>=A0</div><blockquote class=3D"gmail_quote" style=3D"margi= n: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-le= ft: 1ex;"> <blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; borde= r-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class=3D"im"=

<br> =A0 =A0// inside range type SomeRange<br> =A0 =A0void swapFront(ref ElementType!SomeRange obj);<br> =A0 =A0void swapBack(ref ElementType!SomeRange obj);<br> =A0 =A0void swapAt(size_t i, ref ElementType!SomeRange obj);<br> <br></div></blockquote> They will be methods because they must be primitive operations of the respe= ctive ranges. However, there will be wrappers like this:<br> <br> // at module scope<br> void swapFront(Range)(Range r1, Range r2)<br> {<br> =A0 =A0static if (is(typeof(&amp;(r1.front)) =3D=3D ElementType!(Range)*))= {<br> =A0 =A0 =A0 =A0swap(r1.front, r2.front);<br> =A0 =A0} else {<br> =A0 =A0 =A0 =A0static assert(is(typeof(&amp;(r1.swapFront)), &quot;Cannot = swap ranges&quot;);<br> =A0 =A0 =A0 =A0r1.swapFront(r2);<br> =A0 =A0}<br> }<br></blockquote><div><br>OK. I really like this possibility to test for m= embers and activate them when possible. Maybe it could be abstracted away i= nto a Select-like template?<br><br><br></div><blockquote class=3D"gmail_quo= te" style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204= , 204); padding-left: 1ex;"> <blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; borde= r-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class=3D"im"=

<br> =A0 =A0The gnarly bringToFront() algorithm needs the primitive:<br> <br> =A0 =A0// inside range type SomeRange<br> =A0 =A0bool sameFront(SomeRange another);<br> <br> =A0 =A0I think it&#39;s necessary for future algorithms as well. It&#39;s = an<br> =A0 =A0optional primitive. In particular, if front() returns by reference<= br> =A0 =A0it&#39;s easy to infer that two ranges have the same front by compa= ring<br> =A0 =A0the addresses of their front()s.<br> <br></div><div class=3D"im"> And if front does not return by ref? Do you then define the fronts to be<br=

</div></blockquote> <br> If front() does not return by ref, the range should define sameFront() as a= member. If it doesn&#39;t, it won&#39;t have access to a number of algorit= hms.</blockquote><div><br>OK. So it&#39;s really sameFront and not equalFro= nt or somesuch.<br> =A0<br><br><br></div><blockquote class=3D"gmail_quote" style=3D"margin: 0pt= 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1e= x;"><div class=3D"im"> <blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; borde= r-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"> About returning by ref, did you try to use &#39;auto ref&#39;? I think I tr= ied<br> the day the feature appeared, without success, IIRC. Many ranges in<br> Phobos return by ref and won&#39;t compose with other ranges because of tha= t.<br> </blockquote> <br></div> Yah, auto ref was meant for that kind of work. But generally note that cert= ain ranges actively refuse to return by ref in order to not expose addresse= s of their elements. Such ranges are fit for perfectly encapsulated contain= ers.<br> </blockquote><div><br>I was thinking of frustrating obstacles like:<br><br>= auto m =3D map!&quot;a*a&quot;([0,1,2,3]);<br>auto c =3D cycle(m); // won&#= 39;t compile, m.front is not an lvalue, whereas c.front asks for one.<br><b= r> Putting auto ref front() {...} in Cycle does not change anything. Too bad.<= br><br><br>Philippe<br><br></div></div> --0016e659f444a200c40487ccf696--
May 30 2010
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--001636499fd1a6b4a20487e8bf4c
Content-Type: text/plain; charset=ISO-8859-1

On Sun, May 30, 2010 at 15:48, Andrei Alexandrescu <
SeeWebsiteForEmail erdani.org> wrote:

 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.

OK, understood.

mention that it doesn't leave the original range independent from the copy. So Map works as it is.

OK, so map(intputRange) could be affected after its creation by any modification to inputRange, that's coherent. I don't think I was ever confronted to this situation. I tend to discard ranges as I compose them.
 Lazy and input ranges are not incompatible.

I see that now. I really thought that a = b was a no-no for input ranges.
    // 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.

It's just that my code is full of these static ifs. They are clear but I'd like two things: IfPossible!(someCode); // static if (is( typeof())) or __traits(compiles, someCode), then someCode. It's becoming a chore to repeat twice the same line. and: ConditionalCode!(cond1, code1, // static if cond1 then code1 cond2, code2, // else static if cond2 then code2 ... optionalDefaultCode); But I have no solution except by using q{} strings... Maybe with lazy void()?
 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.

Out of curiosity, what algorithm did you have in mind?
  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.

I'll see if I can obtain a simple example and put it in bugzilla, then. --001636499fd1a6b4a20487e8bf4c Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Sun, May 30, 2010 at 15:48, Andrei Alexandres= cu <span dir=3D"ltr">&lt;<a href=3D"mailto:SeeWebsiteForEmail erdani.org">S= eeWebsiteForEmail erdani.org</a>&gt;</span> wrote:<br><blockquote class=3D"= gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb= (204, 204, 204); padding-left: 1ex;"> <blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; borde= r-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class=3D"im"=

Will the definition of a forward range change to incorporate save, or do<br=

<br> =A0 =A0 R r2 =3D r1;<br> and those that have:<br> =A0 =A0 auto r2 =3D r1.save;<br> ?<br> Until now, they were one and the same to me.<br> </div></blockquote><br> <br> Yah. Essentially R r2 =3D r1; is not a guarantee that r2 is independent fro= m r1. (The obvious case: R is a class or interface type.) You&#39;ll need t= o call R r2 =3D r1.save; to make sure that now you have two independently-m= oving ranges. So yes, save must be a member of all forward ranges. isForwar= dRange will yield false if it doesn&#39;t find save.<br> </blockquote><div><br><br>OK, understood.<br>=A0</div><div><br><br> </div><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex;= border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><blockquote= class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px= solid rgb(204, 204, 204); padding-left: 1ex;"> <div class=3D"im">=A0=A0 =A0=A0 <br></div></blockquote> An input range can be initialized from another input range, with the mentio= n that it doesn&#39;t leave the original range independent from the copy. S= o Map works as it is.<br><div class=3D"im"></div></blockquote><div><br>OK, = so map(intputRange) could be affected after its creation by any modificatio= n to inputRange, that&#39;s coherent. I don&#39;t think I was ever confront= ed to this situation. I tend to discard ranges as I compose them.<br> <br>=A0<br></div><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt= 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">= <div class=3D"im"></div> Lazy and input ranges are not incompatible.<br></blockquote><div><br>I see = that now. I really thought that a =3D b was a no-no for input ranges.<br><b= r>=A0</div><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0= .8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"> <blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; borde= r-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class=3D"im"=

=A0 =A0// at module scope<br> =A0 =A0void swapFront(Range)(Range r1, Range r2)<br> =A0 =A0{<br> =A0 =A0 =A0 =A0static if (is(typeof(&amp;(r1.front)) =3D=3D ElementType!(R= ange)*)) {<br> =A0 =A0 =A0 =A0 =A0 =A0swap(r1.front, r2.front);<br> =A0 =A0 =A0 =A0} else {<br> =A0 =A0 =A0 =A0 =A0 =A0static assert(is(typeof(&amp;(r1.swapFront)), &quot= ;Cannot swap ranges&quot;);<br> =A0 =A0 =A0 =A0 =A0 =A0r1.swapFront(r2);<br> =A0 =A0 =A0 =A0}<br> =A0 =A0}<br> <br> <br></div><div class=3D"im"> OK. I really like this possibility to test for members and activate them<br=

template?<br> </div></blockquote> <br> More detail please.<br></blockquote><div><br>It&#39;s just that my code is = full of these static ifs. They are clear but I&#39;d like two things:<br><b= r><br>IfPossible!(someCode); =A0 =A0 =A0 =A0 =A0=A0 // static if (is( typeo= f())) or __traits(compiles, someCode), then someCode. It&#39;s becoming=A0 = a chore to repeat twice the same line.<br> <br><br>and:<br><br><br>ConditionalCode!(cond1, code1,=A0=A0=A0=A0=A0=A0 //= static if cond1 then code1<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 cond2, code2,= =A0=A0=A0=A0=A0 // else static if cond2 then code2<br>...<br>=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0 optionalDefaultCode);<br> <br><br>But I have no solution except by using q{} strings... Maybe with la= zy void()?<br><br><br>=A0</div><blockquote class=3D"gmail_quote" style=3D"m= argin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); paddin= g-left: 1ex;"> <br><blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; b= order-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class=3D= "im"> OK. So it&#39;s really sameFront and not equalFront or somesuch.<br> </div></blockquote><br> <br> Yah. A previous attempt at naming was sameHead but I don&#39;t want to add = too many notions.<br></blockquote><div><br>Out of curiosity, what algorithm= did you have in mind?<br><br>=A0</div><blockquote class=3D"gmail_quote" st= yle=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204)= ; padding-left: 1ex;"> <blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; borde= r-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class=3D"im"=

I was thinking of frustrating obstacles like:<br> <br> auto m =3D map!&quot;a*a&quot;([0,1,2,3]);<br> auto c =3D cycle(m); // won&#39;t compile, m.front is not an lvalue, wherea= s<br> c.front asks for one.<br> <br></div><div class=3D"im"> Putting auto ref front() {...} in Cycle does not change anything. Too bad.<= br> </div></blockquote><br> <br> That&#39;s a bug in the compiler.<br></blockquote><div><br>I&#39;ll see if = I can obtain a simple example and put it in bugzilla, then.<br><br><br></di= v></div> --001636499fd1a6b4a20487e8bf4c--
May 31 2010
prev sibling next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Philippe Sigaud <philippe.sigaud gmail.com> wrote:

 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.

It's just that my code is full of these static ifs. They are clear but I'd like two things: IfPossible!(someCode); // static if (is( typeof())) or __traits(compiles, someCode), then someCode. It's becoming a chore to repeat twice the same line. and: ConditionalCode!(cond1, code1, // static if cond1 then code1 cond2, code2, // else static if cond2 then code2 ... optionalDefaultCode); But I have no solution except by using q{} strings... Maybe with lazy void()?

I see a solution to this in template lambdas. mixin template ifPossible( alias code ) { static if ( __traits( compiles, code ) ) { mixin code; } } mixin ifPossible!( !{ fn( d ); } ); Where !{} is the syntax for an inline-specified template, i.e. a template lambda. Not sure it is worth adding to the language, but I have occasionally wanted it. -- Simen
May 31 2010
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sat, 29 May 2010 12:45:54 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 I plan to make two more (hopefully the last two) changes to the range  
 abstraction this morning.

 1. First, I want to define this:

 // inside range type SomeRange
  property SomeRange save();

 That simply returns a copy of the range. Most implementations look like  
 this:

 // inside range type SomeRange
  property SomeRange save() { return this; }

 If SomeRange is a class or interface, you'd write:

 // inside range type SomeRange
  property SomeRange save() { return this->clone(); }

 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.

In fact, I'd say you'd want to not define save unless it is the trivial case (your example for classes/interfaces shouldn't exist either). The reason being, ranges may be copied multiple times in algorithms, it's generally expected that the copying does not figure into the complexity of an algorithm. I assume that a non-trivial save will be expensive. Expect to see your algorithm blow up in runtime if save is not trivial. -Steve
Jun 01 2010