[racket] Feature request: multiple keys in sort

Yesterday, Harry Spier wrote:
> [...]
> 
> What I meant was something like this:
> (sort '((9 9 9) (8 8 8) (8 9 8) (7 7 7) (7 9 7)) (> #:key first) (>
> #key second))
>> '((9 9 9) (8 9 8) (8 8 8) (7 9 7) (7 7 7))

Ah, so you want to sort with a major/minor comparators?  There's
nothing built in for that, but it's not hard to do.  Here's an
overview of things that you can do.

First, the `sort' function is stable, which means that you can sort
with the minor order first, and then with the minor one:

    (sort (sort '((9 9 9) (8 8 8) (8 9 8) (7 7 7) (7 9 7))
                > #:key second)
          > #:key first)

This is of course more expensive, so if you care about speed, you'll
want to write a specific comparison function:

    (sort '((9 9 9) (8 8 8) (8 9 8) (7 7 7) (7 9 7))
          (λ (x y) (cond [(> (first x) (first y)) #t]
                         [(> (first y) (first x)) #f]
                         [else (> (second x) (second y))])))

It's obviously better to abstract this -- for example, implement a
function that combines comparison functions.  This can be done in a
number of ways -- for example, (apologies for the following name, I
couldn't think of something better, also, it can be much simpler, but
this is an attempt to avoid some overhead):

    (define <...
      (case-lambda
        [(<?)        <?]
        [(<?1 <?2)   (λ (x y) (cond [(<?1 x y) #t]
                                    [(<?1 y x) #f]
                                    [else (<?2 x y)]))]
        [(<? . more) (<... <? (apply <... more))]))
    
    (sort '((9 9 9) (8 8 8) (8 9 8) (7 7 7) (7 9 7))
          (<... (λ (x y) (> (first x) (first y)))
                (λ (x y) (> (second x) (second y)))))

And, in cases like this where each comparison requires a key function,
you can add that into the combiner function (this is a little weird in
making the last key function optional, improve to taste):

    (define <...
      (case-lambda
        [(<?)                <?]
        [(<? key)            (λ (x y) (<? (key x) (key y)))]
        [(<?1 key1 <?2)      (λ (x y) (let ([x (key1 x)] [y (key1 y)])
                                        (cond [(<?1 x y) #t]
                                              [(<?1 y x) #f]
                                              [else (<?2 x y)])))]
        [(<?1 key1 <?2 key2) (λ (x y) (let ([x1 (key1 x)] [y1 (key1 y)])
                                        (cond [(<?1 x1 y1) #t]
                                              [(<?1 y1 x1) #f]
                                              [else (<?2 (key2 x) (key2 y))])))]
        [(<? key . more)     (<... <? key (apply <... more))]))

and this gives you something very close to what you ask for:

    (sort '((9 9 9) (8 8 8) (8 9 8) (7 7 7) (7 9 7))
          (<... > first > second))

And BTW, if you really care about speeding things up by another
smallish factor, you could go with a macro approach -- something that
expands into the manually written piece of code:

    (define-syntax <...
      (syntax-rules ()
        [(_)
         (λ (x y) #f)]
        [(_ <? key more ...)
         (λ (x y)
           (let ([x1 (key x)] [y1 (key y)])
             (cond [(<? x1 y1) #t]
                   [(<? y1 x1) #f]
                   [else ((<... more ...) x y)])))]))

(This *does* expand to a bunch of nested lambdas, which is why it's so
simple.  But these nested functions are all immediately applied, which
means that the compiler will optimize the calls and generate code that
is roughly the same as the manually written code above.)


So the bottom line is that there's no need to extend `sort' for this
kind of functionality.  What would be nice to have though, is such a
comparison combinator -- and the only reason there's nothing that
comes pre-packaged is that I didn't see something that sticks out as
the right api for it.  (See srfi-67 for a very complete discussion,
and a post that I'll send to the dev list soon.)

-- 
          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                    http://barzilay.org/                   Maze is Life!