# The move-to-front (MTF) Transform

To follow up my last post about the Burrows-Wheeler Transform, I decided to implement another simple algorithm which is often used after the BWT to help consolidate localized redundancy in the data before entropy encoding.

The idea behind the Move-to-Front algorithm is that we start with some known
alphabet (like the list of ASCII characters), and encode our data elements as
the *index into that alphabet list* of each element. The trick is that after
each character is encoded, the alphabet list is modified by **moving** the
element whose index we just looked up **to the front** of the alphabet.

Here are my implementations of encode and decode:

```
import Data.List
mtf :: (Eq a, Bounded a, Enum a)=> [a] -> Maybe [Int]
mtf = sequence . snd . mapAccumL enc [ minBound.. ]
where enc l x = (x:delete x l, elemIndex x l)
mtfD :: (Eq a, Bounded a, Enum a)=> [Int] -> [a]
mtfD = snd . mapAccumL dec [ minBound.. ]
where dec l i = let x = l !! i
in (x:delete x l, x)
```

The `mapAccumL`

function is perfect for passing the state of the dictionary
list. Another point of interest to mention is the use of `minBound`

to let the
function be polymorphic over any type for which there is a defined order and
lowest element.

For example, we can do this:

```
*Main> mtf "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES" >>= return . mtfDec :: Maybe String
Just "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"
```

or we can decode to Word8 bytes, if we want to get back the ASCII character in that form, just by specifying a different return type:

```
*Main> :m + Data.Word
*Main Data.Word> mtf "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES" >>= return . mtfDec :: Maybe [Word8]
Just [83,73,88,46,77,73,88,69,68,46,80,73,88,73,69,83,46,83,73,70,84,46,83,73,88,84,89,46,80,73,88,73,69,46,68,85,83,84,46,66,79,88,69,83]
```

Let me know your thoughts!