Polishing a Functional Pearl: The Burrows-Wheeler Transform

Here is a quick post to get me back into the swing of blogging.

I was looking through an old post on StackOverflow about clever functional code, and the best answer, given by “yairchu” was a nice version of the Burrows-Wheeler Transform, which is an algorithm for permuting a string such that it can be compressed more effectively by other algorithms. The code posted was (import Data.List assumed):

bwp :: (Ord a)=> [a] -> [a]
bwp xs = map snd $ sort $ zip (rots xs) (rrot xs)
rots xs = take (length xs) (iterate lrot xs)
lrot xs = tail xs ++ [head xs]
rrot xs = last xs : init xs

I saw I could improve/shorten this in a couple of obvious ways and came up with this:

bwp :: (Ord a) => [a] -> [a]
bwp = map snd . sort . rots
rots xs = zip (tail $ iterate lrot xs) xs
lrot (x:xs) = xs ++ [x]

Still unsatisfied and even more obsessed I came up with this final, prettiest version, before forcing myself to give it up already:

bwp :: (Ord a)=> [a] -> [a]
bwp = map snd . sort . rots
rots xs = zip (lrot xs) xs
lrot = tail . tails . cycle

Unfortunately, this last version will croak if your string happens to look like “111111” or “cAbcAb” because sort will keep trying to compare infinites lists.

date = “” slug = “/polishing-a-functional-pearl-the-burrows-wheeler-transform” Move To Front transform as a follow-up to this post.