Hi,<br><br>I read a previous thread about BWT implementation in Haskell:<br>http://www.mail-archive.com/haskell-cafe@haskell.org/msg25609.html<br>and<br>http://sambangu.blogspot.com/2007/01/burrows-wheeler-transform-in-haskell<br><br>They are all in a `brute-force' way, that is implement based on Burrows-Wheeler's definition like below:<br><br>BWT: sort the rotations of input S to get a matrix M', return the last column L, and the row I, where S appears in M'<br><br>-- O( n^2 \lg n)<br>bwt :: (Ord a)=&gt;[a]-&gt;([a], Int)<br>bwt s = (map last m, i) where<br>&nbsp;&nbsp;&nbsp; m = sort [ drop i s ++ take i s | i&lt;-[1..length s]]<br>&nbsp;&nbsp;&nbsp; (Just i) = elemIndex s m<br><br>And the IBWT: Re-construct M' by iteratively sort on input L, add one column at a time, and pick the I-th row in M'<br><br>-- O( n^3 \lg n )<br>ibwt :: (Ord a)=&gt; ([a], Int) -&gt; [a]<br>ibwt (r, i) = m !! i where<br>&nbsp;&nbsp;&nbsp; m = iterate f (replicate n []) !! n<br>&nbsp;&nbsp;&nbsp; f = sort . zipWith (:) r<br>&nbsp;&nbsp;&nbsp; n = length r<br><br>I read Richard Bird's book, `Pearls of functional algorithm design', there is another solution. Although it is deduced step by step,<br>the core idea is based on random access the list by index. The algorithm mentioned in the book uses suffixes for <br>sorting instead of rotations. The performance are same in terms of big-O. I wrote the following program accordingly.<br><br>BWT: sort S along with the index to get a new order of IDs, and return a permutation of S based on IDs.<br><br>-- O( n^2 \lg n) if (!!) takes O(n) time<br>bwt' :: (Ord a)=&gt; [a] -&gt; ([a], Int)<br>bwt' s =&nbsp; (l, i) where<br>&nbsp;&nbsp;&nbsp; l = map (\i-&gt;s !! ((i-1) `mod` n)) ids<br>&nbsp;&nbsp;&nbsp; (Just i) = elemIndex 0 ids<br>&nbsp;&nbsp;&nbsp; ids = map snd $ sortBy (compare `on` fst) $ zip rots [0..]<br>&nbsp;&nbsp;&nbsp; rots = init $ zipWith (++) (tails s) (inits s) -- only non-empties<br>&nbsp;&nbsp;&nbsp; n = length s<br><br>IBWT: Sort the input L along with index to get a Transform vector, T [1], then permute L iteratively on T start from row I. <br><br>-- O( n^2 ) if (!!) takes O(n) time<br>ibwt' :: (Ord a) =&gt; ([a], Int) -&gt; [a]<br>ibwt' (r, i) =&nbsp; fst $ iterate f ([], i) !! n where<br>&nbsp;&nbsp;&nbsp; t = map snd $ sortBy (compare `on` fst) $ zip r [0..]<br>&nbsp;&nbsp;&nbsp; f (s, j) = let j' = t !! j in (s++[r !! j'], j')<br>&nbsp;&nbsp;&nbsp; n = length r<br><br>However, As I commented, the (!!) takes time proportion to the length of the list, Although it can be turned into real Haskell Array<br>by listArray (0, n-1) xs.<br><br>I wonder if there are any purely functional implementations of BWT/IBWT, which don't base on random access idea nor in brute-force way.<br><br>[Reference]<br>[1], Mark Nelson. `Data Compression with the Burrows-Wheeler Transform'. http://marknelson.us/1996/09/01/bwt/<br><br>--<br>Larry, LIU Xinyu<br>https://github.com/liuxinyu95/AlgoXY<br>