Table of Contents

前言
范畴论
函数的合成与柯里化
函子
- 概念
- 代码实现
of 方法
Maybe 函子
Either 函子
ap 函子
Monad 函子
IO 操作
参考

前言

在看龙书(编译原理)的过程中多次遇到函数式编程这个概念，故做以下总结。

函数是一种最基本的任务，一个大型程序就是一个顶层函数调用若干底层函数，这些被调用的函数又可以调用其他函数，即大任务被一层层拆解并执行。所以函数就是面向过程的程序设计的基本单元。而函数式编程虽然可以归结到面向过程的程序设计范式中，但其思想更接近数学计算。

首先辨析以下计算机（Computer）和计算（Compute）的概念：

在计算机的层次上，CPU执行的是加减乘除的指令代码，以及各种条件判断和跳转指令，汇编语言是最贴近计算机的语言。
计算则指数学意义上的计算，越是抽象的计算，离计算机硬件越远

对应到编程语言，就是越低级的语言，越贴近计算机，抽象程度低，执行效率高，比如C语言；

越高级的语言，越贴近计算，抽象程度高，执行效率低，比如Lisp语言

数式编程就是一种抽象程度很高的编程范式，纯粹的函数式编程语言编写的函数没有变量，因此，任意一个函数，只要输入是确定的，输出就是确定的，这种纯函数我们称之为没有副作用。而允许使用变量的程序设计语言，由于函数内部的变量状态不确定，同样的输入，可能得到不同的输出，因此，这种函数是有副作用的。

函数式编程的一个特点就是，允许把函数本身作为参数传入另一个函数，还允许返回一个函数！

面向对象编程(OOP)通过封装变化使得代码更易理解。函数式编程(FP)通过最小化变化使得代码更易理解。 – Michacel Feathers（Twitter）

范畴论

函数式编程的起源，是一门叫做范畴论（Category Theory）的数学分支，理解函数式编程的关键，就是理解范畴论。它是一门很复杂的数学，认为世界上所有的概念体系，都可以抽象成一个个的"范畴"（category）。

1.1 范畴的概念

范畴论是一种研究抽象数学形式的科学，它把我们的数学世界抽象为两个概念：

维基百科的一句话定义如下。

“范畴就是使用箭头连接的物体。"（In mathematics, a category is an algebraic structure that comprises “objects” that are linked by “arrows”. ）

也就是说，彼此之间存在某种关系的概念、事物、对象等等，都构成"范畴”。随便什么东西，只要能找出它们之间的关系，就能定义一个"范畴"。

上图中，各个点与它们之间的箭头，就构成一个范畴。

箭头表示范畴成员之间的关系，正式的名称叫做"态射"（morphism）。

范畴论认为，同一个范畴的所有成员，就是不同状态的"变形"（transformation）。

通过"态射"，一个成员可以变形成另一个成员。

于是我们可以总结出范畴的数学模型。

所有成员是一个集合
变形关系是函数

也就是说，范畴论是集合论更上层的抽象，简单的理解就是"集合 + 函数"。理论上通过函数，就可以从范畴的一个成员，算出其他所有成员。

1.2 范畴与容器

我们可以将"范畴"想象成是一个容器，里面包含两样东西：

值（value）
值的变形关系，也就是函数。

下面我们使用代码，定义一个简单的范畴：

class Category {
  constructor(val) { 
    this.val = val; 
  }

  addOne(x) {
    return x + 1;
  }
}

上面代码中，Category是一个类，也是一个容器，里面包含一个值（this.val）和一种变形关系（addOne）。你可能已经看出来了，这里的范畴，就是所有彼此之间相差1的数字

注意：本文后面凡是提到"容器"的地方，全部都是指"范畴"。

1.3 范畴论与函数式编程的关系

范畴论使用函数来表达范畴之间的关系。

伴随着范畴论的发展，就发展出一整套函数的运算方法。这套方法起初只用于数学运算，后来有人将它在计算机上实现了，就变成了今天的"函数式编程"。

本质上，函数式编程只是范畴论的运算方法，跟数理逻辑、微积分、行列式是同一类东西，都是数学方法，只是碰巧它能用来写程序

这也可以解释为什么函数式编程要求函数必须是纯的，不能有副作用。因为它是一种数学运算，原始目的就是求值，不做其他事情，否则就无法满足函数运算法则了

在函数式编程中，函数就是一个管道（pipe）。这头进去一个值，那头就会出来一个新的值，没有其他作用

函数的合成与柯里化

函数式编程有两个最基本的运算：合成和柯里化：

函数的合成

如果一个值要经过多个函数，才能变成另外一个值，就可以把所有中间步骤合并成一个函数，这叫做"函数的合成"（compose）

上图中，X和Y之间的变形关系是函数f，Y和Z之间的变形关系是函数g，那么X和Z之间的关系，就是g和f的合成函数g·f。

那么合成两个函数的简单代码如下：

const compose = function (f, g) {
  return function (x) {
    return f(g(x));
  };
}

函数的合成还必须满足结合律

compose(f, compose(g, h))
// 等同于
compose(compose(f, g), h)
// 等同于
compose(f, g, h)

前面说过，函数就像数据的管道（pipe）。那么，函数合成就是将这些管道连了起来，让数据一口气从多个管道中穿过。

组合函数

上面是最简单的函数合成的概念，在实际应用中，将上述思想称之为组合函数

我们可以通过组合小的、确定性的函数，来创建更大的软件组件和功能的过程，会生成更容易组织、理解、调试、扩展、测试和维护的软件。

对于组合，我觉得是函数式编程里面最精髓的地方之一，因为在整个学习函数式编程里，所遇到的基本上都是以组合的方式来编写代码，这也是改变你从一个面向对象，或者结构化编程思想的一个关键点。

这里可以将组合与继承两种概念进行对比。

函数组合就是一种将已被分解的简单任务组织成复杂的整体过程。

现在有这样一个需求：给你一个字符串，将这个字符串转化成大写，然后逆序。可以这么写：

var str = 'function program'

// 一行代码搞定
function oneLine(str) {
    var res = str.toUpperCase().split('').reverse().join('')
    return res;
}

// 或者 按要求一步一步来，先转成大写，然后逆序
function multiLine(str) {
    var upperStr = str.toUpperCase()
    var res = upperStr.split('').reverse().join('')
    return res;
}

console.log(oneLine(str)) // MARGORP NOITCNUF
console.log(multiLine(str)) // MARGORP NOITCNUF

但是现在产品又突发奇想，改了下需求，把字符串大写之后，把每个字符拆开之后组装成一个数组，比如 ’aaa‘ 最终会变成 [A, A, A]。

那么这个时候我们就需要更改我们之前我们封装的函数。这就修改了以前封装的代码，其实在设计模式里面就是破坏了开闭原则。

我们如果把最开始的需求代码写成这个样子，以函数式编程的方式来写:

var str = 'function program'

function stringToUpper(str) {
    return str.toUpperCase()
}

function stringReverse(str) {
    return str.split('').reverse().join('')
}

var toUpperAndReverse = 组合(stringReverse, stringToUpper)
var res = toUpperAndReverse(str)

那么当我们需求变化的时候，我们根本不需要修改之前封装过的东西

var str = 'function program'

function stringToUpper(str) {
    return str.toUpperCase()
}

function stringReverse(str) {
    return str.split('').reverse().join('')
}

// var toUpperAndReverse = 组合(stringReverse, stringToUpper)
// var res = toUpperAndReverse(str)

function stringToArray(str) {
    return str.split('')
}

var toUpperAndArray = 组合(stringToArray, stringToUpper)
toUpperAndArray(str)

可以看到当变更需求的时候，我们没有打破以前封装的代码，只是新增了函数功能，然后把函数进行重新组合

开闭原则是指一个软件实体如类、模块和函数应该对扩展开放，对修改关闭。是针对我们封装，抽象出来的代码，而不是调用的逻辑代码。所以上面这样写并不算破坏开闭原则。

可以看到，组合的方式是就是抽象单一功能的函数，然后再组成复杂功能。这种方式既锻炼了你的抽象能力，也给维护带来巨大的方便。

但是上面的组合我只是用汉字来代替的，我们应该如何去实现这个组合呢。首先明确一点，函数式编程允许把函数本身作为参数传入另一个函数，还允许返回一个函数！

