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

[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 <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
>