JavaScript Algorithms and Data Structures(八)

发表于 分类于 ， 本文字数： 9.5k 阅读时长 ≈ 9 分钟

freeCodeCamp —- JavaScript Algorithms and Data Structures

函数式编程

1. 学习函数式编程

函数式编程是一种方案简单、功能独立、对作用域外没有任何副作用的编程范式：INPUT -> PROCESS -> OUTPUT。

函数式编程：

1）功能独立——不依赖于程序的状态（比如可能发生变化的全局变量）；

2）纯函数——同一个输入永远能得到同一个输出；

3）有限的副作用——可以严格地限制函数外部对状态的更改。

2. 了解函数式编程术语

FCC 团队需求有变更，现在想要两种茶：绿茶（green tea）和红茶（black tea）。 事实证明，用户需求变更是很常见的。

基于以上信息，我们需要重构上一节挑战中的 getTea 函数来处理多种茶的请求。 我们可以修改 getTea 接受一个函数作为参数，使它能够修改茶的类型。 这让 getTea 更灵活，也使需求变更时为程序员提供更多控制权。

首先，我们将介绍一些术语：

Callbacks 是被传递到另一个函数中调用的函数。 你应该已经在其他函数中看过这个写法，例如在 filter 中，回调函数告诉 JavaScript 以什么规则过滤数组。

函数就像其他正常值一样，可以赋值给变量、传递给另一个函数，或从其它函数返回，这种函数叫做头等 first class 函数。 在 JavaScript 中，所有函数都是头等函数。

将函数作为参数或将函数作为返回值返回的函数叫作高阶函数。

当函数被传递给另一个函数或从另一个函数返回时，那些传入或返回的函数可以叫作 lambda。

3. 了解使用命令式编程的危害

使用函数式编程是一个好的习惯。 它使你的代码易于管理，避免潜在的 bug。 但在开始之前，先看看命令式编程方法，以强调你可能有什么问题。

在英语 (以及许多其他语言) 中，命令式时态用来发出指令。 同样，命令式编程是向计算机提供一套执行任务的声明。

命令式编程常常改变程序状态，例如更新全局变量。 一个典型的例子是编写 for 循环，它为一个数组的索引提供了准确的迭代方向。

相反，函数式编程是声明式编程的一种形式。 通过调用方法或函数来告诉计算机要做什么。

JavaScript 提供了许多处理常见任务的方法，所以你无需写出计算机应如何执行它们。 例如，你可以用 map 函数替代上面提到的 for 循环来处理数组迭代。 这有助于避免语义错误，如调试章节介绍的 “Off By One Errors”。

考虑这样的场景：你正在浏览器中浏览网页，并想操作你打开的标签。 下面我们来试试用面向对象的思路来描述这种情景。

窗口对象由选项卡组成，通常会打开多个窗口。 窗口对象中每个打开网站的标题都保存在一个数组中。 在对浏览器进行了如打开新标签、合并窗口、关闭标签之类的操作后，你需要输出所有打开的标签。 关掉的标签将从数组中删除，新打开的标签（为简单起见）则添加到数组的末尾。

代码编辑器中显示了此功能的实现，其中包含 tabOpen()，tabClose()，和 join() 函数。 tabs 数组是窗口对象的一部分用于储存打开页面的名称。

4. 使用函数式编程避免变化和副作用

如果你还没想通，上一个挑战的问题出在 tabClose() 函数里的 splice。 不幸的是，splice 修改了调用它的原始数组，所以第二次调用它时是基于修改后的数组，才给出了意料之外的结果。

这是一个小例子，还有更广义的定义——在变量，数组或对象上调用一个函数，这个函数会改变对象中的变量或其他东西。

函数式编程的核心原则之一是不改变任何东西。 变化会导致错误。 如果一个函数不改变传入的参数、全局变量等数据，那么它造成问题的可能性就会小很多。

前面的例子没有任何复杂的操作，但是 splice 方法改变了原始数组，导致 bug 产生。

回想一下，在函数式编程中，改变或变更叫做 mutation，这种改变的结果叫做“副作用”（side effect）。 理想情况下，函数应该是不会产生任何副作用的 pure function。

让我们尝试掌握这个原则：不要改变代码中的任何变量或对象。

5. 传递参数以避免函数中的外部依赖

上一个挑战是更接近函数式编程原则的挑战，但是仍然缺少一些东西。

虽然我们没有改变全局变量值，但在没有全局变量 fixedValue 的情况下，incrementer 函数将不起作用。

函数式编程的另一个原则是：总是显式声明依赖关系。 如果函数依赖于一个变量或对象，那么将该变量或对象作为参数直接传递到函数中。

这样做会有很多好处。 其中一点是让函数更容易测试，因为你确切地知道参数是什么，并且这个参数也不依赖于程序中的任何其他内容。

其次，这样做可以让你更加自信地更改，删除或添加新代码。 因为你很清楚哪些是可以改的，哪些是不可以改的，这样你就知道哪里可能会有潜在的陷阱。

最后，无论代码的哪一部分执行它，函数总是会为同一组输入生成相同的输出。

6. 在函数中重构全局变量

目前为止，我们已经看到了函数式编程的两个原则：

  1. 不要更改变量或对象 - 创建新变量和对象，并在需要时从函数返回它们。 提示：使用类似 const newArr = arrVar 的东西，其中 arrVar 是一个数组，只会创建对现有变量的引用，而不是副本。 所以更改 newArr 中的值会同时更改 arrVar 中的值。

  2. 声明函数参数 - 函数内的任何计算仅取决于参数，而不取决于任何全局对象或变量。

给数字增加 1 不够有意思，但是我们可以在处理数组或更复杂的对象时应用这些原则。

7. 使用 map 方法从数组中提取数据

目前为止，我们已经学会了使用纯函数来避免程序中的副作用。 此外，我们已经看到函数的值仅取决于其输入参数。

这仅仅是个开始。 顾名思义，函数式编程以函数理论为中心。

能够将它们作为参数传递给其他函数，从另一个函数返回一个函数是有意义的。 函数在 JavaScript 中被视为 First Class Objects，它们可以像任何其他对象一样使用。 它们可以保存在变量中，存储在对象中，也可以作为函数参数传递。

让我们从一些简单的数组函数开始，这些函数是数组对象原型上的方法。 在本练习中，我们来了解下数组的 map 方法（即 Array.prototype.map()）。

请记住，map方法是迭代数组中每一项的方式之一。 在对每个元素应用回调函数后，它会创建一个新数组(不改变原来的数组)。 它这样做时没有改变原始数组。

当调用回调函数时，传入了三个参数。 第一个参数是当前正在处理的数组项。 第二个参数是当前数组项的索引值，第三个参数是在其上调用 map 方法的数组。

看下在 users 上使用 map 方法的例子，返回了一个新数组只包含了用户的名字。 为了简化，例子里只使用了回调函数的第一个参数。

1
2
3
4
5
6
7
8
const users = [
  { name: 'John', age: 34 },
  { name: 'Amy', age: 20 },
  { name: 'camperCat', age: 10 }
];

const names = users.map(user => user.name);
console.log(names);

控制台将显示值 [ 'John', 'Amy', 'camperCat' ]。

8. 在原型上实现 map 方法

之前用到了 Array.prototype.map() 方法（即 map()），通过 map 返回一个与调用它的数组长度相同的数组。 只要它的回调函数不改变原始数组，它就不会改变原始数组。

换句话说，map 是一个纯函数，它的输出仅取决于输入的数组和作为参数传入的回调函数。 此外，它接收另一个函数作为它的参数。

实现一个 map，加深对它的了解。 你可以用 for 循环或者 Array.prototype.forEach() 方法。

9. 使用 filter 方法从数组中提取数据

另一个有用的数组方法是 filter()（即 Array.prototype.filter()）。

filter 在一个数组的每个元素上调用一个函数，并返回一个新的数组，其中只包含该函数返回一个真值的元素，也就是说，一个被传递给 Boolean() 构造函数后返回 true 的值。 换言之，它根据传递给它的函数过滤数组。 和 map 一样，filter 不会改变原始数组。

回调函数接收三个参数。 第一个参数是当前正在被处理的元素。 第二个参数是这个元素的索引，第三个参数是在其上调用 filter 方法的数组。

看下在 users 上使用 filter 方法的例子，返回了一个包含了 30 岁以下的用户新数组。 为了简化，例子里只使用了回调函数的第一个参数。

1
2
3
4
5
6
7
8
const users = [
  { name: 'John', age: 34 },
  { name: 'Amy', age: 20 },
  { name: 'camperCat', age: 10 }
];

const usersUnder30 = users.filter(user => user.age < 30);
console.log(usersUnder30);

控制台将显示值 [ { name: 'Amy', age: 20 }, { name: 'camperCat', age: 10 } ]

10.在原型上实现 filter 方法

为了加深对 filter 的理解，可以自己实现一个。 可以用 for 循环或 Array.prototype.forEach()。

1
2
3
4
5
6
7
8
9
10
11
Array.prototype.myFilter = function(callback) {
  const newArray = [];
  // Only change code below this line
  for (let i = 0; i < this.length; i++) {
    if (Boolean(callback(this[i], i, this)) === true) {
      newArray.push(this[i]);
    }
  }
  // Only change code above this line
  return newArray;
};

11. 使用 slice 方法返回数组的一部分

slice 方法可以从已有数组中返回指定元素。 它接受两个参数，第一个规定从何处开始选取，第二个规定从何处结束选取（不包括该元素）。 如果没有传参，则默认为从数组的开头开始到结尾结束，这是复制整个数组的简单方式。 slice 返回一个新数组，不会修改原始数组。

举个例子：

1
2
const arr = ["Cat", "Dog", "Tiger", "Zebra"];
const newArray = arr.slice(1, 3);

newArray 值为 ["Dog", "Tiger"]

12. 使用 slice 而不是 splice 从数组中移除元素

使用数组时经常遇到要删除一些元素并保留数组剩余部分的情况。 为此，JavaScript 提供了 splice 方法，它接收两个参数：从哪里开始删除项目的索引，和要删除的项目数。 如果没有提供第二个参数，默认情况下是移除一直到结尾的所有元素。 但 splice 方法会改变调用它的原始数组。 举个例子：

1
2
const cities = ["Chicago", "Delhi", "Islamabad", "London", "Berlin"];
cities.splice(3, 1);

在这里 splice 返回字符串 London 并从城市数组中删除它。 cities 将有值 ["Chicago", "Delhi", "Islamabad", "Berlin"]。

正如我们在上一次挑战中看到的那样，slice 方法不会改变原始数组，而是返回一个可以保存到变量中的新数组。 回想一下，slice 方法接收两个参数，从开始索引开始选取到结束（不包括该元素），并在新数组中返回这些元素。 使用 slice 方法替代 splice 有助于避免数组变化产生的副作用。

13. 使用 concat 方法组合两个数组

Concatenation 意思是将元素连接到尾部。 同理，JavaScript 为字符串和数组提供了concat方法。 对数组来说，在一个数组上调用 concat 方法，然后提供另一个数组作为参数添加到第一个数组末尾。 它返回一个新数组，不会改变任何一个原始数组。 举个例子：

1
[1, 2, 3].concat([4, 5, 6]);

返回的数组将是 [1, 2, 3, 4, 5, 6]。

14. 使用 concat 而不是 push 将元素添加到数组的末尾

函数式编程就是创建和使用具有不变性的函数。

上一个挑战介绍了 concat 方法，这是一种在不改变原始数组的前提下，将数组组合成一个新数组的方法。 将 concat 方法与 push 方法做比较。 push 将一个元素添加到调用它的数组的末尾，这样会改变该数组。 举个例子：

1
2
const arr = [1, 2, 3];
arr.push(4, 5, 6);

arr 的值被修改为 [1, 2, 3, 4, 5, 6]，这不是函数编程方式。

concat 方法可以将新项目添加到数组末尾，而不附带改变数组。

15. 使用 reduce 方法分析数据

reduce()（即Array.prototype.reduce()），是 JavaScript 所有数组操作中最常用的方法。 几乎可以用reduce方法解决所有数组处理问题。

reduce 方法是处理数组更通用的方式，而且 filter 和 map 方法都可以当作是 reduce 的特殊实现。 reduce 方法遍历数组中的每个项目并返回单个值（即字符串、数字、对象、数组）。 这是通过在每次迭代中调用一个回调函数来实现的。

回调函数接受四个参数。 第一个参数称为叠加器，它是上一次迭代中回调函数的返回值，第二个参数是当前正在处理的数组元素，第三个参数是该参数的索引，第四个参数是在其上调用 reduce 方法的数组。

除了回调函数，reduce 还有一个额外的参数作为叠加器的初始值。 如果没有第二个参数，会跳过第一次迭代，第二次迭代给叠加器传入数组的第一个元素。

见下面的例子，给 users 数组使用 reduce 方法，返回所有用户数组的和。 为了简化，例子仅使用了回调函数的第一个参数和第二个参数。

1
2
3
4
5
6
7
8
const users = [
  { name: 'John', age: 34 },
  { name: 'Amy', age: 20 },
  { name: 'camperCat', age: 10 }
];

const sumOfAges = users.reduce((sum, user) => sum + user.age, 0);
console.log(sumOfAges);

这里控制台将显示值 64。

在另一个例子里，查看如何返回一个包含用户名称做为属性，其年龄做为值的对象。

1
2
3
4
5
6
7
8
9
10
11
const users = [
  { name: 'John', age: 34 },
  { name: 'Amy', age: 20 },
  { name: 'camperCat', age: 10 }
];

const usersObj = users.reduce((obj, user) => {
  obj[user.name] = user.age;
  return obj;
}, {});
console.log(usersObj);

控制台将显示值 { John: 34, Amy: 20, camperCat: 10 }。

16. 使用 sort 方法按字母顺序给数组排序

sort 方法可以根据回调函数对数组元素进行排序。

举个例子：

1
2
3
4
5
6
7
function ascendingOrder(arr) {
  return arr.sort(function(a, b) {
    return a - b;
  });
}

ascendingOrder([1, 5, 2, 3, 4]);

这将返回值 [1, 2, 3, 4, 5]。

1
2
3
4
5
6
7
function reverseAlpha(arr) {
  return arr.sort(function(a, b) {
    return a === b ? 0 : a < b ? 1 : -1;
  });
}

reverseAlpha(['l', 'h', 'z', 'b', 's']);

这将返回值 ['z', 's', 'l', 'h', 'b']。

JavaScript 的默认排序方法是 Unicode 值顺序排序，有时可能会得到意想不到的结果。 因此，建议提供一个回调函数来指定如何对数组项目排序。 这个回调函数通常叫做 compareFunction，它根据 compareFunction 的返回值决定数组元素的排序方式： 如果两个元素 a 和 b，compareFunction(a,b) 返回一个比 0 小的值，那么 a 会在 b 的前面。 如果两个元素 a 和 b，compareFunction(a,b) 返回一个比 0 大的值，那么 b 会在 a 的前面。 如果两个元素 a 和 b，compareFunction(a,b) 返回等于 0 的值，那么 a 和 b 的位置保持不变。

17. 在不更改原始数组的前提下返回排序后的数组

sort 方法会产生改变原始数组中元素顺序的副作用。 换句话说，它会改变数组的位置。 避免这种情况的一种方法是先将空数组连接到正在排序的数组上（记住 slice 和 concat 返回一个新数组），再用sort方法。

18. 使用 split 方法将字符串拆分成数组

split 方法将一个字符串分割成一个字符串数组。 它需要一个参数作为分隔符，它可以是用于拆分字符串或正则表达式的一个字符。 举个例子，如果分隔符是空格，你会得到一个单词数组；如果分隔符是空字符串，你会得到一个由字符串中每个字符组成的数组。

下面是两个用空格分隔一个字符串的例子，另一个是用数字的正则表达式分隔：

1
2
3
4
5
const str = "Hello World";
const bySpace = str.split(" ");

const otherString = "How9are7you2today";
const byDigits = otherString.split(/\d/);

bySpace 将有值 ["Hello", "World"]，byDigits 将有值 ["How", "are", "you", "today"]。

因为字符串是不可变的，split 方法操作它们更方便。

19. 使用 join 方法将数组组合成字符串

join 方法用来把数组中的所有元素放入一个字符串。 并通过指定的分隔符参数进行分隔。

举个例子：

1
2
const arr = ["Hello", "World"];
const str = arr.join(" ");

str 的值应该是字符串 Hello World。

20. 应用函数式编程将字符串转换为URL片段

最后几个挑战中涵盖了许多符合函数式编程原则并在处理数组和字符串中非常有用的方法。 我们还学习了强大的、可以将问题简化为更简单形式的 reduce 方法。 从计算平均值到排序，任何数组操作都可以用它来实现。 回想一下，map 和 filter 方法都是 reduce 的特殊实现。

让我们把学到的知识结合起来解决一个实际问题。

许多内容管理站点（CMS）为了让添加书签更简单，会将帖子的标题添加到 URL 上。 举个例子，如果你写了一篇标题为 Stop Using Reduce 的帖子，URL很可能会包含标题字符串的某种形式 (如：.../stop-using-reduce)。 你可能已经在 freeCodeCamp 网站上注意到了这一点。

21. 使用 every 方法检查数组中的每个元素是否符合条件

every 方法用于检测数组中所有元素是否都符合指定条件。 如果所有元素满足条件，返回布尔值 true，反之返回 false。

举个例子，下面的代码检测数组 numbers 的所有元素是否都小于 10：

1
2
3
4
5
const numbers = [1, 5, 8, 0, 10, 11];

numbers.every(function(currentValue) {
  return currentValue < 10;
});

every 方法在这里会返回 false。

22. 使用 some 方法检查数组中是否有元素是否符合条件

some 方法用于检测数组中任何元素是否满足指定条件。 如果有一个元素满足条件，返回布尔值 true，反之返回 false。

举个例子，下面的代码检测数组numbers中是否有元素小于 10：

1
2
3
4
5
const numbers = [10, 50, 8, 220, 110, 11];

numbers.some(function(currentValue) {
  return currentValue < 10;
});

some 方法将返回 true。

23. 函数柯里化和局部调用

arity（参数个数）是函数所需的形参的数量。 函数柯里化（Currying）意思是把接受多个 arity 的函数变换成接受单一 arity 的函数。

换句话说，就是重构函数让它接收一个参数，然后返回接收下一个参数的函数，依此类推。

举个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
function unCurried(x, y) {
  return x + y;
}

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

const curried = x => y => x + y

curried(1)(2)

curried(1)(2) 会返回 3。

柯里化在不能一次为函数提供所有参数情况下很有用。 因为它可以将每个函数的调用保存到一个变量中，该变量将保存返回的函数引用，该引用在下一个参数可用时接受该参数。 下面是使用柯里化函数的例子：

1
2
const funcForY = curried(1);
console.log(funcForY(2)); // 3

类似地，局部调用（ partial application）的意思是一次对一个函数应用几个参数，然后返回另一个应用更多参数的函数。 这是一个示例：

1
2
3
4
5
6
function impartial(x, y, z) {
  return x + y + z;
}

const partialFn = impartial.bind(this, 1, 2);
partialFn(10); // 13