我们对上述第二种需求进行函数组合：把字符串大写之后，把每个字符拆开之后组装成一个数组，比如 ’aaa‘ 最终会变成 [A, A, A]

首先函数结构如下：

function twoFuntionCompose(fn1, fn2) {
    return function() {
        // code
    }
}

我们也可以使用如下代码组合两个函数：

var res = stringReverse(stringToUpper(str))

按照这个逻辑我们就可以写出 twoFuntonCompose 的实现了，就是

function twoFuntonCompose(fn1, fn2) {
    return function(arg) {
        return fn1(fn2(arg))
    }
}

同理我们也可以写出三个函数的组合函数，四个函数的组合函数，无非就是一直嵌套多层嘛，变成：

function multiFuntionCompose(fn1, fn2, .., fnn) {
    return function(arg) {
        return fnn(...(fn1(fn2(arg))))
    }
}

这种写法在实际代码中较为难理解，我们可以发现一些规律，无非就是把前一个函数的返回值作为后一个返回值的参数，当直接到最后一个函数的时候，就返回，所以可以这样写

function aCompose(...args) {
    let length = args.length
    let count = length - 1
    let result
    return function f1 (...arg1) {
        result = args[count].apply(this, arg1)
        if (count <= 0) {
          count = length - 1
          return result
        }
        count--
        return f1.call(null, result)
    }
}

当然对于 compose 的实现还有很多种方式，在这篇实现 compose 的五种思路中还给出了另外脑洞大开的实现方式

point-free

在函数式编程的世界中，有这样一种很流行的编程风格。这种风格被称为 tacit programming，也被称作为 point-free，point 表示的就是形参，意思大概就是没有形参的编程风格

// 这就是有参的，因为 word 这个形参
var snakeCase = word => word.toLowerCase().replace(/\s+/ig, '_');

// 这是 pointfree，没有任何形参
var snakeCase = compose(replace(/\s+/ig, '_'), toLowerCase);

有参的函数的目的是得到一个数据，而 pointfree 的函数的目的是得到另一个函数

point-free可以让我们把注意力集中在函数上，参数命名的麻烦肯定是省了，代码也更简洁优雅。需要注意的是，一个 pointfree 的函数可能是由众多非 pointfree 的函数组成的，也就是说底层的基础函数大都是有参的，pointfree 体现在用基础函数组合而成的高级函数上，这些高级函数往往可以作为我们的业务函数，通过组合不同的基础函数构成我们的复制的业务逻辑。

可以说 pointfree 使我们的编程看起来更美，更具有声明式，这种风格算是函数式编程里面的一种追求，一种标准，我们可以尽量的写成 pointfree，但是不要过度的使用，任何模式的过度使用都是不对的。

另外可以看到通过 compose 组合而成的基础函数都是只有一个参数的，但是往往我们的基础函数参数很可能不止一个，这个时候就会用到一个神奇的函数—>柯里化函数

柯里化

在维基百科里面是这么定义柯里化的：

在计算机科学，柯里化（英语：Currying)是把接受多个[参数]的[函数]变换成接受一个单一参数（最初函数的第一个参数）的函数，并且返回 ,接受余下的参数而且返回结果的新函数的技术。

f(x)和g(x)合成为f(g(x))，有一个隐藏的前提，就是f和g都只能接受一个参数。如果可以接受多个参数，比如f(x, y)和g(a, b, c)，函数合成就非常麻烦。

这时就需要函数柯里化了。所谓"柯里化"，就是把一个多参数的函数，转化为单参数函数。

// 柯里化之前
function add(x, y) {
  return x + y;
}
add(1, 2) // 3

// 柯里化之后
function addX(y) {
  return function (x) {
    return x + y;
  };
}
addX(2)(1) // 3

有了柯里化以后，我们就能做到，所有函数只接受一个参数。后文的内容除非另有说明，都默认函数只有一个参数，就是所要处理的那个值

来看一个具体的例子：你有一间面包店并且你想给你优惠的顾客打九折

function discount(price, discount) {
    return price * discount
}

当一位优惠的顾客买了一间价值$500的物品，你给他打折：

const price = discount(500, 0.10); // $50

从长远来看，我们会发现自己每天都在计算 10% 的折扣：

const price = discount(1500,0.10); // $150
const price = discount(2000,0.10); // $200
// ... 等等很多

我们可以将 discount 函数柯里化，这样我们就不用总是每次增加这 0.10 的折扣

// 这个就是一个柯里化函数，将本来两个参数的 discount ，转化为每次接收单个参数完成求职
function discountCurry(discount) {
    return (price) => {
        return price * discount;
    }
}
const tenPercentDiscount = discountCurry(0.1);

现在变成了以下操作

tenPercentDiscount(500); // $50

函子

函数不仅可以用于同一个范畴之中值的转换，还可以用于将一个范畴转成另一个范畴。这就涉及到了函子（Functor）

概念

函子是函数式编程里面最重要的数据类型，也是基本的运算单位和功能单位

它首先是一种范畴，也就是说，是一个容器，包含了值和变形关系。比较特殊的是，它的变形关系可以依次作用于每一个值，将当前容器变形成另一个容器

上图中，左侧的圆圈就是一个函子，表示人名的范畴。外部传入函数f，会转成右边表示早餐的范畴

代码实现

任何具有map方法的数据结构，都可以当作函子的实现

class Functor {
  constructor(val) { 
    this.val = val; 
  }

  map(f) {
    return new Functor(f(this.val));
  }
}

上面代码中，Functor是一个函子，它的map方法接受函数f作为参数，然后返回一个新的函子，里面包含的值是被f处理过的(f(this.val)

一般约定，函子的标志就是容器具有map方法。该方法将容器里面的每一个值，映射到另一个容器。

下面是一些用法的示例

(new Functor(2)).map(function (two) {
  return two + 2;
});
// Functor(4)

(new Functor('flamethrowers')).map(function(s) {
  return s.toUpperCase();
});
// Functor('FLAMETHROWERS')

(new Functor('bombs')).map(_.concat(' away')).map(_.prop('length'));
// Functor(10)

函数式编程里面的运算，都是通过函子完成，即运算不直接针对值，而是针对这个值的容器—-函子。函子本身具有对外接口（map方法），各种函数就是运算符，通过接口接入容器，引发容器里面的值的变形

of 方法

上面生成新的函子的时候，用了new命令。new命令是面向对象编程的标志。

函数式编程一般约定，函子有一个of方法，用来生成新的容器

面就用of方法替换掉new。

Functor.of = function(val) {
  return new Functor(val);
};

然后，前面的例子就可以改成下面这样。

Functor.of(2).map(function (two) {
  return two + 2;
});
// Functor(4)

Maybe 函子

函子接受各种函数，处理容器内部的值。这里就有一个问题，容器内部的值可能是一个空值（比如null），而外部函数未必有处理空值的机制，如果传入空值，很可能就会出错

Functor.of(null).map(function (s) {
  return s.toUpperCase();
});
// TypeError

上面代码中，函子里面的值是null，结果小写变成大写的时候就出错了。

Maybe 函子就是为了解决这一类问题而设计的。简单说，它的map方法里面设置了空值检查

class Maybe extends Functor {
  map(f) {
    return this.val ? Maybe.of(f(this.val)) : Maybe.of(null);
  }
}

有了 Maybe 函子，处理空值就不会出错了。

Maybe.of(null).map(function (s) {
  return s.toUpperCase();
});
// Maybe(null)

Either 函子

条件运算if...else是最常见的运算之一，函数式编程里面，使用 Either 函子表达。

Either 函子内部有两个值：左值（Left）和右值（Right）。右值是正常情况下使用的值，左值是右值不存在时使用的默认值

class Either extends Functor {
  constructor(left, right) {
    this.left = left;
    this.right = right;
  }

  map(f) {
    return this.right ? 
      Either.of(this.left, f(this.right)) :
      Either.of(f(this.left), this.right);
  }
}

Either.of = function (left, right) {
  return new Either(left, right);
};

下面是用法。

var addOne = function (x) {
  return x + 1;
};

Either.of(5, 6).map(addOne);
// Either(5, 7);

Either.of(1, null).map(addOne);
// Either(2, null);

如果右值有值，就使用右值，否则使用左值。通过这种方式，Either 函子表达了条件运算。

Either 函子的常见用途是提供默认值。下面是一个例子。

Either
.of({address: 'xxx'}, currentUser.address)
.map(updateField);

上面代码中，如果用户没有提供地址，Either 函子就会使用左值的默认地址。

Either 函子的另一个用途是代替try...catch，使用左值表示错误。

function parseJSON(json) {
  try {
    return Either.of(null, JSON.parse(json));
  } catch (e: Error) {
    return Either.of(e, null);
  }
}

上面代码中，左值为空，就表示没有出错，否则左值会包含一个错误对象e。一般来说，所有可能出错的运算，都可以返回一个 Either 函子

ap 函子

函子里面包含的值，完全可能是函数。我们可以想象这样一种情况，一个函子的值是数值，另一个函子的值是函数。

function addTwo(x) {
  return x + 2;
}

const A = Functor.of(2);
const B = Functor.of(addTwo)

上面代码中，函子A内部的值是2，函子B内部的值是函数addTwo。

有时，我们想让函子B内部的函数，可以使用函子A内部的值进行运算。这时就需要用到 ap 函子。

ap 是 applicative（应用）的缩写。凡是部署了ap方法的函子，就是 ap 函子

class Ap extends Functor {
  ap(F) {
    return Ap.of(this.val(F.val));
  }
}

注意，ap方法的参数不是函数，而是另一个函子。

因此，前面例子可以写成下面的形式。

Ap.of(addTwo).ap(Functor.of(2))
// Ap(4)

ap 函子的意义在于，对于那些多参数的函数，就可以从多个容器之中取值，实现函子的链式操作。

function add(x) {
  return function (y) {
    return x + y;
  };
}

Ap.of(add).ap(Maybe.of(2)).ap(Maybe.of(3));
// Ap(5)

上面代码中，函数add是柯里化以后的形式，一共需要两个参数。通过 ap 函子，我们就可以实现从两个容器之中取值。它还有另外一种写法

Ap.of(add(2)).ap(Maybe.of(3));

Monad 函子

函子是一个容器，可以包含任何值。函子之中再包含一个函子，也是完全合法的。但是，这样就会出现多层嵌套的函子

Maybe.of(
  Maybe.of(
    Maybe.of({name: 'Mulburry', number: 8402})
  )
)

上面这个函子，一共有三个Maybe嵌套。如果要取出内部的值，就要连续取三次this.val。这当然很不方便，因此就出现了 Monad 函子。

Monad 函子的作用是，总是返回一个单层的函子。它有一个flatMap方法，与map方法作用相同，唯一的区别是如果生成了一个嵌套函子，它会取出后者内部的值，保证返回的永远是一个单层的容器，不会出现嵌套的情况

class Monad extends Functor {
  join() {
    return this.val;
  }
  flatMap(f) {
    return this.map(f).join();
  }
}

上面代码中，如果函数f返回的是一个函子，那么this.map(f)就会生成一个嵌套的函子。所以，join方法保证了flatMap方法总是返回一个单层的函子。这意味着嵌套的函子会被铺平（flatten）

IO 操作

Monad 函子的重要应用，就是实现 I/O （输入输出）操作。

I/O 是不纯的操作，普通的函数式编程没法做，这时就需要把 IO 操作写成Monad函子，通过它来完成。

var fs = require('fs');

var readFile = function(filename) {
  return new IO(function() {
    return fs.readFileSync(filename, 'utf-8');
  });
};

var print = function(x) {
  return new IO(function() {
    console.log(x);
    return x;
  });
}

上面代码中，读取文件和打印本身都是不纯的操作，但是readFile和print却是纯函数，因为它们总是返回 IO 函子。

如果 IO 函子是一个Monad，具有flatMap方法，那么我们就可以像下面这样调用这两个函数。

readFile('./user.txt')
.flatMap(print

这就是神奇的地方，上面的代码完成了不纯的操作，但是因为flatMap返回的还是一个 IO 函子，所以这个表达式是纯的。我们通过一个纯的表达式，完成带有副作用的操作，这就是 Monad 的作用。

由于返回还是 IO 函子，所以可以实现链式操作。因此，在大多数库里面，flatMap方法被改名成chain。

var tail = function(x) {
  return new IO(function() {
    return x[x.length - 1];
  });
}

readFile('./user.txt')
.flatMap(tail)
.flatMap(print)

// 等同于
readFile('./user.txt')
.chain(tail)
.chain(print)