www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - questions around mutating range algorithms, const, and return ref

reply aliak <something something.com> writes:
Hello, I'm trying to write a function called "pull" that, given 2 
ranges, "pull"s the values from range 2 out of range 1. I'm not 
sure if I'm doing it correctly though, and I have some questions 
so any help is appreciated. This is what I have:

ref pull(R1, R2)(return ref R1 r1, R2 r2) {
     import std.algorithm, std.array, std.range;
     int numFound = 0;
     auto r = r1.save;
     ElementType!R1[] unfoundElements;
     foreach (e; r) {
         if (!r2.canFind(e)) {
             unfoundElements ~= e;
         } else {
             numFound++;
         }
     }
     moveEmplaceAll(unfoundElements, r1);
     r1.popBackN(numFound);
     return r1;
}

So my questions are:

1) So first of all, is there a function like this in phobos that 
I can use? From what I understand phobos is supposed to be nogc 
so mutating functions like these are usually in place ones?

2) Is there a way to avoid the extra "moveEmplaceAll" call 
towards the end and still get the same results?

3) Is it necessary to always import std.array (or std.range: 
empty, front) when doing work like this with range algorithms? 
(otherwise you get no property save when an array is used as a 
range)

4) is the .save necessary? My (initial) tests seem to show that 
it works without, but from my understanding of what save does, it 
feels like it's necessary.

5) return ref and -dip25 ... is that something that's going to 
become default at some time? Is there a timeline? (also curious 
about dip1000 for that matter).

6) It will not work when I pass in a range that has const 
elements.

ie:

const(int)[] arr = [1, 2, 3, 4, 5];
arr.pull([2, 3]);

This I guess makes sense because moveEmplaceAll depends on 
isInputRange and from my understanding, a const range cannot be 
one (is that correct?). So am I correct in thinking there really 
is no way around this, or is there some move/cast trickery that I 
can use maybe?

Cheers,
- Ali
Jan 28 2018
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 01/28/2018 02:52 PM, aliak wrote:

 Hello, I'm trying to write a function called "pull" that, given 2
 ranges, "pull"s the values from range 2 out of range 1. I'm not sure if
 I'm doing it correctly though, and I have some questions so any help is
 appreciated. This is what I have:

 ref pull(R1, R2)(return ref R1 r1, R2 r2) {
      import std.algorithm, std.array, std.range;
      int numFound = 0;
      auto r = r1.save;
      ElementType!R1[] unfoundElements;
      foreach (e; r) {
          if (!r2.canFind(e)) {
              unfoundElements ~= e;
          } else {
              numFound++;
          }
      }
      moveEmplaceAll(unfoundElements, r1);
      r1.popBackN(numFound);
      return r1;
 }

 So my questions are:

 1) So first of all, is there a function like this in phobos that I can
 use? From what I understand phobos is supposed to be nogc so mutating
 functions like these are usually in place ones?


I think the following trivial wrapper around std.algorithm.remove() 
should do:

void removeMatching(R, N)(ref R r, N needles) {
     import std.algorithm : remove, canFind;
     r = r.remove!(e => needles.canFind(e));
}

void main() {
     auto arr = [1, 2, 3, 2, 4];
     arr.removeMatching([2, 3]);
     assert(arr == [1, 4]);
}


 2) Is there a way to avoid the extra "moveEmplaceAll" call towards the
 end and still get the same results?


I'm not convinced that unfoundElements is needed at all. :)


 3) Is it necessary to always import std.array (or std.range: empty,
 front) when doing work like this with range algorithms? (otherwise you
 get no property save when an array is used as a range)


I think importing std.range works as well.


 6) It will not work when I pass in a range that has const elements.

 ie:

 const(int)[] arr = [1, 2, 3, 4, 5];
 arr.pull([2, 3]);

 This I guess makes sense because moveEmplaceAll depends on isInputRange
 and from my understanding, a const range cannot be one (is that
 correct?).


Yes but your range is not const, the elements are. So, although 
const(int)[] is a range, it does not have mutable elements.


 So am I correct in thinking there really is no way around
 this, or is there some move/cast trickery that I can use maybe?


You don't want to mutate const elements anyway. It would be breaking a 
promise that other parts of the program may be depending on. I would 
return a filtered-out range:

import std.algorithm;

void main() {
     const(int)[] arr = [1, 2, 3, 2, 4];
     auto result = arr.filter!(e => ![2, 3].canFind(e));
     assert(result.equal([1, 4]));
}

If needed, the caller can easily make an array out of the filtered range 
and the element types will still be const(int):

     import std.range;
     auto arr2 = result.array();
     static assert(is(typeof(arr2) == const(int)[]));


 Cheers,
 - Ali


