begriffs

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