The Sort Problem

[Luke Palmer]

I've been thinking about this problem which comes up in my code a lot:

@sorted = sort { $^a.foo('bar').compute <=> $^b.foo('bar').compute }
@unsorted;

Often the expressions on each side are even longer than that. But one
thing remains: both sides are exactly the same, substitute a $^b for a
$^a.

I can see a couple less-than-desirable ways around this redundancy:

@sorted = sort { infix:<=>( *($^a, $^b)».foo('bar').compute ) }
@unsorted;

Which doesn't work if .compute returns a list... not to mention its
horrible ugliness. Another is to define a variant of sort (haven't had
much practice with A6 material recently; here we go!):

multi sub sort (&block($) = { $_ } : *@data) {
sort { block($^a) cmp block($^b) } @data;
}

@sorted = sort { .foo('bar').compute } @unsorted;

Which has the disadvantage of forcing you to use C<cmp> and forcing an
ascending sort.

Any other ideas? Is a more general solution necessary?

Luke

[Gregor N. Purdy]

Luke --

Hmmm... I haven't been practicing my Perl 6, and its been a while
since the last Apocalyptic refresher, but here goes (I'll don a paper
bag preemptively)...

Thinking of that as the equivalent to:

sort {
my ($ta, $tb) = map { $_.foo('bar').compute } ($^a, $^b);
$ta <=> $tb
} @unsorted;

so if you had a unary <=> that took a two element array (old style
syntax here, sorry):

sub cmp_num { my ($a, $b) = @_; $a <=> $b; }

you could write that as:

sort {
cmp_num map { $_.foo('bar').compute } ($^a, $^b);
} @unsorted;

I'd be a bit afraid of allowing <=> itself to be prefix, although I
admit it would be handy not to need the separate sub definition:

sort {
<=> map { $_.foo('bar').compute } ($^a, $^b);
} @unsorted;

The Schwartzian is the usual way, of course:

map { $_->[1] }
sort { $^a[0] <=> $^b[0] }
map { [ $_.foo('bar').compute, $_ ] }
@unsorted;

But we really aren't being concise here.

(Aside) I wonder if there will be a new Perl 6 idiom to replace this
using properties, something like this:

map { $_.really }
sort : numerically
map { $_.foo('bar').compute but really($_) }
@unsorted;

or:

@unsorted
==> map { $_.foo('bar').compute but really($_) }
==> sort : numerically
==> map { $_.really };

But we *still* aren't concise.

Maybe we should have a two-block sort? The second block gives the
transform to apply to the elements before applying the comparison
block:

sort { $^a <=> $^b } { $_.foo('bar').compute } @unsorted;

Or maybe even something like this:

sort :numerically :as { $^a.foo('bar').compute } @unsorted;

Regards,

-- Gregor

--
Gregor Purdy gre...@focusresearch.com
Focus Research, Inc. http://www.focusresearch.com/

[Joe Gottman]

This is unrelated to the problem you mentioned, but there is another
annoying problem with sort as it is currently defined. If you have an
@array and you want to replace it with the sorted version, you have to type
@array = sort @array;

Besides being long-winded, this causes Perl to make an unnecessary copy of
the array. It would be nice calling if sort (or reverse, or other similar
functions) in void context resulted in in-place modification of the array
that was input.

Joe Gottman

[Uri Guttman]

>>>>> "GNP" == Gregor N Purdy <gre...@focusresearch.com> writes:

GNP> The Schwartzian is the usual way, of course:

GNP> map { $_->[1] }
GNP> sort { $^a[0] <=> $^b[0] }
GNP> map { [ $_.foo('bar').compute, $_ ] }
GNP> @unsorted;

and the GRT is another.

let stick my nose in here. sorting is really composed of 3 parts,
extracting keys, comparing them and then getting back the records in
sorted order. the p5 sort block idioms require duplicating the extract
code and usually a binary operator. the GRT eliminates the binary
operator as it uses the default string compare in sort but it still
requires key extraction and then record extraction (similar to the first
map (last executed) in the ST.

GNP> But we really aren't being concise here.

GNP> (Aside) I wonder if there will be a new Perl 6 idiom to replace this
GNP> using properties, something like this:

GNP> map { $_.really }
GNP> sort : numerically
GNP> map { $_.foo('bar').compute but really($_) }
GNP> @unsorted;

GNP> or:

GNP> @unsorted
GNP> ==> map { $_.foo('bar').compute but really($_) }
GNP> ==> sort : numerically
GNP> ==> map { $_.really };

GNP> But we *still* aren't concise.

that is the problem. the merging of the extracted key (in the ST or GRT)
with the record and the extraction of the record need to be hidden as
that is common code.

GNP> Maybe we should have a two-block sort? The second block gives the
GNP> transform to apply to the elements before applying the comparison
GNP> block:

GNP> sort { $^a <=> $^b } { $_.foo('bar').compute } @unsorted;

duplicate args again.

GNP> Or maybe even something like this:

GNP> sort :numerically :as { $^a.foo('bar').compute } @unsorted;

that looks best but how do you replace the :numerically comparison with
say a unicode aware string compare?

i have been working on a Sort::GRT in my head (finally!) and have some
ideas.

first, key extraction should work on $_ which is set for each element of
the unsorted list so there is no need for $^a. also how can you extract
multiple keys? and each key needs a ascending/descending option. and
each key needs a type so it can be compared correctly.

so here is a (very rough and probably broken) syntax idea building on
that:

sort :key { :descend :string .foo('bar').substr( 10, 3) }
:key { :int .foo('baz') }
:key { :float .foo('amount') } @unsorted ;

sort takes a list of :key's which each has a block (or whatever) that
specifies the key type, ordering and extraction code (that works on the
record in $_). the extraction code is in a block in itself so you can
declare lexicals and use multiple statements. the last value (in list
context) is the key. this is so you can do (p5 style) /foo(\d+)bar/ and
extract that digit string as the key.

side note: i was pondering the problem of where two different keys have
to be extracted from nearby places deep in a nested record
structure. this means duplicate code will be used to get into the deep
part. in my module, i was planning to allow a 'pre-extraction' piece of
code to be used and the value (e.g. a ref to the deep part) stored in a
lexical which can be used later in both key extractions. i don't know
any way to do that with the above syntax. there has to be a larger block
around all the :key's to allow something like that here. the p5 module
will be wrapping all the key extract code in a block so this would work
there.

internally, each record has its keys extracted and they are merged using
the GRT or ST or similar. in either case the record must be attached
(via a pointer or appended or some other way) to the merged key. the
keys are sorted and then the attached records are grabbed back and
returned. sorting in place can be done too.

what is good about the above syntax is that it removes all the common
code, removes the binary operator (order and type is all that matters)
and allows for a simple way to express multiple key extractions.

it can be implemented internally in c to be far faster than any perl or
parrot level code could do. the biggest hurdle i see is proper support
for unicode stuff. maybe another key attribute would be the collating
name? how this affects internal sorting is a question. can you generate
a merged key with numbers, ascii and unicode strings that will sort with
simple string compares? maybe the unicode extraction has to do a char by
char conversions to (32 bit?) integers using the collate sequence and
those numbers can easily be merged and sorted. note that only the
extracted key text needs to be converted so that shouldn't be too
expensive. so it may look like this:

sort :key { :descend :string :collate('iso_some_country')
.foo('bar').substr( 10, 3) }
:key { :int .foo('baz') } @unsorted ;

what is nice about that is that each key could have its own collate
type. the :string attribute could be optional since the :collate implies
a string.

just trying to sort things out,

uri

--
Uri Guttman ------ u...@stemsystems.com -------- http://www.stemsystems.com
--Perl Consulting, Stem Development, Systems Architecture, Design and Coding-
Search or Offer Perl Jobs ---------------------------- http://jobs.perl.org

[Gregor N. Purdy]

Uri --

(But, the GRT doesn't apply to sorting general objects, and the example
has @unsorted containing objects on which we run .foo('bar').compute.)

I like the idea of having multiple modifier clauses attached to the
'sort' word instead of having to do my own or-ing.

I like the idea of having a way of expressing ascending / descending
other then swapping $a and $b in the expression (too easy to overlook).

I'm not sure about the hypothetical syntax (at least not the stuff
inside the curlies).

All the proposals involving consise representation could involve a
behind-the-scenes mapping of the sort-containing statement to some sort
of ST / GRT implementation. Making sure that simple scalar sorting
didn't get slowed down by suchlike would be important.

Maybe it would require a hint that the sort key should be considered
expensive to compute for a ST / GRT / or Orcish Maneuver transformation
to be applied to help things along...

Regards,

-- Gregor

[Uri Guttman]

>>>>> "GNP" == Gregor N Purdy <gre...@focusresearch.com> writes:

GNP> (But, the GRT doesn't apply to sorting general objects, and the
GNP> example has @unsorted containing objects on which we run
GNP> .foo('bar').compute.)

there are no restrictions on what the GRT (or ST) can sort. the key is
key extraction and that can be from an object or anything. if the
compute method has to be called each time during the comparison, you are
in deep sort voodoo. so you can just call it during the extract phase
(the first executed map in the GRT or ST). if you have the object in $_,
you can call a method or do whatever you need to get the key.

GNP> I like the idea of having multiple modifier clauses attached to the
GNP> 'sort' word instead of having to do my own or-ing.

GNP> I like the idea of having a way of expressing ascending /
GNP> descending other then swapping $a and $b in the expression (too
GNP> easy to overlook).

GNP> I'm not sure about the hypothetical syntax (at least not the stuff
GNP> inside the curlies).

well, i said the syntax was bogus. let larry and damian solve that
problem. i just wanted to highlight the real requirements for a high
level multikey sort. i also like not having to see $a or ^$a and also
the reverse of the compare order is bad as well, hence the :descending
flag.

GNP> All the proposals involving consise representation could involve
GNP> a behind-the-scenes mapping of the sort-containing statement to
GNP> some sort of ST / GRT implementation. Making sure that simple
GNP> scalar sorting didn't get slowed down by suchlike would be
GNP> important.

no problem. if there is no key extraction code, it defaults to $_ and no
map is done. you can still specify the order like this:

@sorted = sort :key { :descending } @unsorted ;

@sorted = sort :key { :int :descending } @unsorted ;

those should be very fast (default key type is asciibetical).

idea: in void context, sort will sort in place:

sort :key { :int :descending } @unsorted_and_then_sorted ;

in list context it sorts and returns a list. in scalar context it
returns a ref to the sorted list, saving an extra copy.

$sorted_array_ref = sort :key { :int :descending } @unsorted ;

GNP> Maybe it would require a hint that the sort key should be
GNP> considered expensive to compute for a ST / GRT / or Orcish
GNP> Maneuver transformation to be applied to help things along...

no key extraction code, no need for the ST/GRT. order is all you need
there. maybe type or collate could be passed in but i am not sure how
this will affect the internal design and speed. if my unicode to integer
map is needed to make that work well, it will require a map layer. but
adding unicode to anything will complexify and slowify things. :)

and the orcish maneuver is not on the speed level of the GRT or ST.

<please don't quote my entire email. edit the quote and insert your
comments below>

thanx,

[Luke Palmer]

Uri Guttman writes:
> >>>>> "GNP" == Gregor N Purdy <gre...@focusresearch.com> writes:
>
> GNP> (But, the GRT doesn't apply to sorting general objects, and the
> GNP> example has @unsorted containing objects on which we run
> GNP> .foo('bar').compute.)
>
> there are no restrictions on what the GRT (or ST) can sort. the key is
> key extraction and that can be from an object or anything. if the
> compute method has to be called each time during the comparison, you are
> in deep sort voodoo. so you can just call it during the extract phase
> (the first executed map in the GRT or ST). if you have the object in $_,
> you can call a method or do whatever you need to get the key.

Might you explain what the GRT is and what it is intended to do? I've
been lost throughout most of your proposal.

Thanks,
Luke

[Uri Guttman]

>>>>> "LP" == Luke Palmer <fibo...@babylonia.flatirons.org> writes:

LP> Uri Guttman writes:
>> >>>>> "GNP" == Gregor N Purdy <gre...@focusresearch.com> writes:
>>
GNP> (But, the GRT doesn't apply to sorting general objects, and the
GNP> example has @unsorted containing objects on which we run
GNP> .foo('bar').compute.)
>>
>> there are no restrictions on what the GRT (or ST) can sort. the key is
>> key extraction and that can be from an object or anything. if the
>> compute method has to be called each time during the comparison, you are
>> in deep sort voodoo. so you can just call it during the extract phase
>> (the first executed map in the GRT or ST). if you have the object in $_,
>> you can call a method or do whatever you need to get the key.

LP> Might you explain what the GRT is and what it is intended to do?
LP> I've been lost throughout most of your proposal.

and now you know how i feel about some threads you delve into! my brane
hertz! :)

sorry about the confusion. read the paper at:

http://www.sysarch.com/perl/sort_paper.html

the idea is simple and very old. you extract keys from the records and
merge them (with some munging) into a byte string. then you can run a
straight sort with comparisons on those merged key strings and use fast
string compares. the win is not doing the key extraction on each set of
comparisons which is O(N log N). instead you do the extractions once per
key which is O(N). it is a real world optimization as pure O() theory
wouldn't care as the dominating O(N log N) is still the same in both
cases. :)

all we (larry rosler and myself) did was translate the idea into perl
and document how to do it. one of these days i will actually create a
perl5 module (started one years ago but it got shelved) to implement
this and make it easy to use. i recently came up with a design
breakthrough (just not being as stupid as i was a few years ago) to make
it easier to do so i may get back onto it.

but much of my p6 proposal was to have the sort function reflect the
essence of both the GRT and ST which is to factor out key extraction in
a map before the sort. my syntax examples were meant to show what is
needed to pass into a full sort system and what isn't needed. perl5's
sort exposed everything and required redundant code in the comparison
block, confusing expressions, etc. the ST and GRT removed some of the
redundant code but replaced that with the map/sort/map which has
different redundant code (redundant between different instances of
them. why see the map parts?).

so my proposed syntax isolates the key extraction code and makes it work
on $_. it also removes the comparison operator stuff and allows the
coder to just say what they want in regard to sort order, key type and
collate sequence. the guts will do all the common code (the maps) and
generate/compile the proper key extraction code. in fact, there is no
need for the GRT or ST to even be implemented at all. the key extraction
code and order could be used to generate comparison stuff just like
perl5 does. the ST and GRT are just implementation optimizations and
don't belong in a language level discussion.

hope that helps,

[Rafael Garcia-Suarez]

Joe Gottman wrote in perl.perl6.language :

> This is unrelated to the problem you mentioned, but there is another
> annoying problem with sort as it is currently defined. If you have an
> @array and you want to replace it with the sorted version, you have to type
> @array = sort @array;
>
> Besides being long-winded, this causes Perl to make an unnecessary copy of
> the array. It would be nice calling if sort (or reverse, or other similar
> functions) in void context resulted in in-place modification of the array
> that was input.

I'd rather not change the behaviour of sort (or other built-ins that
may or may not operate in place) depending on the calling context.
What to do, for example, when C<sort> is the last statement of a sub?

Besides this, a construction like @x = sort @x could be detected by
a suitable optimizer and turned to (internally) an in-place sort.
(It appears that Dave Mitchell is working on such an optimization for
perl 5.)

[Deborah Pickett]

On Thu, 12 Feb 2004 15.40, Joe Gottman wrote:
> This is unrelated to the problem you mentioned, but there is another
> annoying problem with sort as it is currently defined. If you have an
> @array and you want to replace it with the sorted version, you have to type
> @array = sort @array;
>
> Besides being long-winded, this causes Perl to make an unnecessary copy of
> the array. It would be nice calling if sort (or reverse, or other similar
> functions) in void context resulted in in-place modification of the array
> that was input.

I just know that this has come up before . . . I don't remember whether it was
consensus[1] or just my wishful thinking that this would make code like:

sub foo
{
my $listref = shift;
# other stuff...
# return sorted list.
sort @$listref;
}

morally ambiguous[2], because that "sort" is being called in whatever context
the function call was in, which could be miles away.

I'd suggest that an in-place sort have a marginally different name, but the
rubyometer is already redlined as it is.

(Even more OT: I dislike the scoping rules for named sorting subroutines in
Perl 5. It means you can't do questionable things like this:

# A common function used all over the place.
sub onewayorother { $direction * ($a <=> $b) }
# much later ...
my $direction = -1;
my @arr = sort onewayorother (5,7,9);

The more I look at that, the more I think it's a stupid example, but I have a
vivid memory of being upset about it several years ago, when I wasn't a very
good programmer. This is looking less like a whinge and more like a
confession. Move along, nothing more to see here.)

[1] If, by "consensus", you mean "Larry Said No."
[2] Not semantically ambiguous, because it isn't.

--
Debbie Pickett
http://www.csse.monash.edu.au/~debbiep
deb...@csse.monash.edu.au

[Aaron Crane]

Luke Palmer wrote:
> Any other ideas?

How about something like this, modulo any errors in my Perl 6 syntax?

sub sort(?&cmp = &infix:cmp, +$key, +$desc, *@data) { ... }

I think that allows all of these:

# P5: @sorted = sort @unsorted;
@sorted = sort @unsorted;

The simplest case is the same as the Perl 5, which seems a pleasant feature.

# P5: @sorted = sort { $a <=> $b } @unsorted;
@sorted = sort { $^a <=> $^b } @unsorted; # or:
@sorted = sort &infix:<=> <== @unsorted;

This also seems reasonable.

# P5: @sorted = sort { $a->foo('bar')->compute <=> $b->foo('bar')->compute }
# @unsorted
# or: @sorted = map { $_->[1] }
# sort { $a->[0] <=? $b->[0] }
# map { [ $_->foo('bar')->compute, $_ ] }
# @unsorted
@sorted = sort &infix:<=>, key => { $_.foo('bar').compute } <== @unsorted;

I think my suggestion wins big here. We've only had to specify how to
extract the key, and sort itself takes care of everything else. And it looks
to me like this sort function has enough information about the programmer's
intent for it to optimise in all sorts of exciting ways -- it should be able
to do the equivalent of the GRT internally, for example.

Just for kicks, this one demonstrates all the features. It's the same as
before, but in descending order:

@unsorted
==> sort &infix:<=>, desc => 1, key => { $_.foo('bar').compute }
==> @sorted;

What problems can anyone spot with this suggestion?

--
Aaron Crane * GBdirect Ltd.
http://training.gbdirect.co.uk/courses/perl/

[Ph. Marek]

> ...

> so here is a (very rough and probably broken) syntax idea building on
> that:
>
> sort :key { :descend :string .foo('bar').substr( 10, 3) }
>
> :key { :int .foo('baz') }
> :key { :float .foo('amount') } @unsorted ;

I see a kind of problem here: If the parts of the key are not fixed length but
can vary you can put them in strings *only* after processing all and
verifying the needed length.

Example:

sort :key { :descend :string .foo('bar') }

:key { :int .foo('baz') }
:key { :float .foo('amount') } @unsorted ;

Now .foo('bar') isn't bounded with any length - so you don't know how much
space to reserve.

And I believe that
- generating keys on every list element
- storing them into a array (array of array) and
- after having processed all checking the length, and
- now generate the to-be-sorted-strings
- sort

isn't the optimal way.
BTW: this requires that *all* keys are generated.
In cases like
- by name,
- by age,
- by height,
- by number of toes left,
- and finally sort by the social security number

most of the extractions (and possibly database-queries of calculations or
whatever) will not be done - at least in the current form of
sort { $a->{"name"} cmp $b->{"name"} ||
$a->{"age"} <=> $b->{"age"} ||
...

That is to say, I very much like the syntax you propose, but I'm not sure if
pre-generating *every* key-part is necessarily a speed-up.

If there are expensive calculations you can always cut them short be
pre-calculating them into a hash by object, and just query this in sort.

Also I fear that the amount of memory necessary to sort an array of length N
is not N*2 (unsorted, sorted), but more like N*3 (unsorted, keys, sorted),
which could cause troubles on bigger arrays ....

Regards,

Phil

[Aaron Sherman]

On Thu, 2004-02-12 at 01:59, Uri Guttman wrote:

> sorry about the confusion. read the paper at:
>
> http://www.sysarch.com/perl/sort_paper.html

All of which stops being a concern if you have a sort variant that works
on pairs in the first place. Perl _5_ code follows:

sub sortpairs(&@) {
my $comp = shift;
my %pairs = @_;
return map {$pairs{$_}} sort {$comp->($a)} keys %pairs;
}

@new1 = sortpairs {$a <=> $b} map {($_->computekey,$_)} @old1;
@new2 = sortpairs {$a cmp $b} map {(lc($_),uc($_))} @old2;

as you can see, you can perform any key extraction you like in the map
portion (which just returns key/value pairs) and sortpairs' job is just
to compare the keys and return the resulting sorted values.

No Perl 6 here, move along ;-)

Perl 6 could contribute here by making it cheaper to construct/pass the
keys, but that's about it.

--
Aaron Sherman <a...@ajs.com>
Senior Systems Engineer and Toolsmith
"It's the sound of a satellite saying, 'get me down!'" -Shriekback

[Aaron Sherman]

On Thu, 2004-02-12 at 08:43, Aaron Sherman wrote:

> sub sortpairs(&@) {
> my $comp = shift;
> my %pairs = @_;
> return map {$pairs{$_}} sort {$comp->($a)} keys %pairs;
> }

Doh... it's early for me. That's C<sort {$comp->()}> with no parameter.
The fact that $a and $b are dynamically scoped in Perl 5 helps out here.

[Dan Sugalski]

At 11:40 PM -0500 2/11/04, Joe Gottman wrote:
> This is unrelated to the problem you mentioned, but there is another
>annoying problem with sort as it is currently defined. If you have an
>@array and you want to replace it with the sorted version, you have to type
> @array = sort @array;

That would seem to be a place for more explicit, and specific,
behaviour. Since we're going "everything is an object" then it's just
a matter of:

@array.sort_in_place;

and making sure that the array role provides the appropriate method.
--
Dan

--------------------------------------"it's like this"-------------------
Dan Sugalski even samurai
d...@sidhe.org have teddy bears and even
teddy bears get drunk

[Larry Wall]

On Thu, Feb 12, 2004 at 12:07:37PM +0100, Ph. Marek wrote:
: > ...

: > so here is a (very rough and probably broken) syntax idea building on
: > that:
: >
: > sort :key { :descend :string .foo('bar').substr( 10, 3) }
: >
: > :key { :int .foo('baz') }
: > :key { :float .foo('amount') } @unsorted ;
: I see a kind of problem here: If the parts of the key are not fixed length but
: can vary you can put them in strings *only* after processing all and
: verifying the needed length.

I think this is easily solved by sorting on a list of strings rather than a
single string.

: - generating keys on every list element

: - storing them into a array (array of array) and
: - after having processed all checking the length, and
: - now generate the to-be-sorted-strings
: - sort
:
: isn't the optimal way.
: BTW: this requires that *all* keys are generated.
: In cases like
: - by name,
: - by age,
: - by height,
: - by number of toes left,
: - and finally sort by the social security number

Not if you lazily add strings to the list of strings mentioned above.

: That is to say, I very much like the syntax you propose, but I'm not sure if

: pre-generating *every* key-part is necessarily a speed-up.
:
: If there are expensive calculations you can always cut them short be
: pre-calculating them into a hash by object, and just query this in sort.

Another approach is to declare a function that "is cached", I suppose.

: Also I fear that the amount of memory necessary to sort an array of length N

: is not N*2 (unsorted, sorted), but more like N*3 (unsorted, keys, sorted),
: which could cause troubles on bigger arrays ....

We'll just use virtual memory. :-)

Larry

[Luke Palmer]

Aaron Crane writes:
> Luke Palmer wrote:
> > Any other ideas?
>
> How about something like this, modulo any errors in my Perl 6 syntax?
>
> sub sort(?&cmp = &infix:cmp, +$key, +$desc, *@data) { ... }
>
> I think that allows all of these:
>
> # P5: @sorted = sort @unsorted;
> @sorted = sort @unsorted;
>
> The simplest case is the same as the Perl 5, which seems a pleasant feature.

