Map/Reduce:除了"howto“之外，还有什么理论基础吗？

Question

有一段时间我在想，你只需要一个到么半群的映射，然后reduce就会根据么半群的乘法进行缩减。

首先，这并不完全是么半群的工作方式，其次，这并不完全是map/reduce在实践中的工作方式。

也就是说，以无处不在的"count“为例。如果没有要计算的内容，任何map/reduce引擎都将返回一个空数据集，而不是一个中性元素。真扫兴。

此外，在么半群中，一个运算是为两个元素定义的。我们可以很容易地将其扩展到有限序列，或者，由于结合性，扩展到有限有序集。但是没有办法将它扩展到任意的“集合”，除非我们真正拥有一个σ-algebra。

那么，理论是什么呢？我试着找出它，但我做不到；我试着用谷歌搜索它，但什么也没找到。

Answer 1

我认为思考map-reduce的正确方式不是将其本身视为一种计算范例，而是将其视为一种类似于while循环的控制流构造。您可以将while视为一个具有两个参数的程序构造函数，一个谓词函数和一个任意程序。类似地，map-reduce构造有两个名为map和reduce的参数，每个参数都有作用。因此，与while类似，要问的有用问题是关于证明构造的程序相对于给定的前置条件和后置条件的正确性。和往常一样，这些问题涉及(a)终止和运行时性能以及(b)不变量的维护。