我所了解的函数式编程

前言

我从去年年初开始接触函数式编程，看了很多和函数式编程相关的书和博客，如JS函数式编程、 Haskell趣学指南、Real World Haskell，接触到很多函数式语言，如 Haskell, Elixir, Lisp系列等等。随着函数式代码写得越来越多，我越来越喜欢函数式的编程方式，渐渐成为了一名函数式编程的爱好者。本文是我学习函数式编程以来的一些总结。

简介

函数式编程是一种编程范式，主要是利用函数把运算过程封装起来，通过组合各种函数来计算结果。举个简单的例子，假设我们要把字符串 functional programming is great 变成每个单词首字母大写，我们可以这样实现：

1
2
3
4
5

var string = 'functional programming is great';
var result = string
  .split(' ')
  .map(v => v.slice(0, 1).toUpperCase() + v.slice(1))
  .join(' ');

或许对很多人来说这并没有什么特别之处，但这里已经是利用了函数式编程的核心思想： 通过函数对数据进行转换。

上面的例子先用 split 把字符串转换数组，然后再通过 map 把各元素的首字母转换成大写，最后通过 join 把数组转换成字符串。 整个过程就是 join(map(split(str)))，我们只是利用面向对象编程的接口来把这个转换过程写成上面那样。

细心的同学可以发现，其实这个过程和 Unix 的管道操作非常相似，管道操作通过 | 来把上一个程序的输出重定向到下一个程序的输入，如：cat log.txt | grep mystring。这种方式非常符合我们对计算机的理解：给定特定输入，返回计算结果。函数式编程正好是这种方式的一种「实现」。

函数式编程与面向对象编程

我们知道，函数式编程是一种编程范式，它经常与面向对象编程作比较。 经常编写面向对象程序的人们会发现，面向对象是让操作围绕数据，我们会定义一个类的属性，然后定义一些方法，这些方法会围绕这些属性来进行操作。如：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class ObjectManager {
  constructor() {
    this._objects = [];
  }

  add(object) {
    this._objects.push(obj);
    return this;
  }

  get(index) {
    return this._objects[index];
  }
}

var objects = new ObjectManager();
objects.add({ key: 1 }).add({ key: 2 }).add({ key: 3 });
objects.get(2); // { key: 3 }

可以看见，上面代码中的 add、get 方法其实是围绕 this._objects 这个数据来进行操作。如果是函数式编程的话，更多的是让数据围绕操作。我们会定义一系列函数，然后让数据「流」过这些函数，最后输出结果。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// basic implementation
function add(array, object) {
  return array.concat(object);
}

function get(array, index) {
  return array[index];
}

var objects = add(add(add([], { key: 1 }), { key: 2 }), { key: 3});
get(objects, 2); // { key: 3 }

这就是用函数式编程改写过的代码，尽管非常难以阅读，一点也不符合函数式编程简洁的特点，但它确实代表了函数式编程的基本思想：通过函数对数据进行转换。我们可以用以下方式来改写：

1
2
3
4
5
6

// improvement
Array.prototype.get = function(index) { return this[index]; };
[].concat({ key: 1 }) // [{ key: 1 }]
  .concat({ key: 2 }) // [{ key: 1 }, { key: 2 }]
  .concat({ key: 3 }) // [{ key: 1 }, { key: 2 }, { key: 3 }]
  .get(2); // { key: 3 }

这个版本才像函数式的写法，它有两个要点：

1. 用 get 代替直接通过 [index] 来访问数据，它和面向对象版本的 get 非常相似，是为了避免直接访问数组。
2. 利用 concat 代替 push 拼接数组，这和面向对象版本的 add 有本质的区别。尽管大家看起来都是链式调用，但面向对象版本是通过返回 this 来实现链式调用，而函数式版本是通过返回一个新数组的方式来实现链式调用的。这点可以很好的体现出 操作围绕数据 和 数据围绕操作 的区别。

基本特点

函数式编程的基本特点有两个：

• 通过函数来对数据进行转换
• 通过串联多个函数来求结果

我们来看看下面这个例子：假设有三个函数，f(x) 可以把 x 转换成 a，g(a) 可以把 a 转换成 b，h(b) 可以把 b 转换成 c，即：

1
2
3

f(x) -> a
g(a) -> b
h(b) -> c

