Subject: `sort` interface improvement and universal ordering predicate

From: Mattias Engdegård <[email-masked]>
Date: Sun, 10 Mar 2024 14:28:02 +0100

The existing `sort` interface suffers from some usability problems:

1. Writing an ordering predicate is often difficult and error-prone, even for very basic tasks such as selecting the field to sort on. It's not uncommon to botch a predicate as simple as

  (lambda (a b) (< (f a) (f b)))

which I've managed to do myself more than once. It gets particularly messy when sorting on multiple fields.
Having to write a custom comparison function for almost every occasion also means that performance suffers.

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)

because the keyword interface is easier to read and write than a lengthening list of optional positional parameters, and can be extended more gracefully. For example, it could be handy to have a `reversed` (or `descending`) parameter. The parsing cost is not significant.

Instead of inventing a new and rather meaningless function name, I suggest we re-use `sort` and allow both

  (sort seq lessp)                       ; old-style
  (sort seq &key key lessp destructive)  ; new-style

since they are easy to distinguish, and let `destructive` default to false in new-style calls, true in the old style.