GNU bug report logs - #69709
`sort` interface improvement and universal ordering predicate

Previous Next

Full log

Message #35 received at 69709 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 69709 <at> debbugs.gnu.org,
 Gerd Möllmann <gerd.moellmann <at> gmail.com>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, Dmitry Gutov <dmitry <at> gutov.dev>
Subject: Re: bug#69709: `sort` interface improvement and universal ordering
 predicate
Date: Wed, 20 Mar 2024 20:01:39 +0100

Now the origin/scratch/sort-key branch contains a draft proposal. Summary:

* Our timsort has now the key function handling from the original code (ported to Emacs).
* New keyword-based calling convention for `sort`. The old one is still there and works as before.
* New `value-less-p` universal ordering predicate.
* No manual updates yet.
* NEWS entries are there.
* `sort-on` is now completely superfluous (slower, less convenient) and should be removed.
* Performance seems fine from initial tests. More comprehensive benchmarking will be done.

Some things that I haven't made up my mind about:

* Better name for `value-less-p`:
    value<
    {generic,universal,standard,lisp}{-less-p,<}

* Maybe the :destructive keyword be called :inplace or :in-place instead? Shorter, less violent.

* Should the :reverse keyword be called :reversed or even :descending ?

* Internally, `value-less-p` computes a 3-way result; it would be easy to expose that to Lisp as `value-compare`, could be useful.

* The design space for `value-less-p` is vast: the current code is an attempt at intuitive semantics without too much complexity. There are also good (and bad) arguments for:

- heterogeneous comparisons (compare objects of different types)
- total order on all values
- strict agreement with `equal`
- automatic call-out to user-defined comparison functions for classes that have them

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.