Re: [Haskell-cafe] Why monoids will abide...

On Thu, Jan 22, 2009 at 06:53:24AM -0800, Dan Piponi wrote:

On Wed, Jan 21, 2009 at 11:12 PM, Eugene Kirpichov wrote:

...

To my mind, in the map-reduce case you generally need a commutative monoid. Or, you need an extra infrastructure that mappend's only results from adjacent machines, or something like that.

This is a good paper on the stuff I'm talking about: http://citeseer.ist.psu.edu/blelloch90prefix.html It doesn't explicitly mention monoids but it's all about associative operations with identity.

Indeed, the parallel scan algorithm over an arbitrary monoid (originally due to Ladner and Fischer) was one of the inspirations for the use of monoids in the fingertree paper.