函数式编程

衍生

函数式编程

共 4,596 字，需阅读 11 分钟

2017/04/12 下午

4,363 次阅读

函数式编程最早起源于数学中的范畴论，和面向对象编程、命令式编程并列为三大编程范式，也就是如何编写程序的方法论。它属于"结构化编程"的一种，主要思想是把运算过程尽量写成一系列嵌套的函数调用。

#范畴论的核心概念：

把世界上一切存在关系的元素理解为一个范畴，有点像分子结构，范畴内部的各原子之间的关系就是函数，所以大概来说，范畴内部包含：原子 + 函数（原子的关系映射）。

这么说就好理解了，我们可以理解为我们真实的编程生产中所使用的一个个量称之为原子，对原子进行计算的函数即为函数。

像这样：

          1
2
3
4
5
6
7
8
9
          // 命令式编程
const c = 1 + 2
console.log(c)

// 函数式编程
// 把add理解为是一个"范畴", a、b为范畴中的原子，内部的"a + b"即为函数本身，即a和b的映射关系
// 整个计算过程未产生变量，对外部无依赖、无改变、未泄露任何变量
const add = (a, b) => a + b
console.log(add(1, 2))

#函数式编程的主要特征：

一等公民
计算过程完全函数化
无副作用，有输入，有输出
每个函数只有一个参数（柯里化）
支持闭包和高阶函数
使用递归实现流程控制

#合成

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

示例：

          1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
          // 两个函数
const add = a => a + a
const multiply = c => c * c
multiply(add(1))
// 4

// 合成后
var compose = (a, b) => {
    return c => {
        return a(b(c))
    }
}

// 简写
var compose = (a, b) => c => a(b(c))

// continue
const add = n => n + n
const multiply = n => n * n

compose(multiply, add)(2)
// 16

#柯里化

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

示例：

          1
2
3
4
5
6
          const add = (a, b) => a + b
add(1, 2)

// 柯里化之后
const add = a => b => a + b
add(1)(2)

有了柯里化以后，我们就能做到，所有函数只接受一个参数，其实也是一种变相的封装。

如下实例：

          1
2
3
4
5
6
7
          // 如上文中，如果a量为固定值1，则我们可以封装为
const addOne = b => add(1, b)

addOne(2)

// 等介于
add(1)(2)

#尾调用

简单一句话说就是：

函数内部的最后一步操作是执行另一个函数

如下代码：

          1
2
3
          function a(x) {
  return b(x)
}

函数a的最后一步操作是执行函数b，此函数即为尾调用。

以下两种情况不属于尾调用：

          1
2
3
4
5
6
7
8
9
10
          // 情况一
function f(x) {
  let y = g(x)
  return y
}

// 情况二
function f(x) {
  return g(x) + 1
}

上面两个函数f在内部执行完g函数后依然有其他操作，即便第二个函数的操作是写在同一行内的，也不算尾调用。

          1
2
3
4
5
6
          function f(x) {
  if (x > 0) {
    return m(x)
  }
  return n(x)
}

上面代码中函数m和n均为尾调用，他们都属于函数f的最后一步操作。

#尾调用优化

尾调用之所以和其他调用不同，是因为，函数在执行时，在其内部会维护一个调用堆栈，保存调用位置和内部变量等信息。

如果在函数 A 的内部调用函数 B，那么在 A 的调用记录上方，还会形成一个 B 的调用记录。等到 B 运行结束，将结果返回到 A，B 的调用记录才会消失。如果函数 B 内部还调用函数 C，那就还有一个 C 的调用记录栈，以此类推。所有的调用记录，就形成一个"调用栈"（call stack）。

尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用记录，因为调用位置、内部变量等信息都不会再用到了，只要直接用内层函数的调用记录，取代外层函数的调用记录就可以了。

          1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
          // 下函数在内存中执行时
function f() {
  let m = 1
  let n = 2
  return g(m + n)
}
f()

// 等同于
function f() {
  return g(3)
}
f()

// 等同于
g(3)

上面代码中，如果函数g不是尾调用，函数f就需要保存内部变量m和n的值、g的调用位置等信息，一直等到f函数完全执行完毕才释放。但由于调用g之后，函数f就结束了，所以执行到最后一步，完全可以删除 f() 的调用记录，只保留 g(3) 的调用记录。这就叫做"尾调用优化"（Tail call optimization），即只保留内层函数的调用记录。如果所有函数都是尾调用，那么完全可以做到每次执行时，调用记录只有一项，这将大大节省内存。这就是"尾调用优化"的意义。

#尾递归

函数调用自身，称为递归。如果尾调用自身，就称为尾递归。

一个简单的递归函数：

          1
2
3
4
5
6
          // 当然这只是一个示例函数，实际上是死循环，浏览器会提示栈溢出
const a = n => {
    return a(n++)
}

a(1)

递归非常耗费内存，因为需要同时保存成千上百个调用记录，很容易发生 “栈溢出“ 错误（stack overflow）。但对于尾递归来说，由于只存在一个调用记录，所以永远不会发生 “栈溢出” 错误。

          1
2
3
4
5
6
          function factorial(n) {
  if (n === 1) return 1
  return n * factorial(n - 1)
}

factorial(5) // 120

上面面代码是一个阶乘函数，计算n的阶乘，最多需要保存n个调用记录，复杂度 O(n) 。如果改写成尾递归，只保留一个调用记录，复杂度 O(1) 。

          1
2
3
4
5
6
          function factorial(n, total) {
  if (n === 1) return total
  return factorial(n - 1, n * total)
}

factorial(5, 1) // 120

由此可见，"尾调用优化"对递归操作意义重大，所以一些函数式编程语言将其写入了语言规格。 ES6也是如此，第一次明确规定，所有 ECMAScript 的实现，都必须部署"尾调用优化"。这就是说，在 ES6 中，只要使用尾递归，就不会发生栈溢出，相对节省内存。

#尾递归优化

尾递归的实现，往往需要改写递归函数，确保最后一步只调用自身。做到这一点的方法，就是把所有用到的内部变量改写成函数的参数。比如上面的例子，阶乘函数 factorial 需要用到一个中间变量 total ，那就把这个中间变量改写成函数的参数。这样做的缺点就是不太直观，第一眼很难看出来，为什么计算5的阶乘，需要传入两个参数5和1？三个方法可以解决这个问题。

#在尾递归函数之外，再提供一个正常形式的函数。

          1
2
3
4
5
6
7
8
9
10
          function tailFactorial(n, total) {
  if (n === 1) return total
  return tailFactorial(n - 1, n * total)
}

function factorial(n) {
  return tailFactorial(n, 1)
}

factorial(5) // 120

上面代码通过一个正常形式的阶乘函数 factorial ，调用尾递归函数 tailFactorial ，看起来就正常多了。

#柯里化

          1
2
3
4
5
6
7
8
9
10
11
12
13
14
          function currying(fn, n) {
  return function (m) {
    return fn.call(this, m, n)
  }
}

function tailFactorial(n, total) {
  if (n === 1) return total
  return tailFactorial(n - 1, n * total)
}

const factorial = currying(tailFactorial, 1)

factorial(5) // 120

上面代码通过柯里化，将尾递归函数 tailFactorial 变为只接受1个参数的 factorial 。

#ES6的函数默认值

          1
2
3
4
5
6
          function factorial(n, total = 1) {
  if (n === 1) return total
  return factorial(n - 1, n * total)
}

factorial(5) // 120