This is a feature that, IMO, we can not do without. I still do things
like:

print "$_: %hash{$_}" for sort keys %hash;

All the time, and I don't want to give that up for some "clearer"
syntax, as there is no such thing.

>
> # P5: @sorted = sort { $a <=> $b } @unsorted;
> @sorted = sort { $^a <=> $^b } @unsorted; # or:
> @sorted = sort &infix:<=> <== @unsorted;
>
> This also seems reasonable.
>
> # P5: @sorted = sort { $a->foo('bar')->compute <=> $b->foo('bar')->compute }
> # @unsorted
> # or: @sorted = map { $_->[1] }
> # sort { $a->[0] <=? $b->[0] }
> # map { [ $_->foo('bar')->compute, $_ ] }
> # @unsorted
> @sorted = sort &infix:<=>, key => { $_.foo('bar').compute } <== @unsorted;

Ok, I have to say, that's pretty good. Er, really good. I like it a
lot.

> I think my suggestion wins big here. We've only had to specify how to
> extract the key, and sort itself takes care of everything else. And it looks
> to me like this sort function has enough information about the programmer's
> intent for it to optimise in all sorts of exciting ways -- it should be able
> to do the equivalent of the GRT internally, for example.
>
> Just for kicks, this one demonstrates all the features. It's the same as
> before, but in descending order:
>
> @unsorted
> ==> sort &infix:<=>, desc => 1, key => { $_.foo('bar').compute }
> ==> @sorted;
>
> What problems can anyone spot with this suggestion?

I don't like the C<desc> flag. But I can't, at the moment, think of any
way around it short of:

@unsorted
==> sort { $^b <=> $^a }, key => { .foo('bar').compute }
==> @sorted

Which people have made pretty clear that they don't like.

Oh, by the way, your Perl 6 syntax is immaculate. Bravo :-)

Luke

[Uri Guttman]

>>>>> "LP" == Luke Palmer <fibo...@babylonia.flatirons.org> writes:

>> # P5: @sorted = sort { $a->foo('bar')->compute <=> $b->foo('bar')->compute }
>> # @unsorted
>> # or: @sorted = map { $_->[1] }
>> # sort { $a->[0] <=? $b->[0] }
>> # map { [ $_->foo('bar')->compute, $_ ] }
>> # @unsorted
>> @sorted = sort &infix:<=>, key => { $_.foo('bar').compute } <== @unsorted;

LP> Ok, I have to say, that's pretty good. Er, really good. I like it a
LP> lot.

how do you select descending order? and how do you selecte that per key?
you can't provide a binary operator without also providing the
order. and what about different key types? the <=> and cmp operators are
not enough information needed to do complex sorts. collating sequences
are another issue. you need to have that info on a perl key basis.

>> I think my suggestion wins big here. We've only had to specify how
>> to extract the key, and sort itself takes care of everything else.
>> And it looks to me like this sort function has enough information
>> about the programmer's intent for it to optimise in all sorts of
>> exciting ways -- it should be able to do the equivalent of the GRT
>> internally, for example.

sort can't figure it out without you telling it things. you need more
than just key extraction.

>> Just for kicks, this one demonstrates all the features. It's the same as
>> before, but in descending order:
>>
>> @unsorted
>> ==> sort &infix:<=>, desc => 1, key => { $_.foo('bar').compute }
>> ==> @sorted;
>>
>> What problems can anyone spot with this suggestion?

multiple keys with each having different comparisons and different sort
orders.

LP> @unsorted
LP> ==> sort { $^b <=> $^a }, key => { .foo('bar').compute }
LP> ==> @sorted

LP> Which people have made pretty clear that they don't like.

as i have said before. needing to have $a and $b in the correct order is
bug prone and confusing to many.

[Uri Guttman]

>>>>> "PM" == Ph Marek <philip...@bmlv.gv.at> writes:

>> ...
>> so here is a (very rough and probably broken) syntax idea building on
>> that:
>>
>> sort :key { :descend :string .foo('bar').substr( 10, 3) }
>>
>> :key { :int .foo('baz') }
>> :key { :float .foo('amount') } @unsorted ;

PM> I see a kind of problem here: If the parts of the key are not
PM> fixed length but can vary you can put them in strings *only* after
PM> processing all and verifying the needed length.

varying keys has no effect on this. you still build up a merged key of
whatever length is needed for each record. perl5 does that with pack or
.= or sprintf (all used in variants of the GRT).

PM> Example:
PM> sort :key { :descend :string .foo('bar') }
PM> :key { :int .foo('baz') }
PM> :key { :float .foo('amount') } @unsorted ;

PM> Now .foo('bar') isn't bounded with any length - so you don't know how much
PM> space to reserve.

who needs to reserve space? you just let the guts do a realloc like p5
does now.

PM> And I believe that
PM> - generating keys on every list element
PM> - storing them into a array (array of array) and
PM> - after having processed all checking the length, and
PM> - now generate the to-be-sorted-strings
PM> - sort

PM> isn't the optimal way.
PM> BTW: this requires that *all* keys are generated.
PM> In cases like
PM> - by name,
PM> - by age,
PM> - by height,
PM> - by number of toes left,
PM> - and finally sort by the social security number

