### 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.

### Summary

- 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
`rep`

going from the original type to its new representation - The other is
`abs`

which 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*n*^{2}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`

and`abs`

`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
- Furthermore
`rep`

is 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*(*n*^{2}) `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
`m`

be a monad. A functor would have worked fine. Returning to

`rep`

and`abs`

:`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