[Haskell-cafe] Need for speed: the Burrows-Wheeler Transform

[Andrew Coppin]

Stefan O'Rear wrote:
> Mr. C++ apparently isn't a very good C++ programmer, since his best
> effort absolutely *pales* in comparison to Julian Seward's BWT:
>
> stefan at stefans:/usr/local/src/hpaste$ head -c 135000 /usr/share/dict/words | (time bzip2 -vvv) > /dev/null
>   (stdin): 
>     block 1: crc = 0x25a18961, combined CRC = 0x25a18961, size = 135000
>       0 work, 135000 block, ratio  0.00
>       135000 in block, 107256 after MTF & 1-2 coding, 61+2 syms in use
>       initial group 6, [0 .. 0], has 20930 syms (19.5%)
>       initial group 5, [1 .. 1], has 4949 syms ( 4.6%)
>       initial group 4, [2 .. 2], has 20579 syms (19.2%)
>       initial group 3, [3 .. 4], has 17301 syms (16.1%)
>       initial group 2, [5 .. 10], has 24247 syms (22.6%)
>       initial group 1, [11 .. 62], has 19250 syms (17.9%)
>       pass 1: size is 127140, grp uses are 339 550 192 440 12 613 
>       pass 2: size is 51693, grp uses are 321 440 288 316 139 642 
>       pass 3: size is 51358, grp uses are 329 387 376 304 122 628 
>       pass 4: size is 51302, grp uses are 298 421 397 304 125 601 
>       bytes: mapping 21, selectors 433, code lengths 110, codes 51297
>     final combined CRC = 0x25a18961
>     2.602:1,  3.075 bits/byte, 61.57% saved, 135000 in, 51887 out.
>
> real	0m0.165s
> user	0m0.044s
> sys	0m0.012s
>
>
> Yup, does slightly more work (huffman coding) in 1/200 the time :)
>
> (Note, on my system .Lazy BWT3 takes 5.3s on the same input)
>   

...OK...so how do I make Haskell go faster still?

Presumably by transforming the code into an ugly mess that nobody can 
read any more...?