PM> most of the extractions (and possibly database-queries of calculations or
PM> whatever) will not be done - at least in the current form of
PM> sort { $a->{"name"} cmp $b->{"name"} ||
PM> $a->{"age"} <=> $b->{"age"} ||
PM> ...

PM> That is to say, I very much like the syntax you propose, but I'm
PM> not sure if pre-generating *every* key-part is necessarily a
PM> speed-up.

see the paper for more on that. the work you do in the callback, even if
you only do the first compare is O(N log N). in large sorts that will
outweigh the O(N) work on extracting the keys one time.

and as with all algorithms, real world cases will differ. short sorts
can be faster with complex comparisons because of the initial
overhead. maybe the internal code can decide to do that instead of a GRT
based on the sort array size. the key extract code is the same in both
cases so that would be an interesting optimization.

PM> If there are expensive calculations you can always cut them short
PM> be pre-calculating them into a hash by object, and just query this
PM> in sort.

again, the goal is to eliminate work in the comparison. but as i said,
this is an implementation problem. we should focus on the language level
needs of the sort func and not how it is done internally. i shouldn't
have brought up the internal design here.

PM> Also I fear that the amount of memory necessary to sort an array
PM> of length N is not N*2 (unsorted, sorted), but more like N*3
PM> (unsorted, keys, sorted), which could cause troubles on bigger
PM> arrays ....

as larry said, virtual memory. and there are ways to reduce the copies
internally with pointers (something p5 couldn't do at p5 code level).

other than copying the extracted keys, you could leave the original
array alone and sort it in place by indexing it based on the sorted
pointers. and since the records will all be the same PMC type (usually),
you could just swap the array's pointers and not move any data
around. so no extra copies would be made other than key extraction.

[Aaron Crane]

Luke Palmer wrote:

> Aaron Crane writes:
> > @unsorted
> > ==> sort &infix:<=>, desc => 1, key => { $_.foo('bar').compute }
> > ==> @sorted;
>

> I don't like the C<desc> flag. But I can't, at the moment, think of any
> way around it short of:
>
> @unsorted
> ==> sort { $^b <=> $^a }, key => { .foo('bar').compute }
> ==> @sorted
>
> Which people have made pretty clear that they don't like.

One option might be an 'rsort' function, but I think that's somewhat lacking
in the taste department.

Another might be as simple as

@unsorted ==> sort ==> reverse ==> @sorted;

But I can see an argument that C<< ==> reverse >> is quite a large code
burden for something so conceptually simple.

I have one other idea, but I can't decide if I like it:

@unsorted ==> sort &rinfix:cmp ==> @sorted;

That is, rinfix: (or some other name) is like infix:, but gives you a
function that reverses its arguments before actually running the operator.
Perhaps it could even be implemented as a macro.

[Uri Guttman]

>>>>> "AC" == Aaron Crane <aar...@gbdirect.co.uk> writes:

AC> One option might be an 'rsort' function, but I think that's
AC> somewhat lacking in the taste department.

AC> Another might be as simple as

AC> @unsorted ==> sort ==> reverse ==> @sorted;

again, reverse order needs to be on a per key basis. the problem we are
wrangling is how to support multiple keys in a clean syntactical way.

AC> @unsorted ==> sort &rinfix:cmp ==> @sorted;

AC> That is, rinfix: (or some other name) is like infix:, but gives you a
AC> function that reverses its arguments before actually running the operator.
AC> Perhaps it could even be implemented as a macro.

again, confusing. why should the order of a binary operator mean so
much? the order of a sort key is either ascending or descending. that is
what coders want to specify. translating that to the correct operator
(cmp or <=>) and the correct binary order is not the same as specifying
the key sort order and key type (int, string, float).

[Luke Palmer]

Aaron Crane writes:
> I have one other idea, but I can't decide if I like it:
>
> @unsorted ==> sort &rinfix:cmp ==> @sorted;
>
> That is, rinfix: (or some other name) is like infix:, but gives you a
> function that reverses its arguments before actually running the operator.
> Perhaps it could even be implemented as a macro.

Like this one?

macro rinfix($op)
is parsed(/ \: (.*?) <before: <[\s(]> > /)
{
return {
-> $a, $b {
&("infix:$op").($b, $a)
}
}
}

Luke

[Simon Cozens]

aar...@gbdirect.co.uk (Aaron Crane) writes:
> One option might be an 'rsort' function, but I think that's somewhat lacking
> in the taste department.

Agreed.

> Another might be as simple as
>
> @unsorted ==> sort ==> reverse ==> @sorted;

@sorted <== sort <== @unsorted, no? ;)

> @unsorted ==> sort &rinfix:cmp ==> @sorted;
>
> That is, rinfix: (or some other name) is like infix:, but gives you a
> function that reverses its arguments before actually running the operator.
> Perhaps it could even be implemented as a macro.

I like this; it reminds me of the games you have to play with determining
what do to with binary operators whose operands are overloaded in different
classes.

--
Do not go gentle into that good night/Rage, rage against the dying of the light

[Dave Whipp]

Perhaps something like:

@sorted = sort { infix:<=> map { scalar $_.foo('bar').compute } @^_ } }
@data

I'm not entirely sure it's readability is better than yours, though.

Dave.

"Luke Palmer" <fibo...@babylonia.flatirons.org> wrote in message
news:20040212031...@babylonia.flatirons.org...

[Simon Cozens]

da...@whipp.name (Dave Whipp) writes:
> @sorted = sort { infix:<=> map { scalar $_.foo('bar').compute } @^_ } }
> @data

Abusing the rubyometer slightly:
@data = @sorted.sort( op => &infix:<=>, key => { $^a.foo('bar').compute } );

--
If the code and the comments disagree, then both are probably wrong.
-- Norm Schryer

[Aaron Sherman]

On Thu, 2004-02-12 at 15:46, Uri Guttman wrote:
> >>>>> "LP" == Luke Palmer <fibo...@babylonia.flatirons.org> writes:

> LP> Ok, I have to say, that's pretty good. Er, really good. I like it a
> LP> lot.
>
> how do you select descending order? and how do you selecte that per key?
> you can't provide a binary operator without also providing the
> order. and what about different key types? the <=> and cmp operators are
> not enough information needed to do complex sorts. collating sequences
> are another issue. you need to have that info on a perl key basis.

You know, I have trouble typing "per" when I'm thinking "perl" too ;-)

I think my example addressed all of your concerns, and did it in Perl 5.
Once again, that was:

sub sortpairs(&@) {
my $comp = shift;
my %pairs = @_;

return map {$pairs{$_}} sort {$comp->()} keys %pairs;

}

@new1 = sortpairs {$a <=> $b} map {($_->computekey,$_)} @old1;
@new2 = sortpairs {$a cmp $b} map {(lc($_),uc($_))} @old2;

So, in order, your questions were:

* how do you select descending order?
You reverse the $a and $b in the first parameter to sortpairs
* and how do you selecte that per key?
Ok, I was only addressing one key. But, it's not hard to
generalize the idea, and certainly Perl 6 gives you the tools to
do so easily.
* you can't provide a binary operator without also providing the
order.
Correct
* and what about different key types? the <=> and cmp operators

