五、高阶函数

五、高阶函数

Tzu-li and Tzu-ssu were boasting about the size of their latest programs. ‘Two-hundred thousand lines,’ said Tzu-li, ‘not counting comments!’ Tzu-ssu responded, ‘Pssh, mine is almost a million lines already.’ Master Yuan-Ma said, ‘My best program has five hundred lines.’ Hearing this, Tzu-li and Tzu-ssu were enlightened.

Master Yuan-Ma，《The Book of Programming》

There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies.

C.A.R. Hoare，1980 ACM Turing Award Lecture

开发大型程序通常需要耗费大量财力和物力，这绝不仅仅是因为构建程序所花费时间的问题。大型程序的复杂程度总是很高，而这些复杂性也会给开发人员带来不少困扰，而程序错误或 bug 往往就是这些时候引入的。大型程序为这些 bug 提供了良好的藏身之所，因此我们更加难以在大型程序中找到它们。

让我们简单回顾一下前言当中的两个示例。其中第一个程序包含了 6 行代码并可以直接运行。

let total = 0, count = 1;
while (count <= 10) {
  total += count;
  count += 1;
}
console.log(total);

第二个程序则依赖于外部函数才能执行，且只有一行代码。

console.log(sum(range(1, 10)));

哪一个程序更有可能含有 bug 呢？

如果算上sum和range两个函数的代码量，显然第二个程序的代码量更大。不过，我仍然觉得第二个程序包含 bug 的可能性比第一个程序低。

之所以这么说的原因是，第二个程序编写的代码很好地表达了我们期望解决的问题。对于计算一组数字之和这个操作来说，我们关注的是计算范围和求和运算，而不是循环和计数。

sum和range这两个函数定义的操作当然会包含循环、计数和其他一些操作。但相比于将这些代码直接写到一起，这种表述方式更为简单，同时也易于避免错误。

抽象

在程序设计中，我们把这种编写代码的方式称为抽象。抽象可以隐藏底层的实现细节，从更高（或更加抽象）的层次看待我们要解决的问题。

举个例子，比较一下这两份豌豆汤的食谱：

按照每人一杯的量将脱水豌豆放入容器中。倒水直至浸没豌豆，然后至少将豌豆浸泡 12 个小时。将豌豆从水中取出沥干，倒入煮锅中，按照每人四杯水的量倒入水。将食材盖满整个锅底，并慢煮 2 个小时。按照每人半个的量加入洋葱，用刀切片，然后放入豌豆中。按照每人一根的量加入芹菜，用刀切片，然后放入豌豆当中。按照每人一根的量放入胡萝卜，用刀切片，然后放入豌豆中。最后一起煮 10 分钟以上即可。

第二份食谱：

一个人的量：一杯脱水豌豆、半个切好的洋葱、一根芹菜和一根胡萝卜。

将豌豆浸泡 12 个小时。按照每人四杯水的量倒入水，然后用文火煨 2 个小时。加入切片的蔬菜，煮 10 分钟以上即可。

相比第一份食谱，第二份食谱更简短且更易于理解。但你需要了解一些有关烹调的术语：浸泡、煨、切片，还有蔬菜。

在编程的时候，我们不能期望所有功能都是现成的。因此，你可能就会像第一份食谱那样编写你的程序，逐个编写计算机需要执行的代码和步骤，而忽略了这些步骤之上的抽象概念。

在编程时，注意你的抽象级别什么时候过低，是一项非常有用的技能。

重复的抽象

我们已经了解的普通函数就是一种很好的构建抽象的工具。但有些时候，光有函数也不一定能够解决我们的问题。

程序以给定次数执行某些操作很常见。 你可以为此写一个for循环，就像这样：

for (let i = 0; i < 10; i++) {
  console.log(i);
}

我们是否能够将“做某件事N次”抽象为函数？ 编写一个调用console.log N次的函数是很容易的。

function repeatLog(n) {
  for (let i = 0; i < n; i++) {
    console.log(i);
  }
}

但如果我们想执行打印数字以外的操作该怎么办呢？我们可以使用函数来定义我们想做的事，而函数也是值，因此我们可以将期望执行的操作封装成函数，然后传递进来。

function repeat(n, action) {
  for (let i = 0; i < n; i++) {
    action(i);
  }
}

repeat(3, console.log);
// → 0
// → 1
// → 2

