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

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. 2009/1/21 Dan Piponi :

Another important application of monoids is in parallelisation. In map-reduce you want to split the reduce part over multiple processors and combine the results back together again. Associativity ensures that when you combine the pieces together you get the same result as if you did the whole operation on one processor.

Eg. we can rewrite

(((a `mappend` b) `mappend` c) `mappend` d

as

(a `mappend` b) `mappend` (c `mappend` d)

and compute (a `mappend` b) and (c `mappend` d) on separate processors. And so on recursively. (The mempty element tells us what result we should give if we're reducing an empty array.)

For a large class of problems, parallelising the algorithm consists of teasing out the hidden monoid structure so it can be chopped up in this way. -- Dan

On Tue, Jan 20, 2009 at 4:27 PM, Don Stewart wrote:

...

http://apfelmus.nfshost.com/monoid-fingertree.html

Thanks Apfelmus for this inspiring contribution! _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe