Single-Pass Huffman Coding

Summary

Single-Pass Huffman Coding Posted on February 17, 2018 While working on something else, I figured out a nice Haskell implementation of Huffman coding, and I thought I’d share it here. I’ll go through a few techniques for transforming a multi-pass algorithm into a single-pass one first, and then I’ll show how to use them for Huffman. If you just want to skip to the code, it’s provided at the end . The algorithm isn’t single-pass in the sense of Adaptive Huffman Coding: it still uses the normal Huffman algorithm, but the input is transformed in the same traversal that builds the tree to transform it. Circular Programming There are several techniques for turning multi-pass algorithms into single-pass ones in functional languages. Perhaps the most famous is circular programming: using laziness to eliminate a pass. R. S. Bird (1984) used this to great effect in solving the repmin problem: Given a tree of integers, replace every integer with the minimum integer in the tree, in one pass. For an imperative programmer, the problem is relatively easy: first, write the code to find the minimum value in the tree in the standard way, using a loop and a “smallest so far” accumulator. Then, inside the loop, after updating the accumulator, set the value of the leaf to be a reference to the accumulator. At first, that solution may seem necessarily impure: we’re using global, mutable state to update many things at once. However, as the paper shows, we can claw back purity using laziness: data Tree a = Leaf a | Tree a :*: Tree a repMin :: Tree Integer -> Tree Integer repMin xs = ys where (m, ys) = go xs go (Leaf x) = (x, Leaf m) go (xs :*: ys) = (min x y, xs' :*: ys') where (x,xs') = go xs (y,ys') = go ys There and Back Again Let’s say we don’t have laziness at our disposal: are we hosed? No ! Danvy and Goldberg (2005) explore this very issue, by posing the question: Given two lists, xs and ys, can you zip xs with the reverse of ys in one pass? The technique used to solve the problem ...