http://www.perlmonks.org?node_id=401366

in reply to Things I have learnt

At the risk of providing an inferior answer amid higher authorities, I'll try to explain the Schwartzian Transform.

First, one has to understand why it is useful. Assume you want to sort a list by, for example, ignoring the first character in each element. In other words, you want to sort 'Babc' before "Abcd". You could write such a sort like this:

my @sorted = sort { substr( \$a, 1 ) cmp substr( \$b, 1 ) } @unsorted;

And that works fine. But remember that the comparison routine of a sort function gets called many times. ...possibly several times per element being sorted. It's somewhat inefficient calling substr twice for each comparison, over and over and over again as the list gets sorted.

There is a better way. What if, instead of calling substr over and over again, multiple times per element being sorted, you called it once per element and stored the results? If you can create, store, and access this cached list fast enough, it will be more efficient than doing complex calculations over and over again on the same element throughout the course of the sort.

The Schwartzian Transform does this. It creates a cache of whatever complex computation you had in mind, and saves it alongside the original data, so that it's easy to keep track of the real data and its cached pre-computed sort criteria at the same time.

The most common form of the Schwartzian Transform takes a flat list, and turns it into a list of references to two-element arrays. Here's how our substr( \$string, 1 ) might work in a ST.

@original | @transform | [0] [1] _________ | _________________________ abc | abc bc asdf | asdf sdf jkas | jkas kas qwert | qwert wert uiop | uiop iop

So in the above example:

@original = qw/abc asdf jkas qwert uiop/;

...and...

@transformed = ( [ 'abc' , 'bc' ], [ 'asdf' , 'sdf' ], [ 'jkas' , 'kas' ], [ 'qwert', 'wert' ], [ 'uiop' , 'iop' ] );

Now lets look at the complete transform, as commonly seen:

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

Look at this from the bottom up: