Schwartzian transform

The general form of the Schwartzian transform is:

@sorted = map  { $_->[0] }
          sort { $a->[1] cmp $b->[1] or $a->[0] cmp $b->[0] }
          map  { [$_, foo($_)] }
               @unsorted;

Here foo($_) represents an expression that takes $_ (each item of the list in turn) and produces the corresponding value that is to be compared in its stead.

Reading from right to left (or from the bottom to the top):

• the original list @unsorted is fed into a map operation that wraps each item into a (reference to an anonymous 2-element) array consisting of itself and the calculated value that will determine its sort order (list of item becomes a list of [item, value]);
• then the list of lists produced by map is fed into sort, which sorts it according to the values previously calculated (list of [item, value] ⇒ sorted list of [item, value]);
• finally, another map operation unwraps the values (from the anonymous array) used for the sorting, producing the items of the original list in the sorted order (sorted list of [item, value] ⇒ sorted list of item).

The use of anonymous arrays ensures that memory will be reclaimed by the Perl garbage collector immediately after the sorting is done.

Without the Schwartzian transform, the sorting in the example above would be written in Perl like this:

@sorted = sort { foo($a) cmp foo($b) } @unsorted;

While it is shorter to code, the naive approach here could be much less efficient if the key function (called foo in the example above) is expensive to compute. This is because the code inside the brackets is evaluated each time two elements need to be compared. An optimal comparison sort performs O(n log n) comparisons (where n is the length of the list), with 2 calls to foo every comparison, resulting in O(n log n) calls to foo. In comparison, using the Schwartzian transform, we only make 1 call to foo per element, at the beginning map stage, for a total of n calls to foo.

However, if the function foo is relatively simple, then the extra overhead of the Schwartzian transform may be unwarranted.

For example, to sort a list of files by their modification times, a naive approach might be as follows:

 function naiveCompare(file a, file b) {
     return modificationTime(a) < modificationTime(b)
 }
 
 // Assume that sort(list, comparisonPredicate) sorts the given list using
 // the comparisonPredicate to compare two elements.
 sortedArray := sort(filesArray, naiveCompare)

Unless the modification times are memoized for each file, this method requires re-computing them every time a file is compared in the sort. Using the Schwartzian transform, the modification time is calculated only once per file.

A Schwartzian transform involves the functional idiom described above, which does not use temporary arrays.

The same algorithm can be written procedurally to better illustrate how it works, but this requires using temporary arrays, and is not a Schwartzian transform. The following example pseudo-code implements the algorithm in this way:

 for each file in filesArray
     insert array(file, modificationTime(file)) at end of transformedArray
 
 function simpleCompare(array a, array b) {
     return a[2] < b[2]
 }
 
 transformedArray := sort(transformedArray, simpleCompare)
 
 for each file in transformedArray
     insert file[1] at end of sortedArray

The first known online appearance of the Schwartzian transform is a December 16, 1994 posting by Randal Schwartz to a thread in comp.unix.shell Usenet newsgroup, crossposted to comp.lang.perl. (The current version of the Perl Timeline is incorrect and refers to a later date in 1995.) The thread began with a question about how to sort a list of lines by their "last" word:

adjn:Joshua Ng
adktk:KaLap Timothy Kwong
admg:Mahalingam Gobieramanan
admln:Martha L. Nangalama

Schwartz responded with:

#!/usr/bin/perl
require 5; # New features, new bugs!
print
    map { $_->[0] }
    sort { $a->[1] cmp $b->[1] }
    map { [$_, /(\S+)$/] }
    <>;

This code produces the result:

admg:Mahalingam Gobieramanan
adktk:KaLap Timothy Kwong
admln:Martha L. Nangalama
adjn:Joshua Ng

Schwartz noted in the post that he was "Speak[ing] with a lisp in Perl", a reference to the idiom's Lisp origins.

The term "Schwartzian transform" itself was coined by Tom Christiansen in a follow-up reply. Later posts by Christiansen made it clear that he had not intended to name the construct, but merely to refer to it from the original post: his attempt to finally name it "The Black Transform" did not take hold ("Black" here being a pun on "schwar[t]z", which means black in German).

Some other languages provide a convenient interface to the same optimization as the Schwartzian transform:

• In Python 2.4 and above, both the sorted() function and the in-place list.sort() method take a key= parameter that allows the user to provide a "key function" (like foo in the examples above). In Python 3 and above, use of the key function is the only way to specify a custom sort order (the previously supported cmp= parameter that allowed the user to provide a "comparison function" was removed). Before Python 2.4, developers would use the lisp-originated decorate–sort–undecorate (DSU) idiom,[2] usually by wrapping the objects in a (sortkey, object) tuple.
• In Ruby 1.8.6 and above, the Enumerable abstract class (which includes Arrays) contains a sort_by[3] method, which allows specifying the "key function" (like foo in the examples above) as a code block.
• In D 2 and above, the schwartz Sort function is available. It might require less temporary data and be faster than the Perl idiom or the decorate–sort–undecorate idiom present in Python and Lisp. This is because sorting is done in-place, and only minimal extra data (one array of transformed elements) is created.
• Racket's core sort function accepts a #:key keyword argument with a function that extracts a key, and an additional #:cache-keys? requests that the resulting values are cached during sorting. For example, a convenient way to shuffle a list is (sort l < #:key (λ (_) (random)) #:cache-keys? #t).
• In PHP 5.3 and above the transform can be implemented by use of array_walk, e.g. to work around the limitations of the unstable sort algorithms in PHP.

  function spaceballs_sort(array& $a): void
  {
      array_walk($a, function(&$v, $k) { $v = array($v, $k); });
      asort($a);
      array_walk($a, function(&$v, $_) { $v = $v[0]; });
  }
  

• In Elixir, the Enum.sort_by/2 and Enum.sort_by/3 methods allow users to perform a Schwartzian transform for any module that implements the Enumerable protocol.
• In Raku, one needs to supply a comparator lambda that only takes 1 argument to perform a Schwartzian transform under the hood:

  @a.sort( { $^a.Str } ) # or shorter: @a.sort(*.Str)
  

  would sort on the string representation using a Schwartzian transform,

  @a.sort( { $^a.Str cmp $^b.Str } )
  

  would do the same converting the elements to compare just before each comparison.
• In Rust, somewhat confusingly, the slice::sort_by_key method does *not* perform a Schwartzian transform as it will not allocate additional storage for the key, it will call the key function for each value for each comparison. The slice::sort_by_cached_key method will compute the keys once per element.

The Wikibook Algorithm Implementation/Sorting has a page on the topic of: Schwartzian transform

• Sorting with the Schwartzian Transform by Randal L. Schwartz
• Mark-Jason Dominus explains the Schwartzian Transform
• http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52234
• Python Software Foundation (2005). 1.5.2 I want to do a complicated sort: can you do a Schwartzian Transform in Python?. Retrieved June 22, 2005.
• Memoize Perl module - making expensive functions faster by caching their results.