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.

Download Video: (HD / SD).

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



Related Posts