Re: [Haskell-cafe] Why monoids will abide...
On 2009 Jan 22, at 10:09, Andrew Wagner wrote: See, that's the kind of name we need! StructureWithAssociativeOperationAndIdentity -- make both the mathematicians AND the non-mathematicians mad! SimpleArithmetic (you have numbers and a single arithmetic operation on them). You can play similar games with the mathematical concepts of groups and rings. (But you get into trouble with magmas and semigroups.) In any case, my response to bikeshedding these days is to present a fait accompli so people can just get stuff done instead of waiting for many-legs-and-no-brain (otherwise known as a committee) to do something. The math terms have at least the advantage of already being well defined. Yes, this means you get to learn some abstract math --- but then, you're going to be faced with that the first time you encounter (or need!) type-level Peano numbers anyway. Or fix/mfix (least defined fixed point). -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allb...@kf8nh.com system administrator [openafs,heimdal,too many hats] allb...@ece.cmu.edu electrical and computer engineering, carnegie mellon universityKF8NH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why monoids will abide...
On Wed, Jan 21, 2009 at 11:12 PM, Eugene Kirpichov ekirpic...@gmail.com 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
Re: [Haskell-cafe] Why monoids will abide...
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 dpip...@gmail.com wrote: On Wed, Jan 21, 2009 at 11:12 PM, Eugene Kirpichov ekirpic...@gmail.com 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why monoids will abide...
On Thu, Jan 22, 2009 at 06:53:24AM -0800, Dan Piponi wrote: On Wed, Jan 21, 2009 at 11:12 PM, Eugene Kirpichov ekirpic...@gmail.com 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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why monoids will abide...
Thanks; I saw you mention the paper before, but now I finally started reading it :) By the way, the paper *does* arrange an extra infrastructure for mappending only adjacent results. Looks like with a commutative monoid, a fold could be done in a fully distributed fashion, however it would no more be a scan. 2009/1/22 Dan Piponi dpip...@gmail.com: On Wed, Jan 21, 2009 at 11:12 PM, Eugene Kirpichov ekirpic...@gmail.com 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
Re: [Haskell-cafe] Why monoids will abide...
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/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why monoids will abide...
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
Re: [Haskell-cafe] Why monoids will abide...
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 dpip...@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 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why monoids will abide...
2009/1/21 Don Stewart d...@galois.com: 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 And for an introduction : http://sigfpe.blogspot.com/2009/01/haskell-monoids-and-their-uses.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
