A while ago, I wrote a piece describing a simple way of implementing MapReduce as a Monad in Haskell. As part of my further research I’ve discovered that in fact MapReduce is very naturally a Monad Transformer. This means that given any m one can associate to it a MapReduce type MapReduceT m. If m is an Additive Monad, then so is MapReduceT m.
This is theoretically interesting, as well as providing a nice pedagogical introduction to Monad Transformers and Additive Monads. Furthermore, I have proved that the Haskell State Monad is in fact the MapReduce type associated to the (rather trivial) monad of maps. I’ve written this up in a short paper, and would welcome comments and, to be honest, suggestions as to anywhere I could try to publish it.
I’m working (slowly) on a distributed version of this framework based on CloudHaskell, at the moment limiting myself to the original, simple MapReduce monad. So far I have distributed storage working, so when I get the time, it should not take much more effort. If anyone is interested in joining in with this research programme, I’d be very happy to share the work.
Here are the relevant papers:
- Map Reduce as a Monad: the original paper, published in The Monad Reader
- The MapReduce type of a Monad: the new paper describing MapReduceT and the relation to the State monad