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

[Eugene Kirpichov]

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
>
> 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 <dons at galois.com> wrote:
>> http://apfelmus.nfshost.com/monoid-fingertree.html
>>
>> Thanks Apfelmus for this inspiring contribution!
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>