On Thu, Jan 22, 2009 at 06:53:24AM -0800, Dan Piponi wrote: > On Wed, Jan 21, 2009 at 11:12 PM, Eugene Kirpichov <ekirpic...@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. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