那么怎么把 x 转换成 c ？相信这难不倒大家，我们只需要通过如下式子就可以实现：

1

h( g( f(x) ) )

上面的式子可以解读成把 f(x) 的结果传给 g 函数(即 g(f(x))), 再把结果传给 h 函数，即是上式子的意思。

由于串联函数在函数式编程中实在太常见了，各个函数式语言都有自己的表达方式。下面我们来看看各个函数式语言是怎么表达这个式子的：

Lisp 家族

1

(h (g (f x)))

Haskell

1

let result = h . g . f x

Elixir:

1

result = x |> f |> g |> h

函数式编程除了提倡串联函数之外，还有很多有趣的特性，接下来我们来看看函数式编程中一些常见的特性。

常见特性

很多时候你去查阅函数式编程的相关资料，你都会看到下面这些术语：

无副作用

指调用函数时不会修改外部状态，即一个函数调用 n 次后依然返回同样的结果。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

var a = 1;
// 含有副作用，它修改了外部变量 a
// 多次调用结果不一样
function test1() {
  a++
  return a;
}

// 无副作用，没有修改外部状态
// 多次调用结果一样
function test2(a) {
  return a + 1;
}

透明引用

指一个函数只会用到传递给它的变量以及自己内部创建的变量，不会使用到其他变量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

var a = 1;
var b = 2;
// 函数内部使用的变量并不属于它的作用域
function test1() {
  return a + b;
}
// 函数内部使用的变量是显式传递进去的
function test2(a, b) {
  return a + b;
}

不可变变量

指的是一个变量一旦创建后，就不能再进行修改，任何修改都会生成一个新的变量。使用不可变变量最大的好处是线程安全。多个线程可以同时访问同一个不可变变量，让并行变得更容易实现。 由于 JavaScript 原生不支持不可变变量，需要通过第三方库来实现。 (如 Immutable.js，Mori 等等)

1
2
3
4

var obj = Immutable({ a: 1 });
var obj2 = obj.set('a', 2);
console.log(obj);  // Immutable({ a: 1 })
console.log(obj2); // Immutable({ a: 2 })

函数是一等公民

指的是函数和其他数据类型一样，可以赋值给变量，可以作为参数传递，可以作为返回值，可以作为数组中的函数，可以是对象中的一个值等等。下面这些术语都是围绕这一特性的应用：

• 高阶函数 (Higher order function) 如果一个函数接受函数作为参数，或者返回值为函数，那么该函数就是高阶函数。

  1 2 3 4 5 6 7 8 9 10 11

  // 接受函数的函数 function test1(callback) { callback() } // 返回函数的函数 function test2() { return function() { console.log(1); } }

• 闭包 (Closure) 如果一个函数引用了自由变量，那么该函数就是一个闭包。何谓自由变量？自由变量是指不属于该函数作用域的变量(所有全局变量都是自由变量，严格来说引用了全局变量的函数都是闭包，但这种闭包并没有什么用，通常情况下我们说的闭包是指函数内部的函数)。

  1 2 3 4 5 6 7 8 9 10 11

  // test1 是普通函数 function test1() { var a = 1; // test2 是内部函数 // 它引用了 test1 作用域中的变量 a // 因此它是一个闭包 return function test2() { return a + 1; } }

• 函数组合 (Composition) 前面提到过，函数式编程的一个特点是通过串联函数来求值。然而，随着串联函数数量的增多，代码的可读性就会不断下降。函数组合就是用来解决这个问题的方法。假设有一个 compose 函数，它可以接受多个函数作为参数，然后返回一个新的函数。当我们为这个新函数传递参数时，该参数就会「流」过其中的函数，最后返回结果。

  1 2 3 4 5 6 7

  // 组合 f, g 函数, 从左到右求值 var composed = compose(f,g); composed(x) = g(f(x)); // 组合 f, g, h 函数, 从右到左求职 var composed = composeRight(h, g, f); composed(x) = h(g(f(x)));

• 柯里化 (Currying) 柯里化是对函数的封装，当调用函数时传递参数数量不足时，会返回一个新的函数，直到参数数量足够时才进行求值。

  1 2 3

  // 假设函数 f 接受三个参数 f = curry(f); f(x,y,z) = f(x,y)(z) = f(x)(y,z) = f(x)(y)(z);

