JP Embedded Solutions

Implementing MapReduce in Haskell

Summary

MapReduce is a general technique for massively parallel programming developed by Google.  It takes its inspiration from ideas in functional programming, but has moved away from that paradigm to a more imperative approach.

We have found that MapReduce can be expressed naturally, using functional programming techniques, as a form of monad, which we have implemented in Haskell.  The basic idea is to convert each map / reduce stage into a monadic function, so MapReduce becomes a composition:

mapReduce :: [String] -> [(String,Int)]
mapReduce state = runMapReduce mr state
where
mr = distributeMR >>= wrapMR mapper >>= wrapMR reducer

In addition, the implementation is inherently parallel.

Suggestions for future research

  1. Look at ways of making distributing data across threads more efficient
  2. Develop ways of using true concurrency so the approach can be used on clusters

Downloads

About these ads

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

4 Responses

  1. […] have discussed elsewhere my initial implementation of MapReduce as a monadic operation that works in parallel processes on a single machine.  Here I take the first steps towards […]

  2. […] have discussed elsewhere my initial implementation of MapReduce as a monadic operation that works in parallel processes on a single machine.  Here I take the first steps towards […]

  3. Ah, but how fast will it run?

    • On a Macbook Pro, it took only a few seconds to do word-count on a million words. I am working on a distributed version, but rather lost the impetus. Perhaps I should start again.

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: