monoid是一种数学理论，他定义了一种特殊的集合操作。
这种特殊的集合操作，满足2个特性，
1. 结合律，
数学有3大定律，结合律，自反律，以及传递律
那么结合律就是 (a + b) + c= a + (b + c)
也就是结果和操作的组合顺序无关。
再举一个例子，(a + b) + (c + d) = a + (b + c) + d = (a + d) + (b + c) ....
等等操作顺序组合。
这个加法操作就是一个monoid,
那么，在集合论里面， 异或就是一个monoid
(1 xor 0) xor (0 xor 1) = (1 xor 1) xor (0 xor 0)
那么，接下来在计算科学里面，把这种monoid的集合以及数字概念拓展到了函数概念
我们假设，这操作的不是数字和集合，而是函数会怎么样？
这些函数的复合就是复合函数，满足结合律。
也就是 f(g(x)) = g(f(x)), 复合函数我们定义为 f * g = g * f
那么在加几个函数的复合，比如有4个函数，a，b, c, d
那么，在monoid里面就是 (b * c) * (a * d) = (a * b) * (c * d)
那么，在一个函数上面的复合也具备monoid特性，就是 (a * a) * a = a * (a * a)
那么，这个在计算科学上的运用就是，所有具备monoid特性的计算模型，函数，都具备了天生的并行计算的特性。
并行计算是可以大幅度水平计算性能扩展的。
好了，我们看一个scala的例子，就是monoid模式在scala的集合操作里面有很多应用。
有几个方法，一个是foldLeft，FoldRight，Fold
还有一个是Reduce是里面的代表，
这些方法可以运用在Scala的并行计算的持久型数据结构(Persistence Data Structure)上面。
那么，foldLeft 是怎么运用在这些数据结构上面的呢？
在Scala里面要计算一个序列的Sum也就是和，那么就是
List.foldLeft(0)(_ + _) 或者 List.reduce(_ + _)
为啥说foldLeft，或者reduce可以运用于monoid，因为
(1 + (2 + (3 + 4) == (1 + 2) + 3 ) + 4)
他们满足结合律，所以不管这些加法计算怎么复合，f(f(f(1,2)，3），4）) 的结果和复合的顺序无关，
如何用程序表达这些无限次数的自我函数复合呢？就是reduce和fold，foldLeft，foldRight
我们以FoldLeft为例子，
这个函数接受一个参数，返回的是一个偏序函数(partial function)，
接受另一个高阶函数(high order function)作为参数，
这高阶函数运行完，还是一个自我可以复合的高阶函数。
def foldLeft[B](z: B)(f: (B, A) => B): B
这个函数的定义很清楚地表达了，他接受2个参数，是一个partial function，
第二个参数是一个高阶函数，也就是要定义的
可以自我复合的monoid，就是不管以任何顺序复合本身，函数是一直保持一致的状态结果。
那么其实对于这些monoid函数使用foldright是一样的，从右到左计算和从左到右的计算是一样的结果，
monoid的好处是可以运用在并发，并行计算，很多不同的计算单元可以同时计算，和合并。
因为monoid的计算顺序是和结果无关的，那么结果就是不同的计算顺序可以任意结合。
比如上面那么例子 (1 + 2) 和 （3 + 4）是可以同时在2个机器上面进行计算的，那么这个就是并行计算，大大节省了计算时间，
他们的计算结果也可以合并，就是 (3 + 7）这一个计算单元也可以在T2时间点计算。
我们这么来看这个计算顺序，这个是一个树结构的计算过程。
1 T1
+ 2 T2
+ 3 T3
+ 4 T4
这个计算是一个树状的计算过程，需要4个时间单元 一共是 O(n) 计算复杂度，在单个计算单位上面
但是如果是并发，并行计算，就是只需要2个计算单元，
1 + 2 3 + 4 T1
\ /
+ T2
那么他们的计算结果其实是一样的，因为monoid是计算结果和计算顺序无关性。
那么接下来，我们说，这个计算时间复杂度是Loga(B) a 是cpu或者计算单元的个数，而B是整个计算单元的分割数目
大家也就看出来了，这个并行计算的计算树，是一个平衡多叉树，可以用这个数据结构去分配和计算所需要的计算时间和复杂度。
平衡计算资源和有效计算时间。
PS 题外话: 适合并发操作的存储式数据结构
在Scala的集合类里面有一个特别适合并行计算的集合库，以par开头的一个包，就是Parallel Collections
里面有list，tree等等数据结构，但是都是基于持久性数据结构的设计，基本是以特殊的并发，
修改版本控制的类似于copy on write的一些数据结构，就是一个linked list，其实在不一样的并发操作，
有多个版本，对于不同的线程，进程。他们的状态是不一样的，最后会合并，基于一些特殊的版本控制计算，和分布式算法
有些是一样的。
这个好比，一个人，同时在多个次元空间，被复制了多个不同的未来，和现在，最后合并成一个。
举个例子，小A今天起床，
线程A也就是一个4维空间，里面在T1 8：00钟时刻，他在看书，
但是在线程B，另一个维度空间里面到了8：00他在刷牙
在线程C另一个维度空间里面8：00他在洗澡，
他在这个时间点上面干啥，我们叫做他的状态，能改变他的状态的就是上帝，也就是计算机。
其实，对于每一个线程里面，他的状态被复制了，这就是持久性数据结构，他的状态在同一个时间点在不同的空间不能互相访问，
但是是复制出来的。
好了，我们举例小B的例子，
小B在线程1里面穿红色衣服，
在线程2里面他要变成蓝色衣服，
在线程3里面他要变成黑色衣服。
那么，这里缺失的是时间，我们说小B是在7点穿红色衣服，还是蓝色衣服，还是黑色衣服，取决于7点是哪个线程修改了他的衣服，
这里就有不一致性，我们无从预测，小B在7点究竟穿什么颜色的衣服。
这个就是可以修改的数据结构，那么他的弱点是，在并发计算，并行计算的时候，不知道究竟小B事穿什么衣服，是红蓝黑，还是黑红蓝，
还是蓝红黑，在最后9点，小B有3个可能的状态，红衣服，蓝衣服，和黑衣服，这取决于，那个线程先运行。
那么，在看小B的例子，
在3个线程的4维空间，每一个小B的状态，被复制了一个小B出来，在线程1，小B永远是红色衣服，在线程2，小B永远是黑色衣服，
在线程3，小B永远是蓝色衣服，那么，到底小B在8：30是什么衣服，我们合并，3个线程空间，小B的状态，
有2种策略，1. 或者小B在最后一个时间点的状态就是他在8：30的衣服颜色，2. 或者由用户自己指定，喜欢看小B穿啥衣服，就是穿啥衣服。
那么，在LinkedList的例子
在 1 -> 2 -> 5 -> 6 的LinkedList里面 线程1 操作是增加节点8 ，线程2操作是在 2 到 5之间插入3
那么
T1: 1 -> 2 -> 5 -> 6 -> 8
T2: |-> 3 -> 5 -> 6
所以，对于T2这个线程看到的状态永远是 1 -> 2 -> 3 -> 5 -> 6 看不到8
对于 T1 看到的是 1 -> 2 -> 5 -> 6 -> 8 看不到3
那么，我们说，这个数据结构，不覆盖状态，就是所谓的支持并发和并行计算，的无锁计算数据结构，用的就是分布式算法的原理。
是叫做存储式或者持久数据结构。
题外话: idempotent
这里要提到另一个概念，就是idempotent，这个概念的含义是不管如何对于一个函数重复计算，他的结果不会改变。
好了，用一个REST的增删改查的例子，比如，在一个REST api里面执行一个删除操作的时候，网络断线了，被坏人掐断了，
怎么办，那么到底有没有改成，客户端要不要重新操作？这里就涉及到客户端和服务器端的状态不一致，
如果，这个删除是在成功删除后，返回结果时候断线的，那么客户端有数据，服务器端没有，
如果，这个删除是在删除操作前失败，那么，客户端和服务器端还是有数据，
但是返回结果都是一样额额，断线，断线，断线。。。。500 错误。
那客户端到底要不要再删除一次？好纠结，好了，其实不必纠结，直接删除一次好了，
因为 删除操作，是一个具有idempotent特性的操作，就是不管对于服务器施加多少次的删除操作，那么其实最后的结果都是一样的
返回的是对象已经被删除了，或者断线，哪怕断线了，不管是不是成功删除，只要继续对服务器继续一样的操作，得到的结果是一样的。
所以，有些monoid也有idempotent特性，不管如何复合，那么，他们获得的结果都是一样的。
比如XOR等等，这些被叫做Idempotent Monoid