• 模式匹配 (Pattern matching) 模式匹配是指可以为一个函数定义多个版本，通过传入不同参数来调用对应的函数。形式上有点像「方法重载」，但方法重载是通过传入*参数类型*不同来区分的，模式匹配没有这个限制。利用模式匹配，我们可以去掉函数中的「分支」(最常见的是 if)，写出非常简洁的代码。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

  // 普通版本，需要在函数内部对参数进行判断 function fib(x) { if (x === 0) return 0; if (x === 1) return 1; return fib(x-1) + fib(x-2); } // 模式匹配版本。 // 由于 JavaScript 不支持模式匹配， // 下面代码只是作演示用途 var fib = (0) => 0; var fib = (1) => 1; var fib = (x) => fib(x-1) + fib(x-2); // 调用 fib(10);

可以看到，如果能在语言层面支持模式匹配，那么在函数定义中就可以省略很多「分支」。 上面的例子可能不够明显，请想象一下在编写 Restful API 时，我们需要解析请求中的参数，然后返回对应内容。传统方式下，我们需要写很多 if 语句来进行判断，如果该 API 支持非常多参数，那么该函数就会有非常多的 if 语句，这种函数在维护的时候会是一个噩梦。 如果支持模式匹配，那么我们只需要定义多个函数即可。

常见函数

接下来来看看几个常见的函数。

• map 映射函数，通过定义函数来实现数据的映射，简单来说就是令一个数组变换成另一个数组，如要将 [1,2,3] 变换成 [4,5,6]，我们只需要定义一个 x+3 的变换即可，即：

  1	[1,2,3].map(x => x+3); // 返回 [4, 5, 6]

map 函数的实现非常简单，只需要遍历数组，然后对每个元素调用一次变换函数，最后返回结果即可。

1
2
3
4
5
6
7
8

function map(array, fn) {
  var result = [];
  for (var i = 0; i < array.length; i++) {
    var transformed = fn(array[i], i);
    result.push(transformed);
  }
  return result;
}

• reduce (有些语言里面叫 fold) 归纳函数，给定一个初始值，再定义一个函数来归纳数组，最后返回一个值，简单来说就是令一个数组变成一个值。如对 [1,2,3] 求和，相当于给定初始值 0，然后用它去「流」过数组，最后生成结果，翻译成 JavaScript 代码就是：

  1	[1, 2, 3].reduce((prev, next) => prev + next, 0); // 返回 6

prev 是累加值，函数每次返回都会更新该值，而 next 则是当前元素。整个计算过程如下：

1
2
3
4
5
6
7
8

第一次运算：
prev = 0(初始值), next = 1
第二次运算：
prev = 1(0 + 1), next = 2
第三次运算：
prev = 3(1 + 2), next = 3
返回值：
6 (3 + 3)

reduce 函数的实现其实很简单，只需要更新不断更新累加值即可：

1
2
3
4
5
6

function reduce(array, acc, fn) {
  for (var i = 0; i < array.length; i++) {
    acc = fn(acc, array[i]);
  }
  return acc;
}

• filter 过滤函数，通过定义一个函数来筛选元素。如要把数组 [1,2,3] 中的奇数筛选出来，我们只需要把满足条件 x % 2 !== 0 的元素找出来即可。

  1	[1, 2, 3].filter(x => x % 2 !== 0); // 返回 [1, 3]

我们还可以利用 filter 把数组中的 undefined 过滤掉：

1

[1, 2, undefined, 3, undefined, 4].filter(x => x); // 返回 [1, 2, 3, 4]

通过上面两个例子可以发现，只要一个元素在 filter 的过滤函数中返回真值，即可保留该值。我们可以根据这点来实现 filter 函数：

1
2
3
4
5
6
7
8
9

function filter(array, fn) {
  var result = [];
  for (var i = 0; i < array.length; i++) {
    if (fn(array[i], i)) {
      result.push(array[i]);
    }
  }
  return result;
}

最后我们来看看一个混合使用这些函数的例子： 假设我要从 http://example.com?type=1&keyword=hello&test= 中提取查询字符串，过滤掉无效键值对，最后返回一个 Object 形式的结果，大概会有以下步骤：

