decorate-sort-undecorate


Most Perl programmers would be familiar with the Schwartzian transform which derives from the lisp decorate-sort-undecorate idiom. If you’re not familiar with it then reading the wikipedia article should be a sufficient introduction. Essentially it avoids recalculating the comparisons for each call to sort.

In 1994, Randal Schwartz replied to a question in comp.unix.shell asking how to sort on the last name for a list like this:

adjn:Joshua Ng
adktk:KaLap Timothy Kwong
admg:Mahalingam Gobieramanan
admln:Martha L. Nangalama
admrp:Michael R. Pearson
adshl:Siu Lung Henry Lee
adsyh:So Yi Ho
adtkk:Tariq K. Khan
adtkl:Terence K. H. Leung
advld:Vickie L. Dwyer
alaen:Alfred E. Neuman
anedp:Erin D. Picard

The answer:

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

Map, sort, map.

Anyway, here’s a version in JavaScript 1.6. If we have the following array:

var myArray =  ["adjn:Joshua Ng",
"adktk:KaLap Timothy Kwong",
"admg:Mahalingam Gobieramanan",
"admln:Martha L. Nangalama",
"admrp:Michael R. Pearson",
"adshl:Siu Lung Henry Lee",
"adsyh:So Yi Ho",
"adtkk:Tariq K. Khan",
"adtkl:Terence K. H. Leung",
"advld:Vickie L. Dwyer",
"alaen:Alfred E. Neuman",
"anedp:Erin D. Picard"];

We can sort on the last name like so:

var sorted = myArray.map( function (e) {
    return {o: e, s: e.split(/[\s]/gi).pop()};
}).sort( function (a, b) {
    if(a.s > b.s) {
      return 1;
    } else {
      return -1;  
    }
}).map( function (e) {
    return e.o;
});

Note that the value used to sort is calculated in the map().

I’d be interested in further examination into how well this works in current JavaScript implementations (and any map provided for older implementations); and whether there are more appropriate ways to code it up in JavaScript.

† Map isn’t in until 1.6.



CoffeeScript in Action


CoffeeScript in Action book cover

I'm the author. Get it from Manning.