Is there any math foundation for map/reduce? - MathOverflow

Is there any math foundation for map/reduce?

2011-12-17T22:56:42Z

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.

Answer by Jacques Carette for Is there any math foundation for map/reduce?

2011-12-18T02:19:13Z

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.

Answer by none for Is there any math foundation for map/reduce?

2012-01-17T05:07:07Z