你不必将预定义的函数传递给repeat。 通常情况下，你希望原地创建一个函数值。

let labels = [];
repeat(5, i => {
  labels.push(`Unit ${i + 1}`);
});
console.log(labels);
// → ["Unit 1", "Unit 2", "Unit 3", "Unit 4", "Unit 5"]

这个结构有点像for循环 - 它首先描述了这种循环，然后提供了一个主体。 但是，主体现在写为一个函数值，它被包裹在repeat调用的括号中。 这就是它必须用右小括号和右大括号闭合的原因。 在这个例子中，主体是单个小表达式，你也可以省略大括号并将循环写成单行。

高阶函数

如果一个函数操作其他函数，即将其他函数作为参数或将函数作为返回值，那么我们可以将其称为高阶函数。因为我们已经看到函数就是一个普通的值，那么高阶函数也就不是什么稀奇的概念了。高阶这个术语来源于数学，在数学当中，函数和值的概念有着严格的区分。

我们可以使用高阶函数对一系列操作和值进行抽象。高阶函数有多种表现形式。比如你可以使用高阶函数来新建另一些函数。

function greaterThan(n) {
  return m => m > n;
}
let greaterThan10 = greaterThan(10);
console.log(greaterThan10(11));
// → true

你也可以使用高阶函数来修改其他的函数。

function noisy(f) {
  return (...args) => {
    console.log("calling with", args);
    let result = f(...args);
    console.log("called with", args, ", returned", result);
    return result;
  };
}
noisy(Math.min)(3, 2, 1);
// → calling with [3, 2, 1]
// → called with [3, 2, 1] , returned 1

你甚至可以使用高阶函数来实现新的控制流。

function unless(test, then) {
  if (!test) then();
}
repeat(3, n => {
  unless(n % 2 == 1, () => {
    console.log(n, "is even");
  });
});
// → 0 is even
// → 2 is even

有一个内置的数组方法，forEach，它提供了类似for/of循环的东西，作为一个高阶函数。

["A", "B"].forEach(l => console.log(l));
// → A
// → B

脚本数据集

数据处理是高阶函数表现突出的一个领域。 为了处理数据，我们需要一些真实数据。 本章将使用脚本书写系统的数据集，例如拉丁文，西里尔文或阿拉伯文。

请记住第 1 章中的 Unicode，该系统为书面语言中的每个字符分配一个数字。 大多数这些字符都与特定的脚本相关联。 该标准包含 140 个不同的脚本 - 81 个今天仍在使用，59 个是历史性的。

虽然我只能流利地阅读拉丁字符，但我很欣赏这样一个事实，即人们使用其他至少 80 种书写系统来编写文本，其中许多我甚至不认识。 例如，以下是泰米尔语手写体的示例。

示例数据集包含 Unicode 中定义的 140 个脚本的一些信息。 本章的编码沙箱中提供了SCRIPTS绑定。 该绑定包含一组对象，其中每个对象都描述了一个脚本。

{
  name: "Coptic",
  ranges: [[994, 1008], [11392, 11508], [11513, 11520]],
  direction: "ltr",
  year: -200,
  living: false,
  link: "https://en.wikipedia.org/wiki/Coptic_alphabet"
}

这样的对象会告诉你脚本的名称，分配给它的 Unicode 范围，书写方向，（近似）起始时间，是否仍在使用以及更多信息的链接。 方向可以是从左到右的"ltr"，从右到左的"rtl"（阿拉伯语和希伯来语文字的写法），或者从上到下的"ttb"（蒙古文的写法）。

ranges属性包含 Unicode 字符范围数组，每个数组都有两元素，包含下限和上限。 这些范围内的任何字符码都会分配给脚本。 下限是包括的（代码 994 是一个科普特字符），并且上限排除在外（代码 1008 不是）。

数组过滤

为了找到数据集中仍在使用的脚本，以下函数可能会有所帮助。 它过滤掉数组中未通过测试的元素：

function filter(array, test) {
  let passed = [];
  for (let element of array) {
    if (test(element)) {
      passed.push(element);
    }
  }
  return passed;
}

console.log(filter(SCRIPTS, script => script.living));
// → [{name: "Adlam", …}, …]

该函数使用名为test的参数（一个函数值）填充计算中的“间隙” - 决定要收集哪些元素的过程。

需要注意的是，filter函数并没有从当前数组中删除元素，而是新建了一个数组，并将满足条件的元素存入新建的数组中。这个函数是一个“纯函数”，因为该函数并未修改给定的数组。

与forEach一样，filter函数也是标准的数组方法。本例中定义的函数只是用于展示内部实现原理。今后我们会使用以下方法来过滤数据：

console.log(SCRIPTS.filter(s => s.direction == "ttb"));
// → [{name: "Mongolian", …}, …]

使用map函数转换数组

假设我们已经通过某种方式过滤了SCRIPTS数组，生成一个用于表示脚本的信息数组。但我们想创建一个包含名称的数组，因为这样更加易于检查。

map方法对数组中的每个元素调用函数，然后利用返回值来构建一个新的数组，实现转换数组的操作。新建数组的长度与输入的数组一致，但其中的内容却通过对每个元素调用的函数“映射”成新的形式。

function map(array, transform) {
  let mapped = [];
  for (let element of array) {
    mapped.push(transform(element));
  }
  return mapped;
}

let rtlScripts = SCRIPTS.filter(s => s.direction == "rtl");
console.log(map(rtlScripts, s => s.name));
// → ["Adlam", "Arabic", "Imperial Aramaic", …]

与forEach和filter一样，map也是标准的数组方法。

使用reduce汇总数据

与数组有关的另一个常见事情是从它们中计算单个值。 我们的递归示例，汇总了一系列数字，就是这样一个例子。 另一个例子是找到字符最多的脚本。

表示这种模式的高阶操作称为归约（reduce）（有时也称为折叠（fold））。 它通过反复从数组中获取单个元素，并将其与当前值合并来构建一个值。 在对数字进行求和时，首先从数字零开始，对于每个元素，将其与总和相加。

reduce函数包含三个参数：数组、执行合并操作的函数和初始值。该函数没有filter和map那样直观，所以仔细看看：

function reduce(array, combine, start) {
  let current = start;
  for (let element of array) {
    current = combine(current, element);
  }
  return current;
}

console.log(reduce([1, 2, 3, 4], (a, b) => a + b, 0));
// → 10

数组中有一个标准的reduce方法，当然和我们上面看到的那个函数一致，可以简化合并操作。如果你的数组中包含多个元素，在调用reduce方法的时候忽略了start参数，那么该方法将会使用数组中的第一个元素作为初始值，并从第二个元素开始执行合并操作。

console.log([1, 2, 3, 4].reduce((a, b) => a + b));
// → 10

为了使用reduce（两次）来查找字符最多的脚本，我们可以这样写：

function characterCount(script) {
  return script.ranges.reduce((count, [from, to]) => {
    return count + (to - from);
  }, 0);
}

console.log(SCRIPTS.reduce((a, b) => {
  return characterCount(a) < characterCount(b) ? b : a;
}));
// → {name: "Han", …}