are not enough information needed to do complex sorts.

That's fine, you can plug in a call to Alien::Headed::Babies
inside the closure for all I care.
* collating sequences are another issue. you need to have that

info on a perl key basis.

Give me an example?
* multiple keys with each having different comparisons and
different sort orders.

Ok let's delve into it then:

sub sortpairs(&@){
my $comp = shift;

my @elements = @_;
return map {my $e=$elements[$_];$e->[$#{$e}]} sort {
my @akeys = @{$elements[$a]}[0..$#{$elements[$a]}-1];
my @bkeys = @{$elements[$b]}[0..$#{$elements[$b]}-1];
for(my $i=0;$i<@akeys;$i++) {
my $dir = $comp->($akey[$i],$bkey[$i]);
return $dir if $dir;
}
return 0;
} 1..scalar(@elements);
}

@new1 = sortpairs {$_[0] <=> $_[1]} map {[$_,$_]} @old1;
@new2 = sortpairs {$_[0] <=> $_[1] || $_[4] cmp $_[3]} map {[getkeys($_),$_]} @old2;

The second example really illustrates the point that you can swap the
direction of key order and mechanism to compare them at your whim.

Now, you just need to call sortpairs with any array of arrays of keys
(with trailing value).

[Uri Guttman]

>>>>> "AS" == Aaron Sherman <a...@ajs.com> writes:

AS> On Thu, 2004-02-12 at 15:46, Uri Guttman wrote:
>>

>> how do you select descending order? and how do you selecte that per
>> key?

>> you can't provide a binary operator without also providing the
>> order. and what about different key types? the <=> and cmp
>> operators are not enough information needed to do complex
>> sorts. collating sequences are another issue. you need to have that
>> info on a perl key basis.

AS> I think my example addressed all of your concerns, and did it in Perl 5.
AS> Once again, that was:

AS> sub sortpairs(&@) {
AS> my $comp = shift;
AS> my %pairs = @_;
AS> return map {$pairs{$_}} sort {$comp->()} keys %pairs;
AS> }

AS> @new1 = sortpairs {$a <=> $b} map {($_->computekey,$_)} @old1;
AS> @new2 = sortpairs {$a cmp $b} map {(lc($_),uc($_))} @old2;

AS> So, in order, your questions were:

AS> * how do you select descending order?
AS> You reverse the $a and $b in the first parameter to sortpairs

i find that a poor solution. the $a cmp $b isn't needed in the ascending
case at all. a descending marker per key is better as it reflects the
results desired and not how it gets done. the reversing of $a and $b
requires the coder to understand sort comparison callbacks. it is
implementation exposed.

AS> * and how do you selecte that per key?
AS> Ok, I was only addressing one key. But, it's not hard to
AS> generalize the idea, and certainly Perl 6 gives you the tools to
AS> do so easily.

i haven't seen any proposals other than mine (which is bad syntax but
good semantics) for this. and if you have multiple keys with each having
a $a <=> $b in there it will be very noisy.

AS> * you can't provide a binary operator without also providing the
AS> order.
AS> Correct

a single descending marker is simpler and better semantics.

AS> * and what about different key types? the <=> and cmp operators
AS> are not enough information needed to do complex sorts.
AS> That's fine, you can plug in a call to Alien::Headed::Babies
AS> inside the closure for all I care.

there are only a short list of key comparisons possible, int, string,
float and maybe unicode. i separate int from float since they do have
different internals in the GRT. it is one area where you do expose
stuff. otherwise you could just use number.

AS> * collating sequences are another issue. you need to have that
AS> info on a perl key basis.
AS> Give me an example?

simple. pick almost any language char set other than US ascii. many have
special collating sequences. i am not anything close to a unicode expert
but i have seen this issue. in fact setting the LANG (or some other)
environment variable will affect many programs by changing the collating
order.

AS> * multiple keys with each having different comparisons and
AS> different sort orders.

AS> Ok let's delve into it then:

AS> sub sortpairs(&@){
AS> my $comp = shift;
AS> my @elements = @_;
AS> return map {my $e=$elements[$_];$e->[$#{$e}]} sort {
AS> my @akeys = @{$elements[$a]}[0..$#{$elements[$a]}-1];

why the -1? that looks like:

my @akeys = @{$elements[$a]} ;
pop @akeys ;
pop @akeys ;

AS> my @bkeys = @{$elements[$b]}[0..$#{$elements[$b]}-1];
AS> for(my $i=0;$i<@akeys;$i++) {
AS> my $dir = $comp->($akey[$i],$bkey[$i]);
AS> return $dir if $dir;
AS> }
AS> return 0;
AS> } 1..scalar(@elements);
AS> }

that is scary. do you realize that the sort block will be called for
each comparison?

AS> @new1 = sortpairs {$_[0] <=> $_[1]} map {[$_,$_]} @old1;

AS> @new2 = sortpairs {$_[0] <=> $_[1] || $_[4] cmp $_[3]} map
AS> {[getkeys($_),$_]} @old2;

where is getkeys defined? how do you know what indexes to use for each
comparison? what happened to $_[2]? your call to $comp is passed 2
arguments but the second example accesses 4 arguments.

AS> The second example really illustrates the point that you can swap the
AS> direction of key order and mechanism to compare them at your whim.

AS> Now, you just need to call sortpairs with any array of arrays of keys
AS> (with trailing value).

add a third key to that. quickly!

a more straightforward api (which is close to what i will do in
Sort::GRT) is (p5 code)

my $sort = Sort::GRT->new(

keys => [
{ descending => 1,
type => float,
extract => '$_->{amount},
},
{ extract => 'substr( $_->{date}, 0, 4)' },
]
) ;

my @sorted = $sort->do_it( @unsorted ) ;

$sort->do_it_inplace( \@unsorted ) ;

add a third key:

my $sort = Sort::GRT->new(

keys => [
{ descending => 1,
type => float,
extract => '$_->{amount}',
},
{ extract => 'substr( $_->{date}, 0, 4)' },
{ extract => '$_->{user}{last_name}' },
]
) ;

see? no issues with || or <=> or order or $_[4]. each key must have its
own type, order and extract code. the logical way to do that is a list
of hashes which is easy to describe and create a syntax for in p6. all
the other proposals i have seen here bypass this need for multikey
support.

[Larry Wall]

On Thu, Feb 12, 2004 at 09:37:37PM +0000, Simon Cozens wrote:
: aar...@gbdirect.co.uk (Aaron Crane) writes:
: > That is, rinfix: (or some other name) is like infix:, but gives you a

: > function that reverses its arguments before actually running the operator.
: > Perhaps it could even be implemented as a macro.
:
: I like this; it reminds me of the games you have to play with determining
: what do to with binary operators whose operands are overloaded in different
: classes.

Which we're trying very hard to get away from in Perl 6...which reminds me,
I have to put something about that into A12...

Larry

[Larry Wall]

On Thu, Feb 12, 2004 at 04:29:58PM -0500, Uri Guttman wrote:
: again, confusing. why should the order of a binary operator mean so

: much? the order of a sort key is either ascending or descending. that is
: what coders want to specify. translating that to the correct operator
: (cmp or <=>) and the correct binary order is not the same as specifying
: the key sort order and key type (int, string, float).

Uri is dead on with this one, guys.

Larry

[Ph. Marek]

As I listen to this mails, I get the feeling that something like this is
wanted:

Key generation:
@unsorted_temp = map {
$k1=$_.func1('a'); # ASC
$k2=$_.func2('we'); # DESC
[ $_, $k1, $k2 ];
} @unsorted;
Now we've got an array with keys and the objects.
Sorting:
@sorted = sort {
$a->[1] cmp $b->[1] ||
$b->[2] <=> $a->[2] ||
} @unsorted_temp;

These things would have to be said in P6.
So approx.:
@sorted = @unsorted.sort(
keys => [ { $_.func1('a'); },
{ $_.func2('we'); } ],
cmp => [ cmp, <=> ],
order => [ "asc", "desc"],
key_generation => "lazy",
);

That would explain what I want.
Maybe we could turn the parts around:

@sorted = @unsorted.sort(
1 => [ { $_.func1('a'); }, cmp, "asc"],
2 => [ { $_.func2('we'); }, <=>, "desc"],
);

or maybe use a hash instead of an array:

@sorted = @unsorted.sort(
1 => [ key => { $_.func1('a'); }, op => cmp, order => "asc"],
2 => [ key => { $_.func2('we'); }, op => <=>, order => "desc"],
);

If that's too verbose? I don't think so; I've stumbled often enough on $a <=>
$b vs. $b <=> $a and similar, and the above just tells what should be done.

Regards,

Phil

[Aaron Sherman]

On Thu, 2004-02-12 at 18:50, Uri Guttman wrote:

> there are only a short list of key comparisons possible, int, string,
> float and maybe unicode. i separate int from float since they do have
> different internals in the GRT. it is one area where you do expose
> stuff. otherwise you could just use number.

And comparing in a particular language (as Dan pointed out in his Parrot
talk); comparing sets (e.g. numeric comparison, but odds and evens are
separate); ordering by string length; ordering by string-to-numeric
value with esoteric exceptions (software versions); etc.

Comparison is essentially always numeric, but only if you reduce your
inputs to numbers, and that's often not terribly efficent (e.g. you can
reduce any ascii string to:

chr(substr($s,0,1))+chr(substr($s,1,1))*128+...

and then comparing. The only limitation is that you'll have to use
Math::BigInt to do the comparison.

> simple. pick almost any language char set other than US ascii. many have
> special collating sequences. i am not anything close to a unicode expert
> but i have seen this issue. in fact setting the LANG (or some other)
> environment variable will affect many programs by changing the collating
> order.

Ok, yes. This was Dan's example, and is EXACTLY why I think you want to
use map once for key extraction and then sort's expression for
comparison.

> that is scary. do you realize that the sort block will be called for
> each comparison?

Yes.... why would it not be? How do you compare, say, IPv6 addresses if
not by performing a logically-ored comparison between each octet? I
certainly don't want to instantiate a Math::BigInt just to compare two
128-bit values.

> AS> @new1 = sortpairs {$_[0] <=> $_[1]} map {[$_,$_]} @old1;
>
> AS> @new2 = sortpairs {$_[0] <=> $_[1] || $_[4] cmp $_[3]} map
> AS> {[getkeys($_),$_]} @old2;
>
> where is getkeys defined?

It was an example. It's whatever you like. In some cases, that might
just be:

sub getkeys {
my $object = shift;
return @{$object->keys};
}

or perhaps:

sub getkeys {
my $string = shift;
return(length($string),$string); # Order by length and then ascii order
}

It was just an example. sortpairs was the interesting part.

> how do you know what indexes to use for each
> comparison? what happened to $_[2]? your call to $comp is passed 2
> arguments but the second example accesses 4 arguments.

You missed a layer of extraction there. $comp is passed each parameter
PAIR.

So if your input is [1,2,3,4,"moo"], then you are comparing the keys 1,
2, 3 and 4 and your value is "moo".

> AS> The second example really illustrates the point that you can swap the
> AS> direction of key order and mechanism to compare them at your whim.
>
> AS> Now, you just need to call sortpairs with any array of arrays of keys
> AS> (with trailing value).
>
> add a third key to that. quickly!

ok, easy:

@new2 = sortpairs {$_[0] <=> $_[1] || $_[4] cmp $_[3] || ACME::Compare::Thingulas->compare($_[5],$_[6])} map {[getkeys($_),$_]} @old2;

Please notice that the ONLY change is in the way I call it, not in
sortpairs. sortpairs still works just fine.

> a more straightforward api (which is close to what i will do in
> Sort::GRT) is (p5 code)
>
> my $sort = Sort::GRT->new(
>
> keys => [
> { descending => 1,
> type => float,
> extract => '$_->{amount},
> },
> { extract => 'substr( $_->{date}, 0, 4)' },
> ]
> ) ;

The value of extract should be a subref, not a string (thus having
closure status, and therefore access to context).

I think you and I are in violent agreement. I just look at this as a
problem that doesn't need solving because Schwartzian Transforms do all
the work for me. You look at it as something needing encapsulation.
That's cool, but sematically, we're doing the same work.