www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - sortOn: sorts range of aggregates by member name(s)

reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
Has there been any proposals to add a sort-wrapper, say sortBy,

in cases such as

     struct X { double x, y, z; }
     auto r = new X[3];

used as

     r.sortBy!("x", "y")

sorting r by value of "x" then "y".

If not and anybody is interest I could write one and make PR in 
std.algorithm.
Nov 04 2014
parent reply "Meta" <jared771 gmail.com> writes:
On Wednesday, 5 November 2014 at 00:32:32 UTC, Nordlöw wrote:

 Has there been any proposals to add a sort-wrapper, say sortBy,

 in cases such as

     struct X { double x, y, z; }
     auto r = new X[3];

 used as

     r.sortBy!("x", "y")

 sorting r by value of "x" then "y".

 If not and anybody is interest I could write one and make PR in 
 std.algorithm.


I think you're looking for multiSort.
Nov 04 2014
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Wednesday, 5 November 2014 at 00:34:54 UTC, Meta wrote:

 On Wednesday, 5 November 2014 at 00:32:32 UTC, Nordlöw wrote:

 Has there been any proposals to add a sort-wrapper, say sortBy,

 in cases such as

    struct X { double x, y, z; }
    auto r = new X[3];

 used as

    r.sortBy!("x", "y")

 sorting r by value of "x" then "y".

 If not and anybody is interest I could write one and make PR 
 in std.algorithm.


 I think you're looking for multiSort.




That's not the same, it requires to specify a comparison 
function. Nordlöw wants to specify an attribute.

This could also be an arbitrary expression, of course:

     r.sortBy!"x*x + y*y + z*z"

The above could be implemented using `with` and 
`std.functional.unaryFun`. Alternatively, a lambda could be used:

     r.sortBy!(a => a.norm);
Nov 05 2014
next sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Wednesday, 5 November 2014 at 11:18:56 UTC, Marc Schütz wrote:

 This could also be an arbitrary expression, of course:

     r.sortBy!"x*x + y*y + z*z"

 The above could be implemented using `with` and 
 `std.functional.unaryFun`. Alternatively, a lambda could be 
 used:

     r.sortBy!(a => a.norm);


Ok. Great. What do you think about the name sortBy?
Nov 05 2014
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Wednesday, 5 November 2014 at 14:07:10 UTC, Nordlöw wrote:

 On Wednesday, 5 November 2014 at 11:18:56 UTC, Marc Schütz 
 wrote:

 This could also be an arbitrary expression, of course:

    r.sortBy!"x*x + y*y + z*z"

 The above could be implemented using `with` and 
 `std.functional.unaryFun`. Alternatively, a lambda could be 
 used:

    r.sortBy!(a => a.norm);


 Ok. Great. What do you think about the name sortBy?


It's intuitive and concise. Plus, Ruby uses `sort` and `sort_by` 
for the same functionality, exactly in parallel, so it will be 
familiar to many users.
Nov 05 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Wednesday, 5 November 2014 at 14:36:11 UTC, Marc Schütz wrote:

 It's intuitive and concise. Plus, Ruby uses `sort` and 
 `sort_by` for the same functionality, exactly in parallel, so 
 it will be familiar to many users.


Here's my first working but primitive version.

https://github.com/nordlow/justd/blob/master/sort_ex.d#L15

How do I extend it to support

- variadic number of extractors
- sortBy("x")

?
Nov 05 2014
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Wednesday, 5 November 2014 at 16:07:40 UTC, Nordlöw wrote:

 On Wednesday, 5 November 2014 at 14:36:11 UTC, Marc Schütz 
 wrote:

 It's intuitive and concise. Plus, Ruby uses `sort` and 
 `sort_by` for the same functionality, exactly in parallel, so 
 it will be familiar to many users.


 Here's my first working but primitive version.

 https://github.com/nordlow/justd/blob/master/sort_ex.d#L15

 How do I extend it to support

 - variadic number of extractors
 - sortBy("x")


My idea was something along these lines (untested):

     template extractorFun(alias extractor) {
         static if(is(typeof(extractor) : string)) {
             auto ref extractorFun(T)(auto ref T a) {
                 mixin("with(a) { return " ~ extractor ~ "; }");
             }
         } else {
             alias extractorFun = extractor;
         }
     }

     alias fn = extractorFun!extractor;
     r.sort!((a, b) => (fn(a) < fn(b)));
Nov 05 2014
next sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Wednesday, 5 November 2014 at 16:54:38 UTC, Marc Schütz wrote:

 My idea was something along these lines (untested):

     template extractorFun(alias extractor) {
         static if(is(typeof(extractor) : string)) {
             auto ref extractorFun(T)(auto ref T a) {
                 mixin("with(a) { return " ~ extractor ~ "; }");
             }
         } else {
             alias extractorFun = extractor;
         }
     }

     alias fn = extractorFun!extractor;
     r.sort!((a, b) => (fn(a) < fn(b)));


Thanks, I'll use this!

Still, is it even possible to extend extractor to become variadic 
or do I have to write a number of explicit overloads

1: void sortBy(alias xtr, R)(R r)
2: void sortBy(alias xtrA, alias xtrB, R)(R r)
3: void sortBy(alias xtrA, alias xtrB, alias xtrC, R)(R r)
etc

?
Nov 05 2014
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Wednesday, 5 November 2014 at 20:50:00 UTC, Nordlöw wrote:

 On Wednesday, 5 November 2014 at 16:54:38 UTC, Marc Schütz 
 wrote:

 My idea was something along these lines (untested):

    template extractorFun(alias extractor) {
        static if(is(typeof(extractor) : string)) {
            auto ref extractorFun(T)(auto ref T a) {
                mixin("with(a) { return " ~ extractor ~ "; }");
            }
        } else {
            alias extractorFun = extractor;
        }
    }

    alias fn = extractorFun!extractor;
    r.sort!((a, b) => (fn(a) < fn(b)));


 Thanks, I'll use this!

 Still, is it even possible to extend extractor to become 
 variadic or do I have to write a number of explicit overloads

 1: void sortBy(alias xtr, R)(R r)
 2: void sortBy(alias xtrA, alias xtrB, R)(R r)
 3: void sortBy(alias xtrA, alias xtrB, alias xtrC, R)(R r)
 etc

 ?


Again untested:

private alias makePredicate(alias xtr) =
     (a, b) => (extractorFun!xtr(a) < extractorFun!xtr(b));

auto sortBy(extractors..., R)(R r) {
     alias preds = staticMap!(makePredicate, extractors);
     return r.sort!preds;
}

(Variadic template parameters also accept aliases.)
Nov 05 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Wednesday, 5 November 2014 at 21:29:20 UTC, Marc Schütz wrote:

 Again untested:

 private alias makePredicate(alias xtr) =
     (a, b) => (extractorFun!xtr(a) < extractorFun!xtr(b));


This errors as

sort_ex.d(35,43): Error: basic type expected, not (
sort_ex.d(35,43): Error: function declaration without return 
type. (Note that constructors are always named 'this')
sort_ex.d(35,50): Error: semicolon expected to close alias 
declaration
sort_ex.d(35,50): Error: Declaration expected, not '=>'


 auto sortBy(extractors..., R)(R r) {
     alias preds = staticMap!(makePredicate, extractors);
     return r.sort!preds;
 }


and this as

sort_ex.d(37,6): Error: template sort_ex.sortBy(xtors..., R)(R r) 
template tuple parameter must be last one
Nov 06 2014
parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Thursday, 6 November 2014 at 09:13:07 UTC, Nordlöw wrote:

 On Wednesday, 5 November 2014 at 21:29:20 UTC, Marc Schütz 
 wrote:

 Again untested:

 private alias makePredicate(alias xtr) =
    (a, b) => (extractorFun!xtr(a) < extractorFun!xtr(b));


 This errors as

 sort_ex.d(35,43): Error: basic type expected, not (
 sort_ex.d(35,43): Error: function declaration without return 
 type. (Note that constructors are always named 'this')
 sort_ex.d(35,50): Error: semicolon expected to close alias 
 declaration
 sort_ex.d(35,50): Error: Declaration expected, not '=>'


It probably needs to be spelled out as function/delegate literal 
(sorry, don't have much time now).


 auto sortBy(extractors..., R)(R r) {
    alias preds = staticMap!(makePredicate, extractors);
    return r.sort!preds;
 }


 and this as

 sort_ex.d(37,6): Error: template sort_ex.sortBy(xtors..., R)(R 
 r) template tuple parameter must be last one


Try nesting the templates, then the tuple can come first:

     template sortBy(extractors...) {
         auto sortBy(R)(R r) {
             // ...
         }
     }

This should then be usable as `sortBy!("x", "y")(range)`.
Nov 06 2014
prev sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Wednesday, 5 November 2014 at 16:54:38 UTC, Marc Schütz wrote:

 On Wednesday, 5 November 2014 at 16:07:40 UTC, Nordlöw wrote:

 On Wednesday, 5 November 2014 at 14:36:11 UTC, Marc Schütz 
 wrote:

 It's intuitive and concise. Plus, Ruby uses `sort` and 
 `sort_by` for the same functionality, exactly in parallel, so 
 it will be familiar to many users.


 Here's my first working but primitive version.

 https://github.com/nordlow/justd/blob/master/sort_ex.d#L15

 How do I extend it to support

 - variadic number of extractors
 - sortBy("x")


 My idea was something along these lines (untested):

     template extractorFun(alias extractor) {
         static if(is(typeof(extractor) : string)) {
             auto ref extractorFun(T)(auto ref T a) {
                 mixin("with(a) { return " ~ extractor ~ "; }");
             }
         } else {
             alias extractorFun = extractor;
         }
     }

     alias fn = extractorFun!extractor;
     r.sort!((a, b) => (fn(a) < fn(b)));


Works! Thanks!

One thing: I tried to add support for integer based member 
indexing via tupleof at

https://github.com/nordlow/justd/blob/master/sort_ex.d#L21

but it errors as

sort_ex.d(42,46): Error: function expected before (), not 0 of 
type int
sort_ex.d(43,46): Error: function expected before (), not 0 of 
type int
sort_ex.d(42,6):        instantiated from here: sort!((a, b) => 
extractorFun!extractor(a) < extractorFun!extractor(b), 
cast(SwapStrategy)0, X[])
sort_ex.d(80,6):        instantiated from here: sortBy!(0, X[])
/home/per/opt/x86_64-unknown-linux-gnu/dmd/linux/bin64/src/phobos/std/a
gorithm.d(10266,9): 
Error: static assert  "Invalid predicate passed to sort: 
__lambda2"
sort_ex.d(42,6):        instantiated from here: sort!((a, b) => 
extractorFun!extractor(a) < extractorFun!extractor(b), 
cast(SwapStrategy)0, X[])
sort_ex.d(80,6):        instantiated from here: sortBy!(0, X[])

when I uncomment the last three tests. What's wrong?
Nov 05 2014
parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Wednesday, 5 November 2014 at 23:40:23 UTC, Nordlöw wrote:

 when I uncomment the last three tests. What's wrong?


Solved it :)
Nov 05 2014
prev sibling next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Marc Schütz:


     r.sortBy!(a => a.norm);


r.schwartzSort!(a => a.norm);

Bye,
bearophile
Nov 05 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Wednesday, 5 November 2014 at 14:52:38 UTC, bearophile wrote:

 Marc Schütz:


    r.sortBy!(a => a.norm);


 r.schwartzSort!(a => a.norm);

 Bye,
 bearophile


Ok, but this doesn't support multi-sorting, right?
Nov 05 2014
parent "bearophile" <bearophileHUGS lycos.com> writes:
Nordlöw:


 Ok, but this doesn't support multi-sorting, right?


If performance is not a top priority, you can use a tuple:

r.schwartzSort!(x => tuple(x.a, x.b, x.c));

Bye,
bearophile
Nov 05 2014
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/5/14 12:18 PM, "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net>" 
wrote:

 On Wednesday, 5 November 2014 at 00:34:54 UTC, Meta wrote:

 On Wednesday, 5 November 2014 at 00:32:32 UTC, Nordlöw wrote:

 Has there been any proposals to add a sort-wrapper, say sortBy,

 in cases such as

    struct X { double x, y, z; }
    auto r = new X[3];

 used as

    r.sortBy!("x", "y")

 sorting r by value of "x" then "y".

 If not and anybody is interest I could write one and make PR in
 std.algorithm.


 I think you're looking for multiSort.




 That's not the same, it requires to specify a comparison function.
 Nordlöw wants to specify an attribute.

 This could also be an arbitrary expression, of course:

      r.sortBy!"x*x + y*y + z*z"

 The above could be implemented using `with` and
 `std.functional.unaryFun`. Alternatively, a lambda could be used:

      r.sortBy!(a => a.norm);


sortBy!(expr) is equivalent with sort!(expr_a < expr_b) so there's no 
additional power to it. However, it does make some sorting criteria 
easier to write. A while ago I took a related diff pretty far but in the 
end decided to discard it because it didn't add sufficient value.

Andrei
Nov 09 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Sunday, 9 November 2014 at 08:12:37 UTC, Andrei Alexandrescu 
wrote:

 sortBy!(expr) is equivalent with sort!(expr_a < expr_b) so 
 there's no additional power to it. However, it does make some 
 sorting criteria easier to write. A while ago I took a related 
 diff pretty far but in the end decided to discard it because it 
 didn't add sufficient value.


What do you mean by sufficient value?

Ruby has sort_by. I believe D would when possible should be a 
superset of the union of powers available in other languages to 
maximize the ease of porting code *to* D and the pleasure for 
programmers to switch to D. I'll try to make this elegant and 
useful and use it myself for a while. If it works for me I'll do 
a PR still. Ok?
Nov 09 2014
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Nordlöw:


 What do you mean by sufficient value?


Every thing you add to Phobos std.algorithm&std.range increases 
the amount of things D programmers have to understand and keep in 
_active memory_. So you have to balance the desire to add 
specialized functionality with the desire to keep that complexity 
low. And I think adding sortBy isn't a good idea.

If you really want to do something like that, I think it's better 
to add something more like Python "operator.attrgetter" 
(https://docs.python.org/2/library/operator.html ), that can be 
used with the standard sort:

items.sort!(fieldGetter("field1", "field2"));

Bye,
bearophile
Nov 09 2014
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/9/14 4:49 AM, "Nordlöw" wrote:

 On Sunday, 9 November 2014 at 08:12:37 UTC, Andrei Alexandrescu wrote:

 sortBy!(expr) is equivalent with sort!(expr_a < expr_b) so there's no
 additional power to it. However, it does make some sorting criteria
 easier to write. A while ago I took a related diff pretty far but in
 the end decided to discard it because it didn't add sufficient value.


 What do you mean by sufficient value?


It seemed to me just another way of doing the same things.


 Ruby has sort_by. I believe D would when possible should be a superset
 of the union of powers available in other languages to maximize the ease
 of porting code *to* D and the pleasure for programmers to switch to D.


Sadly things don't work that way - e.g. Phobos1 took a bunch of string 
functions from Ruby and Python, to no notable effect.


 I'll try to make this elegant and useful and use it myself for a while.
 If it works for me I'll do a PR still. Ok?


That's a better approach, thanks. A few compelling examples would help.


Andrei
Nov 09 2014
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:


 Sadly things don't work that way - e.g. Phobos1 took a bunch of 
 string functions from Ruby and Python, to no notable effect.


If you port Python code to D (and this is something I do almost 
every day) the Phobos string functions help making the porting 
simpler.

Bye,
bearophile
Nov 10 2014
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/10/14 12:56 AM, bearophile wrote:

 Andrei Alexandrescu:


 Sadly things don't work that way - e.g. Phobos1 took a bunch of string
 functions from Ruby and Python, to no notable effect.


 If you port Python code to D (and this is something I do almost every
 day) the Phobos string functions help making the porting simpler.

 Bye,
 bearophile


Good to know, thanks! -- Andrei
Nov 10 2014
prev sibling next sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Monday, 10 November 2014 at 03:38:49 UTC, Andrei Alexandrescu 
wrote:

 That's a better approach, thanks. A few compelling examples 
 would help.


 Andrei


One more thing. How should reverse sorting be handled in elegant 
way? Like this

https://github.com/nordlow/justd/blob/master/sort_ex.d#L57

or via some other clever solution I haven't thought about?
Nov 10 2014
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/10/14 11:58 AM, "Nordlöw" wrote:

 On Monday, 10 November 2014 at 03:38:49 UTC, Andrei Alexandrescu wrote:

 That's a better approach, thanks. A few compelling examples would help.


 Andrei


 One more thing. How should reverse sorting be handled in elegant way?
 Like this

 https://github.com/nordlow/justd/blob/master/sort_ex.d#L57

 or via some other clever solution I haven't thought about?


For most numeric cases having the caller negate the key should suffice. 
For string types you'd need a separate function or fall back to classic 
sort. This, too, doesn't bode well for the power/weight ratio of sortBy. 
-- Andrei
Nov 10 2014
prev sibling parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Monday, 10 November 2014 at 19:58:32 UTC, Nordlöw wrote:

 On Monday, 10 November 2014 at 03:38:49 UTC, Andrei 
 Alexandrescu wrote:

 That's a better approach, thanks. A few compelling examples 
 would help.


 Andrei


 One more thing. How should reverse sorting be handled in 
 elegant way? Like this

 https://github.com/nordlow/justd/blob/master/sort_ex.d#L57

 or via some other clever solution I haven't thought about?


By chaining it with std.range.retro? But this will of course be 
lazy, and will lose the information that the range is sorted.

Maybe there doesn't need to be a special facility for that, if 
it's allowed to specify arbitrary expressions?

     container.sortBy!(a =>  a.intMember)    // ascending
     container.sortBy!(a => -a.intMember)    // descending

Or shorter (the expression will be mixed in):

     container.sortBy!" intMember";          // ascending
     container.sortBy!"-intMember";          // descending
Nov 10 2014
prev sibling parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Monday, 10 November 2014 at 03:38:49 UTC, Andrei Alexandrescu 
wrote:

 On 11/9/14 4:49 AM, "Nordlöw" wrote:

 On Sunday, 9 November 2014 at 08:12:37 UTC, Andrei 
 Alexandrescu wrote:

 sortBy!(expr) is equivalent with sort!(expr_a < expr_b) so 
 there's no
 additional power to it. However, it does make some sorting 
 criteria
 easier to write. A while ago I took a related diff pretty far 
 but in
 the end decided to discard it because it didn't add 
 sufficient value.


 What do you mean by sufficient value?


 It seemed to me just another way of doing the same things.


 Ruby has sort_by. I believe D would when possible should be a 
 superset
 of the union of powers available in other languages to 
 maximize the ease
 of porting code *to* D and the pleasure for programmers to 
 switch to D.


 Sadly things don't work that way - e.g. Phobos1 took a bunch of 
 string functions from Ruby and Python, to no notable effect.


 I'll try to make this elegant and useful and use it myself for 
 a while.
 If it works for me I'll do a PR still. Ok?


 That's a better approach, thanks. A few compelling examples 
 would help.


A positive point about it would be that it's more intuitive to 
read, especially with long names or complex expressions.

     // sort vectors by length
     container.sortBy!"x*x + y*y";
     // vs.
     container.sort!((a,b) => a.x*a.x + a.y*a.y < b.x*b.x + 
b.y*b.y);
Nov 10 2014