characterCount函数通过累加范围的大小，来减少分配给脚本的范围。 请注意归约器函数的参数列表中使用的解构。 `reduce'的第二次调用通过重复比较两个脚本并返回更大的脚本，使用它来查找最大的脚本。

Unicode 标准分配了超过 89,000 个字符给汉字脚本，它成为数据集中迄今为止最大的书写系统。 汉字是一种（有时）用于中文，日文和韩文的文字。 这些语言共享很多字符，尽管他们倾向于以不同的方式写它们。 （基于美国的）Unicode 联盟决定将它们看做一个单独的书写系统来保存字符码。 这被称为中日韩越统一表意文字（Han unification），并且仍然使一些人非常生气。

可组合性

考虑一下，我们怎样才可以在不使用高阶函数的情况下，编写以上示例（找到最大的脚本）？代码没有那么糟糕。

let biggest = null;
for (let script of SCRIPTS) {
  if (biggest == null ||
      characterCount(biggest) < characterCount(script)) {
    biggest = script;
  }
}
console.log(biggest);
// → {name: "Han", …}

这段代码中多了一些绑定，虽然多了两行代码，但代码逻辑还是很容易让人理解的。

当你需要组合操作时，高阶函数的价值就突显出来了。举个例子，我们编写一段代码，找出数据集中男人和女人的平均年龄。

function average(array) {
  return array.reduce((a, b) => a + b) / array.length;
}

console.log(Math.round(average(
  SCRIPTS.filter(s => s.living).map(s => s.year))));
// → 1185
console.log(Math.round(average(
  SCRIPTS.filter(s => !s.living).map(s => s.year))));
// → 209

因此，Unicode 中的死亡脚本，平均比活动脚本更老。 这不是一个非常有意义或令人惊讶的统计数据。 但是我希望你会同意，用于计算它的代码不难阅读。 你可以把它看作是一个流水线：我们从所有脚本开始，过滤出活动的（或死亡的）脚本，从这些脚本中抽出时间，对它们进行平均，然后对结果进行四舍五入。

你当然也可以把这个计算写成一个大循环。

let total = 0, count = 0;
for (let script of SCRIPTS) {
  if (script.living) {
    total += script.year;
    count += 1;
  }
}
console.log(Math.round(total / count));
// → 1185

但很难看到正在计算什么以及如何计算。 而且由于中间结果并不表示为一致的值，因此将“平均值”之类的东西提取到单独的函数中，需要更多的工作。

就计算机实际在做什么而言，这两种方法也是完全不同的。 第一个在运行filter和map的时候会建立新的数组，而第二个只会计算一些数字，从而减少工作量。 你通常可以采用可读的方法，但是如果你正在处理巨大的数组，并且多次执行这些操作，那么抽象风格的加速就是值得的。

字符串和字符码

这个数据集的一种用途是确定一段文本所使用的脚本。 我们来看看执行它的程序。

请记住，每个脚本都有一组与其相关的字符码范围。 所以给定一个字符码，我们可以使用这样的函数来找到相应的脚本（如果有的话）：

function characterScript(code) {
  for (let script of SCRIPTS) {
    if (script.ranges.some(([from, to]) => {
      return code >= from && code < to;
    })) {
      return script;
    }
  }
  return null;
}

console.log(characterScript(121));
// → {name: "Latin", …}

some方法是另一个高阶函数。 它需要一个测试函数，并告诉你该函数是否对数组中的任何元素返回true。

但是，我们如何获得字符串中的字符码？

在第一章中，我提到 JavaScript 字符串被编码为一个 16 位数字的序列。 这些被称为代码单元。 一个 Unicode 字符代码最初应该能放进这样一个单元（它给你超 65,000 个字符）。 后来人们发现它不够用了，很多人避开了为每个字符使用更多内存的需求。 为了解决这些问题，人们发明了 UTF-16，JavaScript 字符串使用的格式 。它使用单个 16 位代码单元描述了大多数常见字符，但是为其他字符使用一对两个这样的单元。

今天 UTF-16 通常被认为是一个糟糕的主意。 它似乎总是故意设计来引起错误。 很容易编写程序，假装代码单元和字符是一个东西。 如果你的语言不使用两个单位的字符，显然能正常工作。 但只要有人试图用一些不太常见的中文字符来使用这样的程序，就会中断。 幸运的是，随着 emoji 符号的出现，每个人都开始使用两个单元的字符，处理这些问题的负担更加分散。

// Two emoji characters, horse and shoe
let horseShoe = "\ud83d\udc34\ud83d\udc5f";
console.log(horseShoe.length);
// → 4
console.log(horseShoe[0]);
// → (Invalid half-character)
console.log(horseShoe.charCodeAt(0));
// → 55357 (Code of the half-character)
console.log(horseShoe.codePointAt(0));
// → 128052 (Actual code for horse emoji)

JavaScript的charCodeAt方法为你提供了一个代码单元，而不是一个完整的字符代码。 稍后添加的codePointAt方法确实提供了完整的 Unicode 字符。 所以我们可以使用它从字符串中获取字符。 但传递给codePointAt的参数仍然是代码单元序列的索引。 因此，要运行字符串中的所有字符，我们仍然需要处理一个字符占用一个还是两个代码单元的问题。

在上一章中，我提到for/of循环也可以用在字符串上。 像codePointAt一样，这种类型的循环，是在人们敏锐地意识到 UTF-16 的问题的时候引入的。 当你用它来遍历一个字符串时，它会给你真正的字符，而不是代码单元。

let roseDragon = "\ud83c\udf45\ud83d\udc09";
for (let char of roseDragon) {
  console.log(char);
// → (emoji rose)
// → (emoji dragon)

如果你有一个字符（它是一个或两个代码单元的字符串），你可以使用codePointAt(0)来获得它的代码。

识别文本

我们有了characterScript函数和一种正确遍历字符的方法。 下一步将是计算属于每个脚本的字符。 下面的计数抽象会很实用：

function countBy(items, groupName) {
  let counts = [];
  for (let item of items) {
    let name = groupName(item);
    let known = counts.findIndex(c => c.name == name);
    if (known == -1) {
      counts.push({name, count: 1});
    } else {
      counts[known].count++;
    }
  }
  return counts;
}  

console.log(countBy([1, 2, 3, 4, 5], n => n > 2));
// → [{name: false, count: 2}, {name: true, count: 3}]

countBy函数需要一个集合（我们可以用for/of来遍历的任何东西）以及一个函数，它计算给定元素的组名。 它返回一个对象数组，每个对象命名一个组，并告诉你该组中找到的元素数量。

它使用另一个数组方法findIndex。 这个方法有点像indexOf，但它不是查找特定的值，而是查找给定函数返回true的第一个值。 像indexOf一样，当没有找到这样的元素时，它返回 -1。

使用countBy，我们可以编写一个函数，告诉我们在一段文本中使用了哪些脚本。

function textScripts(text) {
  let scripts = countBy(text, char => {
    let script = characterScript(char.codePointAt(0));
    return script ? script.name : "none";
  }).filter(({name}) => name != "none");

  let total = scripts.reduce((n, {count}) => n + count, 0);
  if (total == 0) return "No scripts found";

  return scripts.map(({name, count}) => {
    return `${Math.round(count * 100 / total)}% ${name}`;
  }).join(", ");
}

console.log(textScripts('英国的狗说"woof", 俄罗斯的狗说"тяв"'));
// → 61% Han, 22% Latin, 17% Cyrillic

该函数首先按名称对字符进行计数，使用characterScript为它们分配一个名称，并且对于不属于任何脚本的字符，回退到字符串"none"。 filter调用从结果数组中删除"none"的条目，因为我们对这些字符不感兴趣。

为了能够计算百分比，我们首先需要属于脚本的字符总数，我们可以用reduce来计算。 如果没有找到这样的字符，该函数将返回一个特定的字符串。 否则，它使用map将计数条目转换为可读的字符串，然后使用join合并它们。

本章小结

能够将函数值传递给其他函数，是 JavaScript 的一个非常有用的方面。 它允许我们编写函数，用它们中的“间隙”对计算建模。 调用这些函数的代码，可以通过提供函数值来填补间隙。

数组提供了许多有用的高阶方法。 你可以使用forEach来遍历数组中的元素。 filter方法返回一个新数组，只包含通过谓词函数的元素。 通过将函数应用于每个元素的数组转换，使用map来完成。 你可以使用reduce将数组中的所有元素合并为一个值。 some方法测试任何元素是否匹配给定的谓词函数。 findIndex找到匹配谓词的第一个元素的位置。

习题

展开

联合使用reduce方法和concat方法，将一个数组的数组“展开”成一个单个数组，包含原始数组的所有元素。

let arrays = [[1, 2, 3], [4, 5], [6]];
// Your code here.
// → [1, 2, 3, 4, 5, 6]

你自己的循环

编写一个高阶函数loop，提供类似for循环语句的东西。 它接受一个值，一个测试函数，一个更新函数和一个主体函数。 每次迭代中，它首先在当前循环值上运行测试函数，并在返回false时停止。 然后它调用主体函数，向其提供当前值。 最后，它调用update函数来创建一个新的值，并从头开始。

定义函数时，可以使用常规循环来执行实际循环。

// Your code here.

loop(3, n => n > 0, n => n - 1, console.log);
// → 3
// → 2
// → 1

every

类似于some方法，数组也有every方法。 当给定函数对数组中的每个元素返回true时，此函数返回true。 在某种程度上，some是作用于数组的||运算符的一个版本，every就像&&运算符。

将every实现为一个函数，接受一个数组和一个谓词函数作为参数。编写两个版本，一个使用循环，另一个使用some方法。

function every(array, test) {
  // Your code here.
}

console.log(every([1, 3, 5], n => n < 10));
// → true
console.log(every([2, 4, 16], n => n < 10));
// → false
console.log(every([], n => n < 10));
// → true