Re: sort needs a #:key argument

[Ludovic Courtès]

Hello,

Andy Wingo <address@hidden> writes:

> On Tue 20 Oct 2009 10:38, address@hidden (Ludovic Courtès) writes:
>
>> Andy Wingo <address@hidden> writes:
>>
>>>   (sort '((a . 1) (b . -2) (c . 3)) < cdr)
>>>      => ((b . -2) (a . 1) (c . 3))
>>
>> FWIW I find:
>>
>>   (sort '((a . 1) (b . -2) (c . 3))
>>         (lambda (x y)
>>           (< (cdr x) (cdr y))))
>>
>> more in the spirit of not “piling feature on top of feature”.
>
> (sort l < #:key cdr) is a bit contrived. But if your key takes time to
> compute, you need to use the decorate-sort-undecorate idiom, otherwise
> you compute the sort key O(n log n) times instead of O(n) times. It's
> part of our old Lisp tradition :)

If you insist:

  (sort '((a . 1) (b . -2) (c . 3))
        (memoized-lambda
          (lambda (x y)
            (< (cdr x) (cdr y)))))

(With ‘memoized-lambda’ trivially implemented using a weak hash table,
etc.)

:-)

Also, it would be a departure from R5RS (and R6RS’ ‘list-sort’, FWIW).

Thanks,
Ludo’.