little forest

加法是自然之道 - Monoid

March 01, 2020 by Sylvenas

积木游戏

说出来你可能不信，我只花了十分钟的时间就教会三岁的小孩什么是半群,ahhhhh.jpg

周末在家陪小侄女玩了一个小时的积木，在不断叠加积木的过程中，突然想到用搭积木的案例来描述什么是半群异常的清晰,看下面三个积木：

红黄蓝积木

看到这三个积木，(是不是有一种把他们叠在一起的冲动)，按照常规操作，有一部分人可能会总左向右开始叠加，也就是先把最左边的红色积木和中间的黄色积木，搭在一起；然后把最后一个蓝色叠加上，那么最后的结果是：

积木拼接结果

然后可能有另一部分人从右向左叠加，那么就是先拼接黄色和蓝色；然后最后加上红色的积木；最后得到的结果，毫无疑问和第一种是一样的，你这不是废话吗!!

组合方法如果满足这种不论先拼接哪一块，最后按顺序组合在一起，得到的结果就是一样的，这被称为associative(可结合的)，积木的游戏很明显是满足这个法则的；而这个过程，我只演示了一遍，三岁的小侄女，就明白了这个道理；我觉的我们20多岁的人，可能不需要任何解释吧；

而满足结合律的数据类型，则可以称之为半群(Semigroup)，是不是想起来了，很常用的Array.prototype.concat就是一个完全类似的东西，下面我们给半群一个精确的定义和解释。

半群

一个半群(Semigroup)是带有组合方法(i.e.,Array的concat)的数据类型，假设我们的组合符号是+,那么组合方法满足结合律:

a + (b + c) = (a + b) + c

在举个小学数学的知识来验证一下：

const a = 1;
const b = 2;
const c = 3;

a + (b + c) === (a + b) + c   // => true

const e = true;
const f = false;
const g = true;

e && (f && g) === (e && f) && g   // => true

Ok!让我们切换到JavaScript的世界：

'a'.concat('b'.concat('c')) === 'a'.concat('b').concat('c') // => true

[1, 2, 3].concat([4, 5, 6].concat([7, 8, 9]))   // [1,2,3,4,5,6,7,8,9]
[1, 2, 3].concat([4, 5, 6]).concat([7, 8, 9])   // [1,2,3,4,5,6,7,8,9]

由于JavaScript中String,Array类型，原型链上本身具有cancat方法，所以我们可以不断的.concat .concat;但是我们Number类型却没有，所以没法实现类似1.concat(2).concat(3)的代码；

回想一下第一章中的Box理念，如果我们把数字1，包裹进Box中，则我们可以调用Box(1)上面的map方法，我们可以仿照Box再创建一个容器Sum,来包裹数字,让Sum(1)拥有concat方法，看看Sum的实现：

const Sum = x => ({
    x,
    concat: ({ x: y }) => Sum(x + y),
    [inspect]: () => `Sum(${x})`
})

下面我们可以做个验证：

Sum(1).concat(Sum(2).concat(Sum(3)))    // => Sum(6)
Sum(1).concat(Sum(2)).concat(Sum(3))    // => Sum(6)

研究明白了加法的知识，不妨继续扩展一下小学数学知识：

a * (b * c) === (a * b) *  c                   // 乘法
max(a, max(b, c)) === max(max(a, b), c)       // 最大值
min(a, min(b, c)) === min(min(a, b), c)       // 最小值

相信根据Sum的案例，大家可以很轻松的写出很多类似的案例：

// 对任意的 bool 类型求 并(&&) 的结果
const All = x => ({
    x,
    concat: ({ x: y }) => All(x && y),
    [inspect]: () => `All(${x})`
})

// 对任意的自然数求 max(最大值) 的结果
const Max = x => ({
    x,
    concat: ({ x: y }) => Max(x > y ? x : y),
    [inspect]: () => `Max(${x})`
})

**Note:**类似于functor为一个mappable的数据类型，也可以类比半群就是一个concatible的数据类型，这样更好理解

在 Fantasy Land Spec中半群的结合方法也确实就叫concat)

加法是自然之道

让我们再次探索一下小学数学知识：我们已经不断的验证了加法满足结合律，那么减法呢？减法满足结合律吗？

(5 - 2) - 1 // => 2
5 - (2 - 1) // => 4

这就是小学数学老师教的，做加法的时候，可以随意的添加和删除括号；而减法绝不能这样操作！

为什么？因为减法不满足结合律！

我们经常说道法自然，那么自然之道是什么？我认为自然是在做加法，老子道德经说“道生一，一生二，二生三，三生万物”；反映在数学上就是，假如我们创造一个数字1,然后有一个计算法则+,则我们可以很轻松很直觉的创造出所有的自然数！

