JP Embedded Solutions

MapReduce as a monad transformer

Current status

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 monadic type 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.

Next steps

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.

References

Here are the relevant papers:

  1. Map Reduce as a Monad: the original paper, published in The Monad Reader
  2. The MapReduce type of a Monad: the new paper describing MapReduceT and the relation to the State monad
About these ads

Filed under: Functional Programming, Haskell, MapReduce, , , , , ,

4 Responses

  1. arjuna says:

    The links to the pdf files are screwed by wordpress. These are the correct ones, here as a reference for other readers until fixed in the post
    http://media.jpembeddedsolutions.com/pdf/mrmonad.pdf
    http://media.jpembeddedsolutions.com/pdf/mapreduce.pdf
    Thanks for the interesting articles =)

  2. hydo says:

    Yes! I would love to follow this and contribute where I can.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Copyright © 2011, JP Embedded Solutions, All rights reserved

All content is subject to the BSD license

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: