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 <d...@galois.com> 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
