[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: sort needs a #:key argument

From: Andy Wingo
Subject: Re: sort needs a #:key argument
Date: Wed, 21 Oct 2009 20:10:28 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/23.0.92 (gnu/linux)


On Wed 21 Oct 2009 18:06, address@hidden (Ludovic Courtès) writes:

> Andy Wingo <address@hidden> writes:
>> 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.
> If you insist:
>   (sort '((a . 1) (b . -2) (c . 3))
>         (memoized-lambda
>           (lambda (x y)
>             (< (cdr x) (cdr y)))))

This simply does not have the same characteristics. You have to memoize
the keys, not the comparisons. And a hash table does not have quite the
same characteristics.

> :-)

Sure, yes -- but it is somewhat distressing that we want different

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

It's a compatible extension.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]