[Haskell-cafe] Why monoids will abide...
ekirpichov at gmail.com
Thu Jan 22 02:12:30 EST 2009
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 <dpiponi at gmail.com>:
> 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
> (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.
> On Tue, Jan 20, 2009 at 4:27 PM, Don Stewart <dons at galois.com> wrote:
>> Thanks Apfelmus for this inspiring contribution!
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe