digitalmars.D.learn - Why can't static arrays be sorted?
- TheGag96 (8/8) Oct 04 2016 I was writing some code today and ran into this oddity that I'd
- Vladimir Panteleev (5/13) Oct 04 2016 Static arrays in D are value types. Try:
- Adrian Matoga (3/11) Oct 04 2016 Try:
- Jonathan M Davis via Digitalmars-d-learn (9/17) Oct 04 2016 The problem is that static arrays aren't ranges (calling popFront on the...
- TheGag96 (4/13) Oct 05 2016 Ah thanks guys. I think I just got used to thinking arrays would
- pineapple (4/21) Oct 05 2016 Would just like to point out that this is design weirdness on
- Jonathan M Davis via Digitalmars-d-learn (5/28) Oct 05 2016 It doesn't even make conceptual sense for a static array to be a range,
- =?UTF-8?Q?Ali_=c3=87ehreli?= (5/12) Oct 05 2016 But algorithms like sort() need not require popFront(). I guess we need
- pineapple (5/11) Oct 06 2016 Just because the static array itself isn't a range doesn't mean
- pineapple (7/20) Oct 06 2016 I mean, people post here how often asking why static or dynamic
- notna (2/24) Oct 08 2016 +1000
- Adrian Matoga (3/16) Oct 06 2016 `sort` takes a range. [] gets a range from anything.
- TheGag96 (10/13) Oct 06 2016 Interestingly enough, I found that using .each() actually
- ag0aep6g (7/11) Oct 06 2016 each is not restricted to ranges. It accepts other `foreach`-ables, too....
- Jon Degenhardt (23/36) Oct 08 2016 Thanks! Explains some things. I knew each! was callable in
- TheGag96 (8/11) Oct 10 2016 I think so? It's not being modified in the second case because
- Jonathan M Davis via Digitalmars-d-learn (11/23) Oct 10 2016 Whether it's by value depends entirely on the type of the range. They're
- Jon Degenhardt (46/73) Oct 10 2016 The example I gave uses ref parameters. On the surface it would
- ag0aep6g (23/26) Oct 11 2016 Your ref parameters are only for the per-element operations. You're not
- Jon Degenhardt (11/22) Oct 11 2016 I see. Thanks for the explanation. I wasn't thinking it through
- Jon Degenhardt (5/25) Oct 11 2016 Another perspective where the current behavior could be confusing
I was writing some code today and ran into this oddity that I'd never come across before: import std.algorithm : sort; int[10] arr = [0, 3, 4, 6, 2, 1, 1, 4, 6, 9]; thing.sort(); This doesn't compile. Obviously the .sort property works, but what about static arrays makes them unable to be sorted by std.algorithm.sort? Thanks.
Oct 04 2016
On Tuesday, 4 October 2016 at 20:05:15 UTC, TheGag96 wrote:I was writing some code today and ran into this oddity that I'd never come across before: import std.algorithm : sort; int[10] arr = [0, 3, 4, 6, 2, 1, 1, 4, 6, 9]; thing.sort(); This doesn't compile. Obviously the .sort property works, but what about static arrays makes them unable to be sorted by std.algorithm.sort? Thanks.Static arrays in D are value types. Try: thing[].sort(); This will pass a slice of the array to sort, holding a reference to the static array's data.
Oct 04 2016
On Tuesday, 4 October 2016 at 20:05:15 UTC, TheGag96 wrote:I was writing some code today and ran into this oddity that I'd never come across before: import std.algorithm : sort; int[10] arr = [0, 3, 4, 6, 2, 1, 1, 4, 6, 9]; thing.sort(); This doesn't compile. Obviously the .sort property works, but what about static arrays makes them unable to be sorted by std.algorithm.sort? Thanks.Try: arr[].sort();
Oct 04 2016
On Tuesday, October 04, 2016 20:05:15 TheGag96 via Digitalmars-d-learn wrote:I was writing some code today and ran into this oddity that I'd never come across before: import std.algorithm : sort; int[10] arr = [0, 3, 4, 6, 2, 1, 1, 4, 6, 9]; thing.sort(); This doesn't compile. Obviously the .sort property works, but what about static arrays makes them unable to be sorted by std.algorithm.sort? Thanks.The problem is that static arrays aren't ranges (calling popFront on them can't work, because their length isn't mutable). However, you can slice a static array to get a dynamic array which _is_ a range. e.g. thing[].sort(); Just make sure that such a dynamic array does not outlive the static array, or it will refer to invalid memory (which would not be a problem in this case). - Jonathan M Davis
Oct 04 2016
On Wednesday, 5 October 2016 at 02:19:13 UTC, Jonathan M Davis wrote:The problem is that static arrays aren't ranges (calling popFront on them can't work, because their length isn't mutable). However, you can slice a static array to get a dynamic array which _is_ a range. e.g. thing[].sort(); Just make sure that such a dynamic array does not outlive the static array, or it will refer to invalid memory (which would not be a problem in this case). - Jonathan M DavisAh thanks guys. I think I just got used to thinking arrays would always be found to be ranges by the compiler. Good to know!
Oct 05 2016
On Wednesday, 5 October 2016 at 18:19:27 UTC, TheGag96 wrote:On Wednesday, 5 October 2016 at 02:19:13 UTC, Jonathan M Davis wrote:Would just like to point out that this is design weirdness on Phobos' part - the library I've been writing does not have this problem.The problem is that static arrays aren't ranges (calling popFront on them can't work, because their length isn't mutable). However, you can slice a static array to get a dynamic array which _is_ a range. e.g. thing[].sort(); Just make sure that such a dynamic array does not outlive the static array, or it will refer to invalid memory (which would not be a problem in this case). - Jonathan M DavisAh thanks guys. I think I just got used to thinking arrays would always be found to be ranges by the compiler. Good to know!
Oct 05 2016
On Wednesday, October 05, 2016 19:22:03 pineapple via Digitalmars-d-learn wrote:On Wednesday, 5 October 2016 at 18:19:27 UTC, TheGag96 wrote:It doesn't even make conceptual sense for a static array to be a range, because you can't remove elements from it. - Jonathan M DavisOn Wednesday, 5 October 2016 at 02:19:13 UTC, Jonathan M Davis wrote:Would just like to point out that this is design weirdness on Phobos' part - the library I've been writing does not have this problem.The problem is that static arrays aren't ranges (calling popFront on them can't work, because their length isn't mutable). However, you can slice a static array to get a dynamic array which _is_ a range. e.g. thing[].sort(); Just make sure that such a dynamic array does not outlive the static array, or it will refer to invalid memory (which would not be a problem in this case). - Jonathan M DavisAh thanks guys. I think I just got used to thinking arrays would always be found to be ranges by the compiler. Good to know!
Oct 05 2016
On 10/05/2016 12:30 PM, Jonathan M Davis via Digitalmars-d-learn wrote:On Wednesday, October 05, 2016 19:22:03 pineapple viaDigitalmars-d-learnwrote:But algorithms like sort() need not require popFront(). I guess we need another range type: NonShrinkingRandomAccessRange. :) AliWould just like to point out that this is design weirdness on Phobos' part - the library I've been writing does not have this problem.It doesn't even make conceptual sense for a static array to be a range, because you can't remove elements from it.
Oct 05 2016
On Wednesday, 5 October 2016 at 19:30:01 UTC, Jonathan M Davis wrote:Just because the static array itself isn't a range doesn't mean that it should be necessary to do unintuitive gymnastics with it just to pass it to functions like `sort`.Would just like to point out that this is design weirdness on Phobos' part - the library I've been writing does not have this problem.It doesn't even make conceptual sense for a static array to be a range, because you can't remove elements from it. - Jonathan M Davis
Oct 06 2016
On Thursday, 6 October 2016 at 09:17:08 UTC, pineapple wrote:On Wednesday, 5 October 2016 at 19:30:01 UTC, Jonathan M Davis wrote:I mean, people post here how often asking why static or dynamic arrays aren't being accepted by Phobos' range functions in their code? Maybe Phobos really ought to consider another approach. Accepting things that are _valid_ as ranges and not only things that are ranges themselves has proven to be an effective strategy in mach.Just because the static array itself isn't a range doesn't mean that it should be necessary to do unintuitive gymnastics with it just to pass it to functions like `sort`.Would just like to point out that this is design weirdness on Phobos' part - the library I've been writing does not have this problem.It doesn't even make conceptual sense for a static array to be a range, because you can't remove elements from it. - Jonathan M Davis
Oct 06 2016
On Thursday, 6 October 2016 at 09:23:19 UTC, pineapple wrote:On Thursday, 6 October 2016 at 09:17:08 UTC, pineapple wrote:+1000On Wednesday, 5 October 2016 at 19:30:01 UTC, Jonathan M Davis wrote:I mean, people post here how often asking why static or dynamic arrays aren't being accepted by Phobos' range functions in their code? Maybe Phobos really ought to consider another approach. Accepting things that are _valid_ as ranges and not only things that are ranges themselves has proven to be an effective strategy in mach.Just because the static array itself isn't a range doesn't mean that it should be necessary to do unintuitive gymnastics with it just to pass it to functions like `sort`.Would just like to point out that this is design weirdness on Phobos' part - the library I've been writing does not have this problem.It doesn't even make conceptual sense for a static array to be a range, because you can't remove elements from it. - Jonathan M Davis
Oct 08 2016
On Thursday, 6 October 2016 at 09:17:08 UTC, pineapple wrote:On Wednesday, 5 October 2016 at 19:30:01 UTC, Jonathan M Davis wrote:`sort` takes a range. [] gets a range from anything. It's a convention, not gymnastics.Just because the static array itself isn't a range doesn't mean that it should be necessary to do unintuitive gymnastics with it just to pass it to functions like `sort`.Would just like to point out that this is design weirdness on Phobos' part - the library I've been writing does not have this problem.It doesn't even make conceptual sense for a static array to be a range, because you can't remove elements from it. - Jonathan M Davis
Oct 06 2016
On Wednesday, 5 October 2016 at 19:30:01 UTC, Jonathan M Davis wrote:It doesn't even make conceptual sense for a static array to be a range, because you can't remove elements from it. - Jonathan M DavisInterestingly enough, I found that using .each() actually compiles without the [] but (as expected) creates a copy... So, these output different values: thing.each!((ref x) => writeln(&x)); thing[].each!((ref x) => writeln(&x)); Should there me a more consistent behavior here? Even if the behavior is pretty undesired, why can the compiler consider it a range here but not .sort()?
Oct 06 2016
On 10/06/2016 09:54 PM, TheGag96 wrote:Interestingly enough, I found that using .each() actually compiles without the [][...]why can the compiler consider it a range here but not .sort()?each is not restricted to ranges. It accepts other `foreach`-ables, too. The documentation says that it "also supports opApply-based iterators", but it's really anything that foreach accepts. Relevant piece of the source: https://github.com/dlang/phobos/blob/08c587ead2156c85c30a2bbc18028b5967010682/std/algorithm/iteration.d#L913-L914
Oct 06 2016
On Thursday, 6 October 2016 at 20:11:17 UTC, ag0aep6g wrote:On 10/06/2016 09:54 PM, TheGag96 wrote:Thanks! Explains some things. I knew each! was callable in different circumstances than other functional operations, but hadn't quite figured it out. Looks like reduce! and fold! also take iterables. There also appears to be a distinction between the iterator and range cases when a ref parameter is used. As it iterator, each! won't modify the reference. Example: void main() { import std.algorithm : each; int[] dynamicArray = [1, 2, 3, 4, 5]; int[5] staticArray = [1, 2, 3, 4, 5]; dynamicArray.each!((ref x) => x++); assert(dynamicArray == [2, 3, 4, 5, 6]); // modified staticArray.each!((ref x) => x++); assert(staticArray == [1, 2, 3, 4, 5]); // not modified staticArray[].each!((ref x) => x++); assert(staticArray == [2, 3, 4, 5, 6]); // modified } This distinction is a bit on the nuanced side. Is it behaving as it should? --JonInterestingly enough, I found that using .each() actually compiles without the [][...]why can the compiler consider it a range here but not .sort()?each is not restricted to ranges. It accepts other `foreach`-ables, too. The documentation says that it "also supports opApply-based iterators", but it's really anything that foreach accepts. [snip]
Oct 08 2016
On Saturday, 8 October 2016 at 21:14:43 UTC, Jon Degenhardt wrote:This distinction is a bit on the nuanced side. Is it behaving as it should? --JonI think so? It's not being modified in the second case because the array is being passed by value... "x" there is a reference to an element of the copy created to be passed to each(). I assume there's a good reason why ranges in general are passed by value into these functions -- except in this one case, the stuff inside range types copied when passed by value won't be whole arrays, I'm guessing.
Oct 10 2016
On Monday, October 10, 2016 16:29:41 TheGag96 via Digitalmars-d-learn wrote:On Saturday, 8 October 2016 at 21:14:43 UTC, Jon Degenhardt wrote:Whether it's by value depends entirely on the type of the range. They're passed around, and copying them has whatever semantics it has. In most cases, it copies the state of the range but doesn't copy all of the elements (e.g. that's what happens with a dynamic array, since it gets sliced). But if a range is a class, then it's definitely a reference type. The only way to properly save the state of a range is to call save. But passing by ref would make no sense at all with input ranges. It would completely kill chaining them. Almost all range-based functions return rvalues. - Jonathan M DavisThis distinction is a bit on the nuanced side. Is it behaving as it should? --JonI think so? It's not being modified in the second case because the array is being passed by value... "x" there is a reference to an element of the copy created to be passed to each(). I assume there's a good reason why ranges in general are passed by value into these functions -- except in this one case, the stuff inside range types copied when passed by value won't be whole arrays, I'm guessing.
Oct 10 2016
On Monday, 10 October 2016 at 16:46:55 UTC, Jonathan M Davis wrote:On Monday, October 10, 2016 16:29:41 TheGag96 via Digitalmars-d-learn wrote:The example I gave uses ref parameters. On the surface it would seem reasonable to that passing a static array by ref would allow it to be modified, without having to slice it first. The documentation says: // If the range supports it, the value can be mutated in place arr.each!((ref n) => n++); assert(arr == [1, 2, 3, 4, 5]); but, 'arr' is a dynamic array, so technically it's not describing a static array (the opApply case). Expanding the example, using foreach with ref parameters will modify the static array in place, without slicing it. I would have expected each! with a ref parameter to behave the same. At a minimum this could be better documented, but it may also be a bug. Example: T increment(T)(ref T x) { return x++; } void main() { import std.algorithm : each; int[] dynamicArray = [1, 2, 3, 4, 5]; int[5] staticArray = [1, 2, 3, 4, 5]; dynamicArray.each!(x => x++); // Dynamic array by value assert(dynamicArray == [1, 2, 3, 4, 5]); // ==> Not modified dynamicArray.each!((ref x) => x++); // Dynamic array by ref assert(dynamicArray == [2, 3, 4, 5, 6]); // ==> Modified staticArray[].each!((ref x) => x++); // Slice of static array, by ref assert(staticArray == [2, 3, 4, 5, 6]); // ==> Modified staticArray.each!((ref x) => x++); // Static array by ref assert(staticArray == [2, 3, 4, 5, 6]); // ==> Not Modified /* Similar to above, using foreach and ref params. */ foreach (ref x; dynamicArray) x.increment; assert(dynamicArray == [3, 4, 5, 6, 7]); // Dynamic array => Modified foreach (ref x; staticArray[]) x.increment; assert(staticArray == [3, 4, 5, 6, 7]); // Static array slice => Modified foreach (ref x; staticArray) x.increment; assert(staticArray == [4, 5, 6, 7, 8]); // Static array => Modified }On Saturday, 8 October 2016 at 21:14:43 UTC, Jon Degenhardt wrote:Whether it's by value depends entirely on the type of the range. They're passed around, and copying them has whatever semantics it has. In most cases, it copies the state of the range but doesn't copy all of the elements (e.g. that's what happens with a dynamic array, since it gets sliced). But if a range is a class, then it's definitely a reference type. The only way to properly save the state of a range is to call save. But passing by ref would make no sense at all with input ranges. It would completely kill chaining them. Almost all range-based functions return rvalues. - Jonathan M DavisThis distinction is a bit on the nuanced side. Is it behaving as it should? --JonI think so? It's not being modified in the second case because the array is being passed by value... "x" there is a reference to an element of the copy created to be passed to each(). I assume there's a good reason why ranges in general are passed by value into these functions -- except in this one case, the stuff inside range types copied when passed by value won't be whole arrays, I'm guessing.
Oct 10 2016
On 10/11/2016 06:24 AM, Jon Degenhardt wrote:The example I gave uses ref parameters. On the surface it would seem reasonable to that passing a static array by ref would allow it to be modified, without having to slice it first.Your ref parameters are only for the per-element operations. You're not passing the array as a whole by reference. And you can't, because `each` itself takes the whole range by copy. So, the by-ref increments themselves do work, but they're applied to a copy of your original static array. Question is, should `each` 1) take all inputs (ranges, arrays, other foreachables) by reference, or 2) take some inputs (like static arrays) by reference, or 3) take all inputs by value (current behavior)? shuffling to be acceptable. Would also need to make sure that this is actually the most desirable behavior. tell for sure if a range needs to be passed by reference in order to see updates to its elements. I'd be against this. that that one doesn't have worse corner cases. I don't see any deal breakers, but that doesn't mean they're not there ;) an effort not only for the implementer, but also for the users who have to update all their code.
Oct 11 2016
On Tuesday, 11 October 2016 at 18:18:41 UTC, ag0aep6g wrote:On 10/11/2016 06:24 AM, Jon Degenhardt wrote:I see. Thanks for the explanation. I wasn't thinking it through properly. Also, I guess I had assumed that the intent was that each! be able to modify the elements, and therefore the whole array it would be pass by reference, but didn't consider it properly. I'm not going to make any suggestions about whether the behavior should be changed. At some point when I get a bit of time I'll try to submit a documentation change to make the current behavior clearer. --JonThe example I gave uses ref parameters. On the surface it would seem reasonable to that passing a static array by ref would allow it to be modified, without having to slice it first.Your ref parameters are only for the per-element operations. You're not passing the array as a whole by reference. And you can't, because `each` itself takes the whole range by copy. So, the by-ref increments themselves do work, but they're applied to a copy of your original static array.
Oct 11 2016
On Tuesday, 11 October 2016 at 19:46:31 UTC, Jon Degenhardt wrote:On Tuesday, 11 October 2016 at 18:18:41 UTC, ag0aep6g wrote:Another perspective where the current behavior could be confusing is that it is somewhat natural to assume that 'each' is the functional equivalent of foreach, and that they can be used interchangeably. However, for static arrays they cannot be.On 10/11/2016 06:24 AM, Jon Degenhardt wrote:I see. Thanks for the explanation. I wasn't thinking it through properly. Also, I guess I had assumed that the intent was that each! be able to modify the elements, and therefore the whole array it would be pass by reference, but didn't consider it properly.The example I gave uses ref parameters. On the surface it would seem reasonable to that passing a static array by ref would allow it to be modified, without having to slice it first.Your ref parameters are only for the per-element operations. You're not passing the array as a whole by reference. And you can't, because `each` itself takes the whole range by copy. So, the by-ref increments themselves do work, but they're applied to a copy of your original static array.
Oct 11 2016