From 7228082a81ca7fbf6069fb6c995c475b3a13e6cd Mon Sep 17 00:00:00 2001 From: Eli Zaretskii Date: Fri, 2 Feb 2024 15:24:55 +0200 Subject: [PATCH] New function 'sort-on' * lisp/sort.el (sort-on): New function. Patch by John Wiegley . * etc/NEWS: * doc/lispref/sequences.texi (Sequence Functions): Document 'sort-on'. (cherry picked from commit 4b79c80c999fe95654b7db196b12e0844473f6da) --- doc/lispref/sequences.texi | 37 +++++++++++++++++++++++++++++++++---- etc/NEWS | 5 +++++ lisp/sort.el | 20 ++++++++++++++++++++ 3 files changed, 58 insertions(+), 4 deletions(-) diff --git a/doc/lispref/sequences.texi b/doc/lispref/sequences.texi index f1f23f007a4..654019dfc31 100644 --- a/doc/lispref/sequences.texi +++ b/doc/lispref/sequences.texi @@ -434,12 +434,41 @@ but their relative order is also preserved: (9 . "aaa") (9 . "zzz") (9 . "ppp") (9 . "fff")] @end group @end example - -@xref{Sorting}, for more functions that perform sorting. -See @code{documentation} in @ref{Accessing Documentation}, for a -useful example of @code{sort}. @end defun +Sometimes, computation of sort keys of list elements is expensive, and +therefore it is important to perform it the minimum number of times. +By contrast, computing the sort keys of elements inside the +@var{predicate} function passed to @code{sort} will generally perform +this computation each time @var{predicate} is called with some +element. If you can separate the computation of the sort key of an +element into a function of its own, you can use the following sorting +function, which guarantees that the key will be computed for each list +element exactly once. + +@defun sort-on sequence predicate accessor +This function stably sorts the list @var{sequence}, comparing the sort +keys of the elements using @var{predicate}. The comparison function +@var{predicate} accepts two arguments, the sort keys to compare, and +should return non-@code{nil} if the element corresponding to the first +key should sort before the element corresponding to the second key. +The function computes a sort key of each element by calling the +@var{accessor} function on that element; it does so exactly once for +each element of @var{sequence}. The @var{accessor} function is called +with a single argument, an element of @var{sequence}. + +This function implements what is known as +@dfn{decorate-sort-undecorate} paradigm, of the Schwartzian transform. +It basically trades CPU for memory, creating a temporary list with the +computed sport keys, then mapping @code{car} over the result of +sorting that temporary list. Unlike with @code{sort}, the return list +is a copy; the original list is left intact. +@end defun + +@xref{Sorting}, for more functions that perform sorting. See +@code{documentation} in @ref{Accessing Documentation}, for a useful +example of @code{sort}. + @cindex sequence functions in seq @cindex seq library @cindex sequences, generalized diff --git a/etc/NEWS b/etc/NEWS index d87b9162b31..284cdf5ab28 100644 --- a/etc/NEWS +++ b/etc/NEWS @@ -1665,6 +1665,11 @@ precedence over the variable when present. Mostly used internally to do a kind of topological sort of inheritance hierarchies. +** New function 'sort-on'. +This function implements the Schwartzian transform, and is appropriate +for sorting lists when the computation of the sort key of a list +element can be expensive. + ** New API for 'derived-mode-p' and control of the graph of major modes. *** 'derived-mode-p' now takes the list of modes as a single argument. diff --git a/lisp/sort.el b/lisp/sort.el index 2ee76b6e1e3..97b40a2aef4 100644 --- a/lisp/sort.el +++ b/lisp/sort.el @@ -478,6 +478,26 @@ sRegexp specifying key within record: \nr") ;; if there was no such register (error (throw 'key nil)))))))))) +;;;###autoload +(defun sort-on (sequence predicate accessor) + "Sort SEQUENCE by calling PREDICATE on sort keys produced by ACCESSOR. +SEQUENCE should be the input list to sort. +Elements of SEQUENCE are sorted by keys which are obtained by +calling ACCESSOR on each element. ACCESSOR should be a function of +one argument, an element of SEQUENCE, and should return the key +value to be compared by PREDICATE for sorting the element. +PREDICATE is the function for comparing keys; it is called with two +arguments, the keys to compare, and should return non-nil if the +first key should sort before the second key. +This function has the performance advantage of evaluating +ACCESSOR only once for each element in the input SEQUENCE, and is +therefore appropriate when computing the key by ACCESSOR is an +expensive operation. This is known as the \"decorate-sort-undecorate\" +paradigm, or the Schwartzian transform." + (mapcar #'car + (sort (mapcar #'(lambda (x) (cons x (funcall accessor x))) sequence) + #'(lambda (x y) (funcall predicate (cdr x) (cdr y)))))) + (defvar sort-columns-subprocess t) -- 2.39.5