www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - randomAccessRange.sort() vs randomAccessRange.array.sort()

reply "deed" <none none.none> writes:
Why randomAccessRange.array() before calling sort?
The std.algorithm.sort doc says: "Sorts a random-access range ..."


import std.algorithm, std.array;

long[] source = [2, 0, 1];

auto mapped = source.map!("a * 10");
assert (isRandomAccessRange!(typeof(mapped)));   // Passes. 
Implies possibility
                                                  // to to use 
std.algorithm.sort?

auto mappedThenSorted = mapped.sort();           // Error
auto mappedThenSorted = mapped.array.sort();     // Works (and 
used in examples)


What am I missing in the documentation?
Mar 04 2013
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
deed:

 auto mappedThenSorted = mapped.sort();           // Error
 auto mappedThenSorted = mapped.array.sort();     // Works (and 
 used in examples)


 What am I missing in the documentation?
When you try to sort mapped, the D compiler spits out a error message that shows the complex template constraint of sort. You are calling sort using the default unstable algorithm. Here I show the requirements for the unstable sort: import std.algorithm, std.array, std.range; void main() { int[] data = [2, 0, 1]; auto mapped = data.map!q{a * 10}; alias R = typeof(mapped); pragma(msg, hasSwappableElements!R); pragma(msg, hasAssignableElements!R); pragma(msg, isRandomAccessRange!R); pragma(msg, hasSlicing!R); pragma(msg, hasLength!R); // auto r1 = mapped.sort(); // Error // auto r2 = mapped.array.sort(); // OK } It prints: false false true true true Elements generated by a map can't be back-assigned. To help D programmers understand such situations I have asked for this: http://d.puremagic.com/issues/show_bug.cgi?id=9626 Bye, bearophile
Mar 04 2013
parent reply "deed" <none none.none> writes:
 import std.algorithm, std.array, std.range;

 void main() {
     int[] data = [2, 0, 1];

     auto mapped = data.map!q{a * 10};
     alias R = typeof(mapped);

     pragma(msg, hasSwappableElements!R);
     pragma(msg, hasAssignableElements!R);
     pragma(msg, isRandomAccessRange!R);
     pragma(msg, hasSlicing!R);
     pragma(msg, hasLength!R);

 //    auto r1 = mapped.sort();       // Error
 //    auto r2 = mapped.array.sort(); // OK
 }


 It prints:

 false
 false
 true
 true
 true
Meaning sortable ranges are actually a narrow subset of random access ranges? Why aren't the constraints listed in the docs? Are the source files and error messages the only way to get this info?
 Elements generated by a map can't be back-assigned.


 To help D programmers understand such situations I have asked 
 for this:
 http://d.puremagic.com/issues/show_bug.cgi?id=9626
Could be helpful. Example of error message where source has to be investigated: ...\phobos\std\algorithm.d(7946): Error: r[j] is not an lvalue from this file compiled with dmd 2.061: import std.algorithm, std.array, std.range; void main() { long[] slice = [2, -1, -3]; auto mappedSortedSumOfFirstTwo = slice.map!("a ^^ 2"). sort. // causes the error message take(2). reduce!("a + b"); }
Mar 04 2013
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
deed:

 Meaning sortable ranges are actually a narrow subset of random 
 access ranges?
The result of a map() is more like an immutable (lazy) array. A const array is a random access range, but you can't mutate it. To sort it you need a mutable random access range :-)
 Why aren't the constraints listed in the docs?
Maybe because the docs are never finished and never perfect. If you think the docs are not good enough then ask for an improvement in bugzilla, or write a very simple documentation patch.
 Are the source files and error messages the only way to get 
 this info?
I think making the result of a map back-mutable doesn't have a lot of sense.
 Example of error message where source has to be investigated:
If you think you have interesting comments about the bugzilla issue, then it's better to write them in bugzilla. Bye, bearophile
Mar 04 2013
prev sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Monday, 4 March 2013 at 23:55:06 UTC, deed wrote:
 Meaning sortable ranges are actually a narrow subset of random 
 access ranges? Why aren't the constraints listed in the docs? 
 Are the source files and error messages the only way to get 
 this info?
Unless I'm mistaken, this was recently fixed. Are you using 2.062? Having perfectly perfect constraints is a lot of work and review. When we get it wrong, yes, you have to look at source. But contrast this with C++, when you *always* have to look at source or horrible template errors to find out what the error is. D has it good, even when the constraint safety net fails.
Mar 08 2013