master 4b79c80c999 1/2: New function 'sort-on'

[Eli Zaretskii]

branch: master
commit 4b79c80c999fe95654b7db196b12e0844473f6da
Author: Eli Zaretskii <eliz@gnu.org>
Commit: Eli Zaretskii <eliz@gnu.org>

    New function 'sort-on'
    
    * lisp/sort.el (sort-on): New function.  Patch by John Wiegley
    <jwiegley@gmail.com>.
    
    * etc/NEWS:
    * doc/lispref/sequences.texi (Sequence Functions): Document
    'sort-on'.
---
 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 5b3d7dec8a6..816613de4ec 100644
--- a/etc/NEWS
+++ b/etc/NEWS
@@ -1530,6 +1530,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)