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 :

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

See, that's the kind of name we need! StructureWithAssociativeOperationAndIdentity -- make both the mathematicians AND the non-mathematicians mad! On Thu, Jan 22, 2009 at 9:53 AM, Dan Piponi wrote:

On Wed, Jan 21, 2009 at 11:12 PM, Eugene Kirpichov wrote:

...

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.

This is a good paper on the stuff I'm talking about: http://citeseer.ist.psu.edu/blelloch90prefix.html It doesn't explicitly mention monoids but it's all about associative operations with identity. -- Dan _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On Thu, Jan 22, 2009 at 06:53:24AM -0800, Dan Piponi wrote:

On Wed, Jan 21, 2009 at 11:12 PM, Eugene Kirpichov wrote:

...

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.

This is a good paper on the stuff I'm talking about: http://citeseer.ist.psu.edu/blelloch90prefix.html It doesn't explicitly mention monoids but it's all about associative operations with identity.

Indeed, the parallel scan algorithm over an arbitrary monoid (originally due to Ladner and Fischer) was one of the inspirations for the use of monoids in the fingertree paper.

On Thu, 22 Jan 2009, Eugene Kirpichov wrote:

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.

The paper http://www.cs.vu.nl/~ralf/MapReduce/ analyzes the model of Google's MapReduce and Sawzall. quick haskell summaries at: http://www.thenewsh.com/~newsham/x/machine/MapReduce.hs http://www.thenewsh.com/~newsham/x/machine/Sawzall.hs The MapReduce model isn't based directly on a monoid, but the Sawzall model is. Tim Newsham http://www.thenewsh.com/~newsham/

On Thu, 2009-01-22 at 16:11 +0100, Ketil Malde wrote:

One wart that was briefly mentioned during the Great Monoid Naming Thread of 2009 is the need to wrap types in newtypes to provide multiple instances of the same class with different semantics -- the archetypical example being Integer as a monoid over addition as well as multiplication.

I was just wondering if not phantom types might serve here as an alternative way to go about that. Here's a small example illustrating it:

---------------------------------------- {-# LANGUAGE EmptyDataDecls #-} {-# LANGUAGE FlexibleInstances #-}

module Monoids where import Data.Monoid

data Foo a = Foo Integer deriving (Show, Eq)

data Additive data Multiplicative

instance Monoid (Foo Additive) where mappend (Foo x) (Foo y) = Foo (x+y) mempty = Foo 0

instance Monoid (Foo Multiplicative) where mappend (Foo x) (Foo y) = Foo (x*y) mempty = Foo 1

instance Num (Foo a) where fromInteger x = Foo x Foo x + Foo y = Foo (x+y) Foo x * Foo y = Foo (x*y) signum (Foo x) = Foo (signum x) ----------------------------------------

Loading this into ghci, you get: *Monoids> mconcat [1,2]

<interactive>:1:0: Ambiguous type variable `t' in the constraints: `Monoid t' arising from a use of `mconcat' at <interactive>:1:0-12 `Num t' arising from the literal `2' at <interactive>:1:11 Probable fix: add a type signature that fixes these type variable(s) *Monoids> mconcat [1,2::Foo Additive] Foo 3 *Monoids> mconcat [1,2::Foo Multiplicative] Foo 2

(This can of course be prettified a bit by omitting the constructor from the Show instance).

Any thought about this, pro/contra the newtype method?

The old wiki had an excellent page that has not been replicated either verbatim or in spirit in the new wiki. http://web.archive.org/web/20060831090007/http://www.haskell.org/hawiki/Comm... This lists many small tips and tricks that Haskell programmers have discovered/used throughout the years. This particular example is an example of using wrapper types to attach a phantom type as described here: http://web.archive.org/web/20070614230306/http://haskell.org/hawiki/WrapperT...

On Tue, 2009-01-27 at 08:51 -0800, Anish Muttreja wrote:

On Thu, 22 Jan 2009 09:46:19 -0800, Derek Elkins wrote:

...

The old wiki had an excellent page that has not been replicated either verbatim or in spirit in the new wiki. http://web.archive.org/web/20060831090007/http://www.haskell.org/hawiki/Comm...

Thanks, this is really useful.

There is a "wikisnapshot" on haskell.org http://haskell.org/wikisnapshot/CommonHaskellIdioms.html which looks like a replication and has more working links than the web.archive.org page.

The snapshot is quite a bit older than what is available on archive.org. You should be able to stick the link to any page that doesn't work into archive.org and get a version that does work (i.e. re-search for the page.)