函数式编程指南

1. 什么是函数式编程

1.1

当考虑应用设计时，我们应该问问自己是否遵从了以下的设计原则
• 可扩展性一一我是否需要不断地重构代码来支持额外的功能?
• 易模块化一一如果我更改了一个文件，另一个文件会不会受到影响?
• 可重用性一一是否有很多重复的代码?
• 可测性一一给这些函数添加单元测试是否让我纠结?
• 易推理性一一我写的代码是否非结构化严重并难以推理?

1.2

函数式编程需要你在思考解决问题的思路时有所变化。其实使用函数来获得结果并不重要，函数式编程的目标是使用函数来抽象作用在数据之上的控制流与操作，从而在系统中消除副作用并减少对状态的改变。
来更简洁的描述一下：函数式编程是指为创建不可变的程序，通过消除外部可见的副作用，来对纯函数的声明式的求值过程。

1.3 我们首先来了解一下它所基于的基本概念

• 声明式编程：将程序的描述与求值分离开来。它关注于如何用各种表达式来描述程序逻辑，而不一定要指明其控制流或状态的变化
• 纯函数：

1. 仅取决于提供的输入，而不依赖于任何在函数求值期间或调用间隔时可能变化
   的隐藏状态和外部状态 。
2. 不会造成超出其作用域的变化，例如修改全局对象或引用传递的参数 。
   • 引用透明：相同的输入总是产生相同的输出
   • 不可变性

1.4 优点

• 促使将任务分解成简单的函数：1. 单一职责 2. 组合
• 使用流式的调用链来处理数据：函数链是一种惰性计算程序，这意味着当需要时才会执行。有效地模拟了其他函数式语言的按需调用的行为。
• 通过响应式范式降低事件驱动代码的复杂性: observable

2. 高阶函数

鉴于函数的行为与普通对象类似，其理所当然地可以作为其他函数的参数进行传递，或是由其他函数返回。这些函数则称为高阶函数。
因为函数的一等性和高阶性， JavaScript函数具有值的行为，也就是说，函数就是一个基于输人的且尚未求值的不可变的值。

3. 函数调用的方法

• 作为全局函数一一 其中 this 的引用可以是 global 对象或是 undefined (在严格模式中)
• 作为方法 一一其中 this 的引用是方法的所有者，这是Javascript 的面向对象特性的重要部分
• 作为构造函数与 new 一起使用 一一 这种方式会返回新创建对象的引用

4. 闭包

4.1 概念

闭包是一种能够在函数声明过程中将环境信息与所属函数绑定在一起的数据结构。 它是基于函数声明的文本位置的，因此也被称为围绕函数定义的静态作用域或词法作用域 。闭包能够使函数访问其环境状态，使得代码更清晰可读。你很快就会看到，闭包不仅应用于函数式编程的高阶函数中，也可用于事件处理和回调、模拟私有成员变量，还能用于弥补一些 JavaScript 的不足。

支配函数闭包行为的规则与 JavaScript 的作用域规则密切相关。作用域能够将一组变量绑定，并定义变量定义的代码段。从本质上讲，闭包就是函数继承而来的作用域， 这类似于对象方法是如何访问其继承的实例变量的，它们都具有其父类型的引用。在内嵌函数中能够很清楚地看到闭包。

函数的闭包包括以下内容：
• 函数的所有参数
• 外部作用域的所有变量(当然也包括所有的全局变量)

4.2 函数作用域

1. 首先检查变量的函数作用域。
2. 如果不是在局部作用域内，那么逐层向外检查各词法作用域，搜索该变量的引用，直到全局作用域。
3. 如果无法找到变量引用，那么 JavaScript 将返回 undefined。

4.3 实际应用

1. 模拟私有变量。
   闭包可以用来管理的全局命名空间，以免在全局范围内共享数据。一些库和模块还会使用闭包来隐藏整个模块的私有方法和数据。这被称为模块模式 ，它采用了立即调用函数表达式(IIFE)

   
   image.png

2. 异步服务端调用 。

3. 创建人工作作用域变量 。

5. 函数链

5.1 链接方法

方法链是一种能够在一个语句中调用多个方法的面向对象编程模式。当这些方法属于同一个对象时，方法链又称为方法级联, demo如下：

'Functional Programming'.substring(0, 10).toLowerCase() + ' is fun';
// 函数式风格
concat(toLowerCase(substring('Functional Programming', 1, 10))), 'is fun' 

5.2 函数链

函数式编程则采用了不同的方式。它不是通过创建一个全新的数据结构类型来满足特定的需求，而是使用如数组这样的普通类型，并施加在一套粗粒度的高阶操作之上，这些操作是底层数据形态所不可见的。这些操作会作如下设计。
• 接收函数作为参数，以便能够注入解决特定任务的特定行为。
• 代替充斥着临时变量与副作用的传统循环结构，从而减少所要维护以及可能出错的代码。

5.3 lambda 表达式(箭头函数)

lambda 表达式适用于函数式的函数定义，因为它总是需要返回一个值。对于单行表达式，其返回值就是函数体的值。另一个值得注意的是一等函数与 lambda 表达式之间的关系。函数名代表的不是一个具体的值，而是一种(惰性计算的)可获取其值的描述。换句话说，函数名指向的是代表着如何计算该数据的箭头函数。这就是在函数式编程中可以将函数作为数值使用的原因。

5.4 Lodash惰性计算函数链

image.png
_.chain 函数可以添加一个输入对象的状态，从而能够将这些输入转换为所需输出的操作链接在一起。与简单地将数组包裹在(...)对象中不同，其强大之处在于可以链接序列中的任何函数。尽管这是一个复杂的程序，但仍然可以避免创建任何变量 ，并且有效地消除所有循环。
使用 _.chain 的另一个好处是可以创建具有惰性计算能力的复杂程序，在调用 value () 前，并不会真正地执行任何操作。这可能会对程序产生巨大的影响，因为在不需要其结果的情况下，可以跳过运行所有函数

能够惰性地定义程序的管道不止有可读性这一个好处。由于以惰性计算方式编写的程序会在运行前定义好，因此可以使用数据结构重用或者方法融合等技术对其进行优化。这些优化不会减少执行函数本身所需的时间，但有助于消除不必要的调用

6. 递归

递归是一种旨在通过将问题分解成较小的自相似问题来解决问题本身的技术，将这些小的自相似问题结合在一起，就可以得到最终的解决方案。递归函数包含以下两个主要部分。
• 基例(也称为终止条件) ：能够令递归函数计算出具体结果的一组输入，而不必再重复下去
• 递归条件：处理函数调用自身的一组输入(必须小于原始值)。如果输入不变小，那么递归就会无限期地运行，直至程序崩溃。随着函数的递归，输入会无条件地变小，最终到达触发基例的条件，以一个值作为递归过程的终止。

事实上，纯函数式语言甚至没有标准的循环结构，如 do、 for 和 while，因为所有循环都是递归完成的 。 递归使代码更易理解，因为它是以多次在较小的输人上重复相同的操作为基础的

6.1 尾调用优化

image.png

这个版本的实现将递归调用作为函数体中最后的步骤，也就是尾部位置。

6.2 递归定义的数据结构

递归算法执行整个树的先序遍历，从根开始并且下降到所有子节点。由于其自相似性，从根节点遍历树和从任何节点遍历子树是完 全一样的，这就是递归定义。

树的先序遍历按照以下步骤执行，从根节点开始。

1. 显示根元素的数据部分。
2. 通过递归地调用先序函数来遍历左子树。

3. 以相同的方式遍历右子树。

   
   递归的先序遍历，从根节点开始，一直向左下降，然后再向右移动

6.3 递归的弱点

如果你见过错误 Range Error : Maximum Call Stack Exceeded or too much recursion，就会知道递归有问题了。通过下面这个简单的脚本，可以测试浏览器函数堆栈大概的大小:

function increment (i) { 
  console.log(i); 
  increment(++i);
}
increment(i);

不同的浏览器的堆找错误会有不同:例如在某台计算机上， Chrome 会在 17500 次递归后触发异常，而 Firefox 的会递归大约 213000 次。不要以这些数值作为递归函数的上界! 这些数字只是为了说明递归是有限制的。代码预设应该要远远低于这些阀值，否则递归肯定是有问题的。
遍历这种异常巨大的数组的另一种方式就是利用高阶函数，如 map、 filter 以及 reduce。使用这些函数不会产生嵌套的函数调用，因为堆栈在每次迭代循环后都能得到回收。
虽然柯里化和递归导致更多的内存占用，但是鉴于它们带来的灵活性和复用性以及递归解决方案固有的正确性 ，又感觉这些额外的内存花费是值得的。
另外我们可以通过惰性求值来推迟函数执行

6.4 尾递归调用优化

当使用尾递归时，编译器有可能帮助你做尾 部调用优化(TCO)

image.png

TCO 也称为尾部调用消除 ，是 ES6 添加的编译器增强功能。 同时，在最后的位置调用别的函数也可以优化(虽然通常是本身)，该调用位置称为尾部位置 (尾递归因此而得名)。
这为什么算是一种优化?函数的最后一件事情如果是递归的函数调用，那么运行时会认为不必要保持当前的栈帧，因为所有工作已经完成，完全可以抛弃当前帧。在大多数情况下，只有将函数的上下文状态作为参数传递给下一个函数调用(正如在递归阶乘函数处看到的) ，才能使递归调用不需要依赖当前帧。通过这种方式，递归每次都会创建一个新的帧，回收旧的帧，而不是将新的帧叠在旧的上。因为 factorial 是尾递归 的形式，所以 factorial(4)的调用会从典型的递归金字塔:

factorial(4)
  4 * factorial(4)
    4 * 3 * factorial(2)
      4 * 3 * 2 * factorial(1)
        4 * 3 * 2 * 1 * factorial(0)
          4 * 3 * 2 * 1 * 1
        4 * 3 * 2 * 1
       4 * 3 * 2
    4 * 6
return 24

相对于如下上下文堆栈

factorial(4)
  factorial(3, 4)
  factorial(2, 12)
  factorial(1, 24)
  factorial(0, 24)
  return 24
return 24

尾递归 factorial(4)求值的详细视图。函数只使用了一帧。TCO 负责抛弃当前帧，为新的帧让路，就像 factorial 在循环中求值一样

6.5 将非尾递归转为尾递归

const factorial = (n) => (n===1)? 1 : (n * factorial(n - 1));

递归调用并没有发生在尾部，因为最后返回的表达式是 n * factorial (n - 1)。 切记，最后一个步骤一定要是递归，这样才会在运行时 TCO 将 factorial 转换成一 个循环。改成尾递归只需要两步。

1. 将当前乘法结果当作参数传人递归函数。
2. 使用 ES6 的默认参数给定一个默认值(也可以部分地应用它们，但默认参数会让代码更整洁 )。

const factorial = (n, current = 1) => (n === 1) ? current : factorial(n - 1, n * current) ,

这个阶乘函数运行起来眼标准循环没什么区别，没有额外创建堆栈帧，同时仍保留了它原本的数学声明的感觉。之所以能够做这种转换，是因为尾递归函数跟循环有着共同的特点

标准循环(左)及其等效的尾递归函数之间的相似之处。在这两个代码示例中，读者可以很容易地找到基例、事后操作、累计参数和结果

function sum (arr) {
  if (_.isEmpty(arr)) {
    return 0;
  }
  return _.first(arr) + sum(_.rest(arr));
}
// 转为尾调用
function sum(arr, ace = 0) { 
  if(_.isEmpty(arr)) {
    return 0;
  }
  return sum(rest(arr), ace+_.first(arr));
}

尾递归带来递归循环的性能接近于 for 循环。所以对于有尾递归优化的语言，比如 ES6，就可以在保持算法的正确性和 mutation 的控制，同时还能保持不会拖累性能。不过尾调用也不仅限于尾递归 。 也可以是调用另一个函数，这种情况在 JavaScript 代码中也很常见。不过要注意的是，这是个新的 JavaScript标准，即便 ES4就开始起草，很多浏览器也没有广泛实现。

