Building a data compression utility in Haskell using Huffman codes

In this post we will implement a data compression program in about 150 lines of Haskell. It will use Huffman coding and handle arbitrary binary files using constant memory for encoding and decoding.

We will leverage laziness to keep our memory footprint constant while the code remains modular. A good example of Why Functional Programming Matters.

The idea is straightforward: Map each character to a unique sequence of bits. Choose the bit sequences such that common characters map to shorter bit sequences and rare characters map to longer ones. Compression is achieved by the most common characters using fewer bits than their uncompressed representation.

I say characters here, but we could really map anything to bits; like whole words or even bit patterns themselves. But let’s not worry about that for now and stick with characters for the time being.

Let’s say we have the string aaab and we want to compress it using Huffman codes. Well, we know there are only two characters in our input so a single bit should be enough to differentiate which one is which at each position. Here is a possible mapping:

Leave a Comment