Haskell/Burrows–Wheeler transform

Do you understand a compression algorithm like zip? Either way, I recommend you to look into the we:Burrows–Wheeler transform at wikipedia. Coding the BWT in Haskell is quite easy.

-- Burrows-Wheeler.
 
import List (sort,elemIndex)
import Maybe (fromJust)
 
transform :: (Ord x) => [x] -> ([x],Int)
transform x = let n = length x
                  line i = take n $ drop i $ x++x
                  matrix = sort [line i | i<-[0..(n-1)]]
              in
                 (map last matrix,fromJust $ elemIndex x matrix)
 
reTransform :: (Ord x) => ([x],Int) -> [x]
reTransform (x,n) = let tp = zip x [0..]
                        len = length x
                        sx = sort tp
                        p :: [Int] -- permutation, index i is moved to p !! i
                        p = map snd sx
                        --f z = map ( z !! ) p
                        f = flip map p . (!!) -- another point-free exercise solved.
                    in
                        map (x !!) [ l !! n | l<-take len $ iterate f p]
                        --map (x !!) [ l !! n | l<-iterate f p] -- wrong!

The transformation is quite self-explanatory if you understand BWT. These four lines are neither efficient in terms of memory nor speed.

The back-transformation is a little bit harder, but the without p :: [Int]] line and the two comments it is just 6 lines. When I take the time to explain the BWT in my words, the code becomes clear.