Ali
Jan 28 2018
parent reply aliak <something something.com> writes:
On Monday, 29 January 2018 at 06:46:26 UTC, Ali Çehreli wrote:

 I think the following trivial wrapper around 
 std.algorithm.remove() should do:

 void removeMatching(R, N)(ref R r, N needles) {
     import std.algorithm : remove, canFind;
     r = r.remove!(e => needles.canFind(e));
 }


Haha awesome! Yes that's much better :)

Note to self: learn to scroll down in the docs to find other 
definitions. I was convinced that remove only acted on indices :p


 I'm not convinced that unfoundElements is needed at all. :)


Can't argue with that :)


 6) It will not work when I pass in a range that has const


 elements.

 ie:

 const(int)[] arr = [1, 2, 3, 4, 5];
 arr.pull([2, 3]);

 This I guess makes sense because moveEmplaceAll depends on


 isInputRange

 and from my understanding, a const range cannot be one (is


 that

 correct?).


 Yes but your range is not const, the elements are. So, although 
 const(int)[] is a range, it does not have mutable elements.


Ah right, yes the range is not const indeed.


 You don't want to mutate const elements anyway. It would be 
 breaking a promise that other parts of the program may be 
 depending on. I would return a filtered-out range:


Right, I want to mutate the range though, not the elements. So 
moving things from one location is not considered as a const 
violation in c++ for eg, maybe the D way is different though? Any 
reading material there?

Also hasMobileElements!(const int[]) is true, so that means I can 
move elements around right?

If I can move elements, that means I should be able to move the 
ones I want to the beginning, of the range, but then I'm also 
unsure about how to go about changing the size of a range.

popBack on a mutable range with const data might cause 
destructors to be called, so I'm going to say that should be ok 
because as a user, if you're calling a range that mutates by 
removing things, and if you try and access those things later 
that's probably along the same lines as removing elements from a 
range that you're "foreach"ing over.

And your second approach is definitely more practical I'd say, 
but I'm going to go about this as a learning exercise in dealing 
with mutations, and const with ranges in D.

Thanks you for the comments!
Jan 29 2018
next sibling parent reply Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On Monday, 29 January 2018 at 11:36:26 UTC, aliak wrote:

 You don't want to mutate const elements anyway. It would be 
 breaking a promise that other parts of the program may be 
 depending on. I would return a filtered-out range:


 Right, I want to mutate the range though, not the elements. So 
 moving things from one location is not considered as a const 
 violation in c++ for eg, maybe the D way is different though?


Consider this case:

immutable(int)[] a = [1,2,3];
immutable(int)* b = &a[1];

You're free to slice the array or pop elements off its front or 
back, but if you change the order of elements, the value that b 
points to will change. D does not allow this.

You can create a new array with the elements moved into the 
locations you want, and with another layer of indirections 
(int*[]) you can move the elements of the array without mutating 
the values.


 Any reading material there?


https://dlang.org/const-faq.html



 Also hasMobileElements!(const int[]) is true, so that means I 
 can move elements around right?


hasMobileElements checks if the value of front can be moved as in 
move constructors, not as in 'can be moved to a different spot in 
the range'. I will admit the name does little to unconfuse this 
point.

--
   Simen
Jan 29 2018
parent reply aliak <something something.com> writes:
On Monday, 29 January 2018 at 12:10:16 UTC, Simen Kjærås wrote:

 Consider this case:

 immutable(int)[] a = [1,2,3];
 immutable(int)* b = &a[1];

 You're free to slice the array or pop elements off its front or 
 back, but if you change the order of elements, the value that b 
 points to will change. D does not allow this.

 You can create a new array with the elements moved into the 
 locations you want, and with another layer of indirections 
 (int*[]) you can move the elements of the array without 
 mutating the values.


Ooh my... yes I can understand that. And I guess immutable is 
implicitly convertible to const and then if you can move const 
stuff then you have that problem. From the FAQ, my general 
understanding is that const is there as a bridge from immutable 
to mutable as a promise that the memory under this symbol will 
not be altered by that reference.

While experimenting a bit I came across this though which, 
currently, I do understand that value of

struct Int {
     const int value;
}

void main() {
     Int i0 = Int(0);
     Int i1 = Int(1);
     Int i2 = Int(2);
     Int[3] arr0 = [i0, i1, i2];
     Int[] arr1;
     arr1 ~= i0;
     arr1 ~= i1;
     arr1 ~= i2;

     arr1[0] = i0; // nope, Error: cannot modify struct arr1[0] 
Int with immutable members
}

So if a struct has a struct that has any member const, then 
effectively that whole struct is a const (well immutable it 
seems, so not even const)? Is that really correct? What is this 
sorcery? If yes I find it very surprising, but I don't think I'm 
very clear on what D is trying to solve with const ... yet.

I find const a little hard to swallow so far. From what I 
understand, it's good for function parameters, and as a function 
attribute for functions that return temporaries, except don't use 
it with ranges (i.e. don't put it on front). Actually not sure 
about function attributes on second thought. So... function 
parameters and local variables that you know won't change is what 
I'm going to go with for now.


 Also hasMobileElements!(const int[]) is true, so that means I 
 can move elements around right?


 hasMobileElements checks if the value of front can be moved as 
 in move constructors, not as in 'can be moved to a different 
 spot in the range'. I will admit the name does little to 
 unconfuse this point.


I'm not following here :s If value of front can be move 
constructed, then something can take it's place no?

Thank you!
Jan 30 2018
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 01/30/2018 12:17 AM, aliak wrote:


 So if a struct has a struct that has any member const, then effectively
 that whole struct is a const (well immutable it seems, so not even
 const)?


No, it cannot be assigned but the other parts of the object can be mutated.


 Is that really correct? What is this sorcery? If yes I find it
 very surprising, but I don't think I'm very clear on what D is trying to
 solve with const ... yet.


It's the same with C++: A type with a const member cannot have a 
compiler-generated assignment operator.


 I find const a little hard to swallow so far. From what I understand,
 it's good for function parameters, and as a function attribute for
 functions that return temporaries, except don't use it with ranges (i.e.
 don't put it on front). Actually not sure about function attributes on
 second thought. So... function parameters and local variables that you
 know won't change is what I'm going to go with for now.


'const' as a member function attribute is meaningful: It makes the 
implicit 'this' parameter const. Same as a function parameter attribute 
in that regard.


 Also hasMobileElements!(const int[]) is true, so that means I can
 move elements around right?


 hasMobileElements checks if the value of front can be moved as in move
 constructors, not as in 'can be moved to a different spot in the
 range'. I will admit the name does little to unconfuse this point.


 I'm not following here :s If value of front can be move constructed,
 then something can take it's place no?


I'm not happy that I can answer that question. At least I opened a bug 
about some part of the confusion recently. :)

   https://issues.dlang.org/show_bug.cgi?id=18036

Ali
Jan 30 2018
parent aliak <something something.com> writes:
On Tuesday, 30 January 2018 at 09:51:18 UTC, Ali Çehreli wrote:

 [...]


 is trying to

 [...]


 It's the same with C++: A type with a const member cannot have 
 a compiler-generated assignment operator.


Ok, that made it obvious :)



 'const' as a member function attribute is meaningful: It makes 
 the implicit 'this' parameter const. Same as a function 
 parameter attribute in that regard.


 [...]






 I can

 [...]




 as in move

 [...]




 the

 [...]




 point.

 [...]


 constructed,

 [...]


 I'm not happy that I can answer that question. At least I 
 opened a bug about some part of the confusion recently. :)

   https://issues.dlang.org/show_bug.cgi?id=18036

 Ali


ah, ok. Gotcha, thanks again, Ali.
Jan 30 2018
prev sibling parent reply Seb <seb wilzba.ch> writes:
On Monday, 29 January 2018 at 11:36:26 UTC, aliak wrote:

 On Monday, 29 January 2018 at 06:46:26 UTC, Ali Çehreli wrote:

 I think the following trivial wrapper around 
 std.algorithm.remove() should do:

 void removeMatching(R, N)(ref R r, N needles) {
     import std.algorithm : remove, canFind;
     r = r.remove!(e => needles.canFind(e));
 }


 Haha awesome! Yes that's much better :)

 Note to self: learn to scroll down in the docs to find other 
 definitions. I was convinced that remove only acted on indices 
 :p


Not too hard to fix: https://github.com/dlang/phobos/pull/6090
Jan 29 2018
parent aliak <something something.com> writes:
On Monday, 29 January 2018 at 13:55:04 UTC, Seb wrote:

 On Monday, 29 January 2018 at 11:36:26 UTC, aliak wrote:

 On Monday, 29 January 2018 at 06:46:26 UTC, Ali Çehreli wrote:

 I think the following trivial wrapper around 
 std.algorithm.remove() should do:

 void removeMatching(R, N)(ref R r, N needles) {
     import std.algorithm : remove, canFind;
     r = r.remove!(e => needles.canFind(e));
 }


 Haha awesome! Yes that's much better :)

 Note to self: learn to scroll down in the docs to find other 
 definitions. I was convinced that remove only acted on indices 
 :p


 Not too hard to fix: https://github.com/dlang/phobos/pull/6090


Nice! :D
Jan 30 2018