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

Previous Next

Full log

View this message in rfc822 format

From: Dmitry Gutov <dmitry <at> gutov.dev>
To: Mattias Engdegård <mattias.engdegard <at> gmail.com>, 69709 <at> debbugs.gnu.org
Subject: bug#69709: `sort` interface improvement and universal ordering predicate
Date: Sun, 10 Mar 2024 17:48:34 +0200

On 10/03/2024 15:28, Mattias Engdegård wrote:
> 2. Mutability by default is a bug magnet as well.
> 
> To deal with the first problem, we could:
> 
> * Add a universal ordering predicate that will compare two values of the
>   same type for many built-in types: numbers, strings, symbols, markers,
> lists, vectors, records, and a few more.
> * Make this ordering the default.
> * Add a key (accessor) function argument, like that in the recent
> `sort-on` interface, but built-in. This is important.
> 
> These work very well together: the user does not need to write or even
> choose an ordering predicate in most cases. Key functions are much less
> error-prone to write, and with the lexicographic ordering of lists,
> vectors and records, multi-key sorting is made much easier.
> 
> A key function combined with a standard ordering can also be used to
> optimise comparisons since we have all key values up front along with
> how they should be compared. The original timsort code that we stole
> from Python did this.
> 
> As a starting point, a patch implementing a universal ordering predicate
>   is attached below.
> 
> The proposed sorting function interface would be
> 
>    (new-sort seq &key key lessp destructive)

Here's a concern: a lot of existing code is written with either 
mutability in mind (the source list is a throwaway one, owned by the 
caller), or coupled with copy-sequence already.

If the new 'sort' default to non-destructive, wouldn't that make those 
existing callsites slower? Or at least some of them.

Previous Next

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