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