### begriffs

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
• 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
• 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` 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(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 `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