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

[Ross Paterson]

On Thu, Jan 22, 2009 at 06:53:24AM -0800, Dan Piponi wrote:
> On Wed, Jan 21, 2009 at 11:12 PM, Eugene Kirpichov <ekirpichov at gmail.com> 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.