还有一种解决方式是使用 trampolining。 trampolining 可以用迭代的方式模拟尾递归，所以可以非常理想、容易地控制 JavaScript 的堆栈。
trampolining是一个接受函数的函数，它会多次调用函数，直到满足一定的条件。一个可反弹或者重复的函数被封装在 thunk 结构中。 thunk 只不过是多了 一层函数包裹。在函数式 JavaScript背景下，可以用 thunk及简单的匿名函数包裹期望惰性求值的值。
要检查 TCO 和其他 ES6 特性的兼容性，可以登录: https://kangax.github.io/compat table/es6/。

7. 函数的管道化

• 方法链接(紧耦合，有限的表现力) 。
• 函数的管道化(松耦合，灵活)。

image.png

比较命令式代码，这的确是一个能够极大提高代码可读性的语法改进。然而，它与方法所属的对象紧紧地耦合在一起 ， 限制链中可以使用的方法数量 ，也就限制了代码的表现力。这样就只能够使用由 Lodash 提供的操作，而无法轻松地将不同函数库的(或自定义的)函数连接在一起。

7.1 兼容条件

由于 JavaScirpt 是弱类型语言，因此从类型角度来看，无须像使用一些静态类型语言一样太过关注类型。因此，如果一个对象在应用中表现得像某个特定类型， 那么它就是该类型。这也被称为鸭子类型 : “如果走起来像鸭子，并且像鸭子一样叫，那这就是一只鸭子。”
正式地讲，仅当 f 的输出类型等同于函数 g 的输入时，两个函数 f 和 g 是类型兼容的。举例来说， 一个处理学生社会安全号码的简单程序 :

image.png

使用 trim和normalize手动构建函数管道

手动构建函数管道

7.2 元数

元数定义为函数所接收的参数数量 ，也被称为函数的长度
如何返回两个不同的值呢?函数式语言通过一个称为元组的结构来做到这一点。元组是有限的、有序的元素列表。
来看一个代码示例：

return {
  status: false, 
  message: "Input is a too long"
}
// or
 return [false, "Input is too long"]; 

8. 函数执行机制

全局上下文帧永远驻留在堆栈的底部。每个函数的上下文帧都占用一定量的内存，实际取决于其中的局部变量的个数。如果没有任何局部变量，一个空帧大约 48 个字节。每个数字或布尔类型的局部变量和参数会占用 8字节。所以，函数体声明越多的变量，就需要越大的堆栈帧。 每一帧大致包含以下信息:

函数执行机制

注意 :函数的作用域链与 JavaScript 对象的原型链不是一回事。 虽然两者表现得很类似，但是原型链通过 prototype属性建立对象继承的链接，而作用域链是指内部函数能访问到外部函数的闭包。
堆栈的行为由下列规则确定。
• JavaScript 是单线程的，这意味着执行的同步性 。
• 有且只有一个全局上下文(与所有函数的上下文共享) 。
• 函数上下文的数量是有限制的(对客户端代码，不同的浏览器可以有不同的限制)。
• 每个函数调用会创建一个新的执行上下文，递归调用也是如此。

9. 柯里化与函数上下文堆栈

柯里化函数时，把一次函数执行变成了多次执行的函数(每次消费一个参数)，来看一个logger函数

const logger = function (appender, layout, name, level, message)

柯里化后会变成如下嵌套结构

const l ogger =
function (appender) {
  return function (layout) ( 
    return function (name) {
      return function (level) { 
        return function (message) {

嵌套结构的函数会使用更多的堆栈。 先来解释 logger 函数的非柯里化的执行。 由于 JavaScript 的同步执行机制，调用 logger 会暂停全局上下文的执行， 好让 logger 运行， 创建新的活跃上下文，并引用全局上下文中的所有变量。

image.png

调用任何函数时，如 logger，单线程 JavaScript 运行时会暂停当前全局上下文并激活新函数创建的上下文 。 此时，还会通过 scopeChain 创建到全局上下文的链接。
一旦 logger 返回，它的执行上下文也会被弹出堆栈，全局上下文将恢复

当 logger 函数调用其他函数 (如 Log4js)时， 会在堆栈上产生新函数的上下文。 由于 JavaScript的闭包，内部函数调用的上下文会在外部函数上下文堆栈的上面占用分配给它的存储器， 并经由 scopeChain 链接起来

运行嵌套函数时函数上下文的变化 。 因为每个函数会产生新的堆栈帧， 所以堆栈增长跟函数嵌套的层级成正比。 柯里化与递归都依赖于嵌套的函数调用

一旦 Log4js 代码运行完，它就会被弹出堆栈 ; logger 函数也会在之后被弹出， 运行时环境恢复到只有全局上下文的状态。这就是 JavaScript 的闭包背后的魔法。
虽然这种方法强大，但是嵌套深的函数会消耗大量的内存。

柯里化版本：

柯里化将每一个参数都转换成内部嵌套调用。可以连续提供参数带来了灵活性，却额外占用了堆栈空间

柯里化所有函数看起来是不错的主意，但是过度使用会导致其占用较大的堆栈空间，进而导致程序运行速度显著降低。

10. 惰性求值

当输人很大但只有一个小的子集有效时， 避免不必要的函数调用可以体现出许多性能优势，例如函数式语言 Haskell 就内置了惰性函数求值
JavaScript 使用的是更主流的函数求值策略一一及早求值。及早求值会在表达式绑定到变量时求值，不管结果是否会被用到，所以也称为贪婪求值

image.png

10.1 缓存(记忆化)

image.png

10.2 给函数添加记忆化

image.png

10.3 记忆化递归调用

image.png

由于记忆化了阶乘函数，在第二次迭代时吞吐量有显著的提升。在第二次运行时，函 数“记住”了使用公式“101!=101×100!”，并且可以重复使用 factorial(lOO)的值， 使得整个算法立即返回，并对战帧的管理以及污染堆栈方面都有好处

运行记忆化的 factorial(lOO)在第一次会创建 100 的堆栈帧 ， 因为它需要计算 100!在第二次 调用 101 的阶乘时通过记忆化能够重复使用 factorial (100)的结果， 所以只会创建 2个核帧

10.4 生成惰性数据

ES6 最强大的功能之一是可以通过暂停函数执行而不用一次运行完。这带来了许多(可能无限的)机会，比如函数可以生成惰性数据，而不必一次处理大量的数据。这称为生成器(generator)。
下面来看一个简单的例子，该例只取前 3 个元素，而不会产生无数的列表 :

image.png

使用生成器，可以惰性地从无限集中取一定数量的元素:

function take (amount , generator) { 
  let result= [];
  for (let n of generator) {
    result.push(n);
    if(n ===amount) { break };
  }
  return result
}
take(3, range(1, Infinity)); 11-> [1, 2, 3]

除了一些限制，生成器的行为与任何标准函数调用非常相似。可以通过给它传递参数，(也许是一个函数)来操作生成的值:

image.png

11. 生成器

11.1 生成器与递归

就像任何函数调用 一样，也可以在生成器中调用其他生成器。这对于将嵌套对象集合扁平化非常有用，比如树的遍历。因为可以用 for...of 遍历生成器，调用另一个生成器就类似于合并两个集合并遍历。

每个节点代表一个 student 对象，每个箭头代表“学生关系”

可以使用生成器轻松地对这棵树进行建模

image.png
下面的代码使用递归遍历这棵树(每个节点包含一个 Person 对象):
image.png

11.2 迭代器协议

生成函数返回符合迭代器协议的 Generator 对象。这意味着它实现一个名为 next ()的方法，该方法返回使用 yield 关键字 return 的值。此对象具有以下属性。
• done一一如果迭代器到达序列结尾，则值为 true;否则，值为 false，表示迭代器还可以生成下一个值 。
• value一一迭代器返回的值。

image.png

可以以这种形式创建符合某种规范的数据。例如平方生成器:

image.png

JavaScript 中有许多内含@@iterator属性的可迭代对象。数组是可以这样使用的 :

var iter = ['s', 't', 'r', 'e', 'a'][Symbol.iterator]()
iter.next().value // s
iter.next().value // t

字符串也可以迭代:

var iter= ’Stream’[Symbol.iterator](); 
iter.next() .value // -> S
 iter.next().value // -> t

12. Observable

Rx.Observable 对象将函数式编程与响应式编程结合在一起

image.png 从 Observable应用函数 filter 和 map 的过程

响应式编程倾向于和函数式编程一起使用，从而产生函数式晌应式编程