1. http://example.com?type=1&keyword=hello&test->
2. type=1&keyword=hello&test ->
3. [ 'type=1', 'keyword=hello', 'test' ] ->
4. [ [ 'type', '1' ], [ 'keyword', 'hello' ], ['test'] ] ->
5. [ [ 'type', '1' ], [ 'keyword', 'hello' ] ] ->
6. { type: 1, keyword: 'hello' }

这些步骤翻译成函数式代码即是：

1
2
3
4
5
6
7
8

url
  .split('?')[1]
  .split('&')
  .map(v => v.split('='))
  .filter(v => v.length === 2)
  .reduce((prev, next) =>
    Object.assign(prev, { [next[0]]: next[1] }),
  {});

列表

从上面的代码中我们可以发现，列表类的数据结构是非常常用的，函数式语言通常都会对这类数据结构进行优化。列表在函数式语言里面常常以下面这种形式存在：

[ head | tail ]

即一个列表可以看成是由头元素和尾部来组成，如:

1
2
3
4
5
6
7
8

// 普通列表
[1,2,3]
// [1, 2, 3] 可以看成是 1 和 [2, 3] 的组合
[1 | [2,3]]
// [2, 3] 可以看成是 2 和 [3] 的组合
[1 | [2 | [3]]]
// [3] 可以看成是 3 和 [] 的组合
[1 | [2 | [3 | []]]]

我们可以定义函数来获取列表的头部和尾部：

1
2

head([1,2,3]) -> 1
tail([1,2,3]) -> [2,3]

那么把列表定义成这样的形式到底有什么好处呢？答案就是：方便递归。

递归

递归在函数式编程中是非常重要的概念，它可以通过调用函数的形式来模拟循环。如我们要对 [1,2,3,4,5] 求和，最常见的做法是写 for 循环，然后一个一个加起来。而用递归的话则是定义一个相加函数，然后不断对其进行调用。

1
2
3
4
5
6
7
8
9

// JavaScript
function sum(list) {
  if (list.length === 0) return 0;

  var h = head(list);
  var t = tail(list);

  return h + sum(t);
}

上面的代码虽然是递归，但由于 JavaScript 不支持模式匹配，因此写起来非常啰嗦，我们来看看支持模式匹配的代码：

1
2
3

-- Haskell
sum [] = 0
sum (x:xs) = x + sum(xs)

Haskell 的实现只需要两行，它做的事情和上面的 JavaScript 一样，都是递归求和。上面这种形式的递归计算过程如下：

1
2
3
4
5
6
7

1 + sum([2,3,4,5])
1 + 2 + sum([3,4,5])
1 + 2 + 3 + sum([4,5])
1 + 2 + 3 + 4 + sum([5])
1 + 2 + 3 + 4 + 5 + sum([])
1 + 2 + 3 + 4 + 5 + 0
15

这种形式计算小列表没有什么问题，但对于大列表来说问题就非常大了，因为上述代码并不是尾递归(不知道尾递归的同学可以去看阮一峰老师的 尾调用优化)，在大列表的情况下很容易会爆内存。因此，更好的做法是把上述代码改写成尾递归的版本：

1
2
3
4
5
6
7
8
9

// JavaScript
function sum(list, acc) {
  if (list.length === 0) return acc;

  var h = head(list);
  var t = tail(list);

  return sum(t, acc + h);
}

1
2
3

-- Haskell
sum ([], acc) = acc
sum (x:xs, acc) = sum(xs, x + acc)

整个计算过程如下：

1
2
3
4
5
6
7

sum([1,2,3,4,5], 0)
sum([2,3,4,5], 1 + 0)
sum([3,4,5], 2 + 1 + 0)
sum([4,5], 3 + 2 + 1 + 0)
sum([5], 4 + 3 + 2 + 1 + 0)
sum([], 5 + 4 + 3 + 2 + 1 + 0)
13

最后我们来谈谈函数式编程的优缺点：

优点

• 由于函数式代码是声明式的，因此它非常容易阅读。
• 在不可变变量的帮助下，函数式代码不须考虑死锁，非常适合并行执行。
• 函数式编程强调纯函数，无副作用，不涉及状态改变，因此测试和调试非常方便。

缺点

• 性能比命令式编程差。
• 函数式编程用类似管道的方式来处理数据，因此不适合处理可变状态。
• 函数式编程不适合做 IO 操作，也不适合写 GUI。

参考资料

• 什么是函数式编程思维？
• 函数式编程初探
• 声明式编程和命令式编程的比较