Nottingham FP Lab Blog

Applicative functors and Google MapReduce

by Wouter on January 20, 2006.
Tagged as: Lunches.

Yesterday there were a few talks on Datatype Generic Programming. Bruno Oliveira talked about Conor’s applicative functors. Ralf Laemmel showed how Google’s MapReduce Programming Model can be captured succinctly in Haskell. I gave an idea of how the two could be related.

One of the nice properties of applicative functors is that they are closed under composition. As > Maybe and > (a ->) are applicative, so is:
> data Enum k => Dict k v = Dict (k -> Maybe v)
Using this dictionary, both Ralf’s interpretation of Google’s map and reduce correspond to the ‘apply’ of the applicative functor Dict k. Unfortunately, the correspondence wasn’t as nice as you might expect. I needed a few minor tweaks here and there to get things to fit together. The intermediate grouping operation can also be written using the traversal functions in Conor’s library.

It was clear that there is still some work to be done. Paraphrasing Graham, “If you find that the theory doesn’t match the implementation, you should probably rethink the implementation”.