Perl 6 sorting (was: Re: Sort: By keys, values, and their returning values.)

[moritz]

Allow me show off some Perl 6 features here.

If you use a hash in list context in Perl 6, you get a list of pairs, each holding a key and a value.

Since hashes are object like everything else, you can call methods on them:

my @sorted_keys = %hash.keys.sort

Since values are typed (ie you can ask a variable if it contains a number, a string or something entirely different), the default comparison is smart enough to compare strings with string semantics and numbers with number semantics. So if the values are numbers already, there's no need to explicitly use <=>

It is even smart enough to compare pairs, so when you call %hash.sort directly, it sorts primary by key and secondary by value.

What if you want to sort the keys by value? You use the built-in Schwartzian transform:

%hash.keys.sort({ %hash{$_} });

Since the block { %hash{$_} } knows its number of parameters, the sort method can find out that the block takes not two but one parameter, and sorts by the return value of the block, while still returning the original value.

If you want to do that on an anonymous hash, you can sort the pairs instead:

# return a random, anonymous hash:
sub h {
   return %( (1..10).pick(*) )
}

# and get the keys sorted numerically by value:
my @keys = h().sort( { .value })>>.key

This sorts the pairs by value, and then calls the .key method on each list item. (so >>.key is short for .map({ .key }), except that the compiler is allowed to execute the >>.key calls out of order, and parallelize them)

Having Pair objects and a built-in Schwartzian transform makes sorting really simple and powerful. And Rakudo implements all of this already. Have fun experimenting!

[salva]

Having Pair objects and a built-in Schwartzian transform makes sorting really simple and powerful

I hope you are not really using the Schwartzian transform in Rakudo as it is one of the worst ways to optimize a sort-by-generated-key operation!

Something as...

@keys = map gen_key($_), @data;
@sorted = @data[sort {$keys[$a] <=> $keys[$b]} 0..$#keys];

should perform much better when correctly implemented in a low level language, specially if you are able to use packed arrays to store @keys.

[moritz]

I hope you are not really using the Schwartzian transform in Rakudo as it is one of the worst ways to optimize a sort-by-generated-key operation!

Actually it's an implementation detail about which I don't care really much. Correctness first, performance later. I just called it a Schwartzian Transform because that's the name that most perl programmers use for the sort-by-generated-key operation.

Looking at the source it seems to do something close to what you proposed.