5
$\begingroup$

For a while I was thinking that you just need a map to a monoid, and then reduce would do reduction according to monoid's multiplication.

First, this is not exactly how monoids work, and second, this is not exactly how map/reduce works in practice.

Namely, take the ubiquitous "count" example. If there's nothing to count, any map/reduce engine will return an empty dataset, not a neutral element. Bummer.

Besides, in a monoid, an operation is defined for two elements. We can easily extend it to finite sequences, or, due to associativity, to finite ordered sets. But there's no way to extend it to arbitrary "collections" unless we actually have a sigma-algebra.

So, what's the theory? I tried to figure it out, but I could not; and I tried to go google it but found nothing.

Improve this question
$\endgroup$
6
  • 5
    $\begingroup$ What do you mean by map/reduce? $\endgroup$
    – Benjamin Steinberg
    Commented Dec 17, 2011 at 23:02
  • 6
    $\begingroup$ Asking on the stackexchange CS site will work much better than here, where you'll have to explain whatmap/reduce is :) $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Dec 17, 2011 at 23:18
  • 1
    $\begingroup$ Even though I have heard of map/reduce several times and even seen some examples, I'd like to see the closest thing the OP knows to a definition of map/reduce. Certainly it won't be an exact definition, since this is what the OP is searching for, but at least it will probably be more formal and less handwaving than what I know about it. $\endgroup$
    – darij grinberg
    Commented Dec 17, 2011 at 23:24
  • 1
    $\begingroup$ Lookup monad instead of monoid. $\endgroup$
    – François G. Dorais
    Commented Dec 18, 2011 at 0:11
  • $\begingroup$ (reduction need not be associative though...) $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Dec 18, 2011 at 0:15

2 Answers 2

Reset to default
16
$\begingroup$

Yes.

Ok, while that was fun, let's give you a real answer. As François mentionned, the key word is 'Monad'. Basically/roughly your programming language forms a category, with types as the objects, and functions as the arrows. Then 'map' is the action of a functor on arrows, and 'reduce' is an ordered fold, which is (again roughly) the 'bind' of a monad -- see MapReduce as a Monad as a starting point. For the semantics of 'fold', I rather like this paper by Bird and Paterson on (generalized) folds.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Merci beaucoup Jacques! $\endgroup$
    – François G. Dorais
    Commented Dec 18, 2011 at 5:31
  • $\begingroup$ Hmm. the discussion by the first link is about "generalized monad", Haskell style. While it is probably feasible to split the notion into two functors, declaring the second one a monad, I'd stay away from the arbitrariness of programming thinking and hold to a more mathematical interpretation. As to the second paper, monads are not even mentioned there. Instead, as expected, it talks about monoids being used for reduction; and duly so. More, it defines the monoid on Map type that is being used in map/reduce, thus answering my question. $\endgroup$
    – Vlad Patryshev
    Commented Feb 20, 2012 at 1:50
0
$\begingroup$

You might also like this:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.104.5859&rep=rep1&type=pdf

Improve this answer
$\endgroup$
1
  • $\begingroup$ The link goes to the paper "Google’s MapReduce Programming Model — Revisited" by Ralf Lämmel (Microsoft). Here is an HTML abstract page for the linked paper: core.ac.uk/display/20722901 $\endgroup$
    – S. Carnahan ♦
    Commented Dec 15, 2016 at 17:31

Not the answer you're looking for? Browse other questions tagged .