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