Imo this is interesting beyond the “Haskell implementation of X” genre, as a good explanation of arithmetic coding and why it actually works. As the article points out, arithmetic coding was introduced in the 1970s, but didn’t gain popularity until a public, “accessible implementation” was published in 1987— but that “accessible implementation” was a 300-line, dense C program where it was not entirely obvious why the rather obscure series low-level operations it performed were correct. Part of that is inherent to the algorithm, which is a bit tricky: the paper notes, “there is rather a lot of arithmetic in arithmetic coding… arithmetic coding is a simple idea but one that requires care to implement with limited-precision integer arithmetic”. But this attempts to work through an implementation that makes it more clear what arithmetic coding/decoding is doing, and why decoding correctly produces the original input.