Schwartzian transform in Haskell

In the last post, I mentioned that we might be able to improve the performance of our sort using a "http://en.wikipedia.org/wiki/Schwartzian_transform".

This basically involves precaching the expensive calculation (in this case, length), sorting by the cached value, then taking just the original values.

Let's test with a list of words:

words "If on a winter's night a traveller"

So instead of the original sortBy (flip $ comparing length), we'd have something like:

  map fst 
 . sortBy (flip $ comparing snd)  
 . map (id &&& length)

Let's read it from the bottom. First of all we create a list of tuples using the rather wonderful &&& operator from Control.Arrow.

[("If",2),("on",2),("a",1),("winter's",8),("night",5),("a",1),("traveller",9)]

Then we sort comparing the new second field of this tuple.

[("traveller",9),("winter's",8),("night",5),("If",2),("on",2),("a",1),("a",1)]

Finally we map again, getting just the first element of the tuple.

["traveller","winter's","night","If","on","a","a"]

And we can easily abstract this with a new function

sortST cmp f = map fst
             . sortBy (cmp snd)
             . map (id &&& f)

Now we can write:

sortST       comparing  length listOfWords
sortST (flip.comparing) length listOfWords

This is very similar to the sortBy syntax, except that we've separated out the "comparing" from the "length" clause, in order to compose the two separately for the new transformation.