sort needs a #:key argument

sort needs a #:key argument

[Andy Wingo]

Hello,

Do you read guile-devel and are looking for a manageable thing to hack?
Well how about this. `sort!' needs a #:key argument.

I believe you will find more precise specifications in the Common Lisp
specifications, but the basic idea is that the comparison function of
`sort' operates not on elements of the list, but on the result of
applying a function to those elements.

Like this:

  (sort '(1 -2 3 -4) <)
     => (-4 -2 1 3)
  (sort '(1 -2 3 -4) < #:key (lambda (x) (* x x)))
     => (1 -2 3 -4)
  (sort '((a . 1) (b . -2) (c . 3)) < cdr)
     => ((b . -2) (a . 1) (c . 3))

I would do it by exposing scm_sort to Scheme as primitive-sort, and
defining a `sort' in scheme using (ice-9 optargs) and primitive-sort,
customizing the less? procedure if a #:key is given.

Then we'd need to update the documentation, and add a news entry. Any
takers? :)

Andy
-- 
http://wingolog.org/

Re: sort needs a #:key argument

[Ludovic Courtès]

Hello,

Andy Wingo <wingo@pobox.com> 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”.

Thanks,
Ludo’.

Re: sort needs a #:key argument

[Andy Wingo]

Hi,

On Tue 20 Oct 2009 10:38, ludo@gnu.org (Ludovic Courtès) writes:

> Andy Wingo <wingo@pobox.com> 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 :)

Plus.. it's for occupational safety. Less typing for the win! :)

Andy
-- 
http://wingolog.org/

Re: sort needs a #:key argument

[Ludovic Courtès]

Hello,

Andy Wingo <wingo@pobox.com> writes:

> On Tue 20 Oct 2009 10:38, ludo@gnu.org (Ludovic Courtès) writes:
>
>> Andy Wingo <wingo@pobox.com> 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’.

Re: sort needs a #:key argument

[Andy Wingo]

Hello,

On Wed 21 Oct 2009 18:06, ludo@gnu.org (Ludovic Courtès) writes:

> Andy Wingo <wingo@pobox.com> 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
Schemes.

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

It's a compatible extension.

Andy
-- 
http://wingolog.org/