我们平常写代码的时候，可能刚开始设计的很巧妙，思路很清晰；但是随着业务的迭代(产品经理的频繁变换),代码不可避免会变得很多很多； 贴一个经常吐槽Java(假装很懂Java)的一句话：Java的问题不是太啰嗦而是OOP使得类的数目很多。我想不管使用什么语言，代码量增多迟早会面对，而是要积极面对。面向对象原则和GOF设计模式已经在告诉我们如何维护拓展这些类代码：宁可增加新的类代码，尽量不要去修改那些经过测试已经成熟稳定的代码；也就是说不要去做修改替换，而是要做增加！这种增加如同树的自然成长，是一种干生枝，枝生叶的繁茂。

切换到FP的理念中，我们听了太多的纯函数,不可变数据，避免共享状态等等，细想一下不管是函数也好，数据也好，他们有一个共同点就是在原来的基础上添加(append/concat)而是修改原来的！

幺元

现在我们来看一个特殊的数字0，在加法中0是一个很特殊的存在，特殊在哪里呢？

  • 任何自然数和0相加都等于它本身：1 + 0 = 1
  • 0可以添加到加法运算中的任意位置，而不影响计算结果：1 + 2 + 3 = 0 + 1 + 2 + 3 = 1 + 2 + 0 + 3

仔细思考一下，0存在的意义在哪里呢？实际上0是数学中对于自然世界中空的抽象。

在代码的世界中，空是一个很常见的定义，比如：空字符串'',空数组[],这些空值通常用来实现初始化的值，而这种'空值'(和任何元素结合都不会影响结果的单位元)在函数式编程中被称为幺元(Identity Element)或者单位元。用数组的例子来看就是：

[] + [1,2] = [1,2] + [] = [1,2]

加号表示组合的意思，等号表示“值”相等。

结合半群Sum来看,很明显加法操作的幺元为Sum(0)：

Sum.empty = () => Sum(0)

const res1 = Sum.empty().concat(Sum(1)).concat(Sum(2))  // => Sum(3)
const res2 = Sum(1).concat(Sum.empty().concat(Sum(2)))  // => Sum(3)

同样对于All的幺元则为：All.empty = () => All(true),true和任何boolean值结合都不会影响原来的值。

除了Sum(0),All(true),我们可以在代码中找到很多其他的幺元的例子，比如：'',[],{}。

下面我们看一个稍微特殊一点的数字：无穷大(∞)。在加法中，我们不是找到了0作为幺元吗？无穷大看上去是空数字的反面，但是它也是一个单位元，但是如何描述无穷大是数字的空元素呢？答案是使用min操作,看下面伪代码：

min(∞, x) = x;  
min(x, ∞) = x;

对于求最小值的操作来说，在任何地方插入无穷大都不会影响计算结果，对吧！ 同样的负无穷大就是max操作的幺元；数字1就是乘法运算的幺元。现在看来多个‘空对象’是可以同时存在的，只是在不同操作下对于空的定义不同罢了。

单元函数

函数式编程的核心在于函数组合，那么对于函数组合这个操作来说，它的幺元是什么呢？答案是一个很简单的单元函数(identity function):x =>x,通常被简称为id。

单元函数是一个对函数输入没有做任何操作直接返回的函数(id(1) === 1,id(x) === x)，很明显这个函数和任意的函数进行组合，或者插入到函数组合的任意位置，都不影响函数组合的结果。

const compose = (...fns) => x => fns.reduceRight((v, f) => f(v), x)

compose(g, h, x) === compose(g, h)
compose(g, x, h) === compose(g, h)
compose(x, g, h) === compose(g, h)

通过这种组合方式，我们可以看到单元函数是函数组合操作的幺元

广群，半群，幺半群

上面介绍了半群和幺元的概念，本质上来说是很简单的东西，平常代码中也会经常用到，只是没有特意的强化和准确的定义这个概念;下面继续介绍另一个简单的概念：广群

广群

对于某非空集合S，若存在S上的二元运算"*"使得对于任意的a,b∈S,有a*b∈S（运算封闭），则称{S,*}为广群(Group)。 　 广群只是定义一个集合，集合中有元素和操作，操作结果也属于这个集合，这样泛泛的集合称为广群。　

如果广群再加上结合律约束，就会得到半群，因此半群是广群的子集，要求更苛刻些，而半群可以找到一个合适的幺元（identity element），则可以把该半群称为幺半群，也就是**结合律+幺元=幺半群**，所以，Monid对应的中文是幺半群。

所以半群是广群的子集，而幺半群很明显是半群的子集。

总结

这一节介绍的概念比较多，但是在我们完全理解了Functor的基础上，理解半群(concatible),幺元(id),幺半群(半群 + 幺元)就是很简单的概念；一个monoid是一个元素(也可称对象)的集合，monoid首先是一个集合，但是这个集合有一些约束条件，也就是说，是一个特殊的集合，满足结合律和幺元，这种元和其他元素结合时，并不会改变那些元素。

下面的一章则会进入我们函数式编程进阶的核心内容了：Monad。我们使用一句经典名言，来做个引言：

“A monad is just a monoid in the category of endofunctors. What’s the problem?”

SHARE ON: