Re: The Sort Problem

[Rod Adams]

Damian Conway wrote:

Uri persisted:
> but int is needed otherwise? int is more commonly a sort key than 
float.
> it just feels asymetrical with one having a symbol and the other a 
named
> operator.

Sorry, but that's the way the language works. The more general and usual
conversion (to number, not to integer) has the shorter name.


For the record, I do a lot of statistical work. On the sorts where I 
care about speed, I'm using floats far more often than ints. Uri's usage 
obviously varies from mine. Let's not hack up the language to make sort 
more efficient for some arguable benefit.

I would entertain, however, C<float> and C<string> comparators (and 
functions in core) that pretty much (if not precisely) alias C<+> and 
C<~>, forcing said type.


>   DC> If you don't explicitly cast either way, C<sort> just DWIMs by
>   DC> looking at the actual type of the keys returned by the extractor.
>   DC> If any of them isn't a number, it defaults to C<cmp>.
>
> that doesn't work for me. the GRT can't scan all keys before it decides
> on what comparison operator is needed. the GRT needs to merge keys as
> they are extracted and it needs to do the correct conversion to a byte
> string then and not later. you can't DWIM this away if you want the
> optimization.
EXACTLY!!! So, if you want the GRT to kick in, you have to make sure the
return type of your block is appropriate. If you don't give the 
compiler that
hint, you don't get the optimized sorting.


When fed a number that it doesn't trust to be an int or a float, 
couldn't the GRT store the number with C<pack 'Nd', $_, $_>? (ok, 
there's some prepping for sign and endian, but you get the point) Seems 
like a not-terrible way to handle the issue.



Here's another example (all praise be to Rod!):

    @teams = sort [
                  # 1 parameter so it's a key extractor...
                  {+ $^team->{WinPct} },
                  # 2 parameters so it's a comparator...
                  { ($^a->{Conference} eq $^b->{Conference}
                        ? ($^b->{ConfWinPct} <=> $^a->{ConfWinPct} ||
                           $^b->{ConfWon}    <=> $^a->{ConfWon}    ||
                           $^a->{ConfLost}   <=> $^b->{ConfLost})
                    : ($^a->{Division} eq $^b->{Division}
                        ? ($^b->{DivWinPct} <=> $^a->{DivWinPct} ||
                           $^b->{DivWon}    <=> $^a->{DivWon}    ||
                           $^a->{DivLost}   <=> $^b->{DivLost})
                    : 0
                    )
                  },
                  # 1 parameter each so all three are key extractors...
                  {+ $^team->{Won}  } is descending,
                  {+ $^team->{Lost} },
                  {+ $^team->{GamesPlayed} } is descending,
              ] @teams;
Now that's just spiffy. Except in moving from my P5 version to your P6 
version, you have to s/?/??/ and s/:/::/, IIRC.

>   DC> But you *can't* apply C<is descending> to a Code reference.
> then how did you apply 'is insensitive'?
I applied it to the *block* (i.e. a closure definition).
That's not the same thing as a Code reference.
> what i am saying is i think that you need to go back to the drawing
> board to find a clean syntax to mark those flags.
No, I think we have it...just put the appropriate trait on the extractor
*block* when you define it.


I really don't see the problem with

@out = sort {lc $_}, @in;

It's short, simple, unambiguous, IMO very clean. But if people want to 
take a tool that we're creating anyways elsewhere in the language 
(traits) to provide another way to do it, that's fine too.

> i just don't like the reverse args concept at all. it is not
> semantically useful to sorting. sorts care about ascending and
> descending, not a vs b in args.
The problem is that sometimes comparator logic is suffiently complex that
a single comparator needs to have a "bit each way", as in Rod's
football team comparator above.


What my football example was meant to show is that no matter how much we 
abuse poor C<sort> in the name of progress, we need to have a way to 
drop it all and go back to how we did it in P5, for those truly 
pathological cases where nothing else works. If people don't trust this, 
I'll come up with something worse.

As a side note, the reason I couldn't find the original sort in question 
is that I later scraped it in favor of a more robust 100 line sub to 
figure out who ranked where.

But in more common case, how much it break things to have

  type Comparator   ::= Code(Any, Any) returns Int;

become

  type Comparator   ::= Code(Any, Any) returns Int
                                    | '!' Code(Any, Any) returns Int;
where the '!' sets the reverse/descending trait?

So we could get things like:

@out = sort {!~ $_} @in;
@out = sort {!+ -M} @in;
@out = sort {! &complex} @in;
Overall, Damian's proposal looks very good.
Yeah Damian!
-- Rod Adams

PS -- Only pure and utter insanity would lead someone to not make string 
the default sort comparator, and I don't think I've heard anyone here 
mention they are in favor of doing anything else.