Difference Lists and the Codensity Monad
February 4, 2016
Mio Alter shares two tricks for Haskell code optimization: the difference list and the codensity monad. The two are related, and have common history dating back to a math theorem from 1854. Watch this video to learn how Haskell’s abstraction allows us to apply ideas from long before the computer age.
- Slides available here
- Difference lists and the codensity monad are two tricks for program optimization
- We start with a monoid (or monad) and replace it with a monoid (or monad) of functions
- This allows us to replace recursive constructions with function composition and application
- In both constructions we have two functions that obey laws.
- One is
repgoing from the original type to its new representation
- The other is
abswhich goes from the new type back to the original
- One is
- An Example
Consider a function to reverse a list
rev  =  rev (x:xs) = rev xs ++ [x]
- It’s inefficient because
(++)has to traverse over the first argument every time, making this an n2 algorithm
- In 1984 Hughes invented the difference list
- Rather than considering the monoid
[a], we’ll consider the monoid of functions from
[a] -> [a].
type EList a = [a] -> [a]
- Next up is to define
rep xs = (xs ++)
abs f = f 
The new reverse function is
abs . rev’where
rev’  = rep  rev’ (x:xs) = rev’ xs . rep [x]
- This ends up being O(n) since each function composition is O(1).
- How would you ever invent this technique? It seems like a fluke.
- Well in hindsight both lists under concatenation and functions under composition are monoids
repis a homomorphism, i.e.
rep (xs ++ ys) = rep xs . rep ys
- So it’s not unreasonable…but not motivated either
- Surprise, this technique was known in 1854, long before computers!
- Cayley’s Theorem: every monoid is isomorphic to a submonoid in its monoid of endomorphisms
- This is a good place to start, but we can take it further with the codensity monad
- An example of building a tree and traversing a downward zigzag left, right, left, right
- With the functions in this example it will be O(n2)
CodT m a :: forall z. (a -> m z) -> m z
- Kind of weird looking, but plays a similar role on monads as the difference list does to lists
- Notice (in the actual slides of the talk) that the new monad does not require
mbe a monad. A functor would have worked fine.
rep t = (t >>=) abs p = p return
- Contrasting difference lists and the codensity monad
- A nod to category theoretic things not covered in this talk
- Further resources
- Rivas and Jaskelioff - Notions of Computations as Monoids
- Hughes - A Novel Representation of Lists and its Application to the Function “Reverse”
- Voigtlander - Asymptotic Improvement of Computations over Free Monads
- Hutton, Jaskelioff, and Gill - Factorising Folds for Faster Functions
- Hinze - Kan Extensions for Program Optimization