阵列折叠能做什么？

这是“折叠”系列的第 2 部分，我们将了解如何使用简单的折叠模式执行各种数组处理任务。

那又是什么？

在上一篇文章中，我们了解了折叠的底层工作原理。现在我们再回顾一下：

const fold = (reducer, init, xs) => {
    let acc = init;
    for (const x of xs) {
        acc = reducer(acc, x);
    }
    return acc;
};

它使用for..of循环遍历列表xs，每次减少列表，直到最终只剩下一个值。这种编程模式非常强大。当我第一次了解折叠操作时，我怀疑这么简单的操作怎么能做这么多事情。但事实证明，编程中的很多问题都是归约问题——我们有一个包含内容的列表，我们想从中提取一条信息。

你们中的许多人可能熟悉 Python 的内置函数sum、len和max。所有这些函数本质上都是折叠。我想看看仅使用上面的函数定义，我可以在 JavaScript 中实现多少折叠。这将真正展示这个看似简单的小函数所能完成的各种功能。因此，下面列出了我们可以使用折叠创建的不同函数。

保持警惕

我想提一下，下面显示的每个折叠中都有两个部分值得注意：

• Reducer：我为每个 fold 单独定义了 Reducer，而不是像foldadd的 Reducer那样内联定义sum。Reducer 传递了两个参数，acc和x。 的数据类型acc与其初始值相同。
• 初始值：请注意，每个折叠累积的初始值相对于 Reducer 而言都是一个恒等值。例如，0是折叠中使用的初始值sum，因为它在 Reducer 下是恒等值add。请记住，从 Reducer 的角度来看，累积的初始值本质上应该不包含任何信息。它应该是无效的、无用的，就像add看起来0没有任何信息一样。

看哪，褶皱

sum

sum(xs: number[]): number

const add = (acc, x) => acc + x;
const sum = xs => fold(add, 0, xs);

当被问及如何将一系列值汇总成一个列表时，这sum可能是您首先想到的事情。

len

len(xs: any[]): number

const inc = (acc, x) => acc + 1;
const len = xs => fold(inc, 0, xs);

这是对 Python 中广受欢迎的 的模拟len。在 Reducer 中，我们忽略每个元素x，而只添加1。

product

product(xs: number[]): number

const mult = (acc, x) => acc * x;
const product = xs => fold(mult, 1, xs);

一串数字的乘积。即使只有一个0数字，xs这个折叠也会失效。

join

join(xs: any[]): string

const concat = (acc, x) => `${acc}${x}`;
const join = xs => fold(concat, '', xs);

这将连接一个字符串列表，或者任何内容的列表！注入x模板字符串会调用它的.toString()方法。所以我说声明是join(xs: any[]): string，不够具体。我实际上想要的是xs类型，xs: A[]其中A是一种数据类型，当我们调用它的时，它会返回一个格式良好的字符串.toString()。如果没有静态类型，我们无法在 JavaScript 中做到这一点。不过，我们在其他语言中也看到了这个特性，比如通过Haskell 中的类型类和TypeScript 中的接口。没有它，JS 会尝试以x默认方式字符串化，这对于更复杂的对象可能效果不佳。

all

all(xs: boolean[]): boolean

const and = (acc, x) => acc && x;
const all = xs => fold(and, true, xs);

all我非常喜欢和折叠看起来多么简洁some。但有一个问题是，当结果显而易见时，它们不会跳出循环。all([false, true, true, true])即使结果在第一个 就已经知道， 也会遍历整个列表false。

some

some(xs: boolean[]): boolean

const or = (acc, x) => acc || x;
const some = xs => fold(or, false, xs);

maximum

maximum(xs: number[]): number

const max = (acc, x) => (x > acc) ? x : acc;
const maximum = xs => fold(max, -Infinity, xs);

maximum和minimum可以用于任何可排序数据类型的数组，例如 JavaScript 字符串。但这样一来，我们就必须使用合适的初始值。我们这里使用的-Infinity仅适用于数字数组。

minimum

minimum(xs: number[]): number

const min = (acc, x) => (x < acc) ? x : acc;
const minimum = xs => fold(min, Infinity, xs);

flatten

flatten(xs: any[][]): any[]

const concatArray = (acc, x) => [...acc, ...x];
const flatten = xs => fold(concatArray, [], xs);

这绝对是我的最爱之一。这里有很多数组复制操作。我们本可以修改accusingacc.push(...x)并返回它，以避免一直复制数据，但不得不承认，扩展运算符看起来更简洁。它可以将数组展平一层，就像 Lodash 的_.flattenacc一样。

merge

merge(xs: object[]): object

const combine = (acc, x) => ({ ...acc, ...x });
const merge = xs => fold(combine, {}, xs);

merge与 非常相似，只不过它作用于对象。其flatten行为类似于 JavaScript 内置的Object.assign。

reverse

reverse(xs: any[]): any[]

const prepend = (acc, x) => [x, ...acc];
const reverse = xs => fold(prepend, [], xs);

我们可以做到这一点的另一种方法是改变acc使用acc.unshift(x)（MDN）并返回它，而不是通过扩展运算符复制它。

警告：这个 fold 有点奇怪。还记得我说过，累加器的初始值应该是相对于 Reducer 的恒等式吗？好吧，这里的 ，[]不是。prepend([], x)它会返回[x]。根据维基百科关于 fold 的描述：

人们常常想选择运算 f 的恒等元作为初始值 z。

没有提到对恒等元的严格要求。所以，在我们这个混乱的编程世界里，也许某些优雅的数学规则不得不被打破。又或许我只是在某个地方犯了个错误。

pipe

pipe(xs: { (x: any): any }[]): (x: any): any

const composeR = (acc, x) => {
    return m => x(acc(m));
};
const pipe = xs => fold(composeR, x => x, xs);

这是我最喜欢的。我可能在这里弄错了 pipe 函数的类型声明，所以请您原谅我。我觉得有趣的是 acc 的初始值 。x => x它真正体现了这样一个观点：初始值相对于 Reducer 是恒等的。至于 Reducer，它就像数学函数 Composition，只不过是反过来的。

管道接收一个一元函数列表作为参数，并返回一个按顺序运行所有函数的函数。每个函数的返回值作为下一个函数的参数。

last

const second = (acc, x) => x;
const last = xs => fold(second, null, xs);

我只是觉得把它放在最后比较合适。

不仅仅是折叠

到目前为止我们看到的所有例子都是折叠——它们接受一个列表，然后只返回一个值。接下来的例子并不完全是同一意义上的折叠，但我们仍然可以使用折叠来实现它们。没错，map而且filter可以通过折叠来实现！

它们不仅需要一个xs参数，还需要一个函数f。因此，reducer 必须以内联方式定义，这样我们才能f通过 reducer 的闭包捕获 。这些示例也违反了身份规则（参见reverse上文）。

map

const map = (f, xs) => fold((acc, x) => [...acc, f(x)], [], xs);

filter

const filter = (f, xs) => fold((acc, x) => {
    return f(x)
        ? [...acc, x]
        : acc;
}, [], xs);

在 和 中map，我们都传入了beforefilter函数，使它们遵循“先迭代，后数据”的原则。这样我们就可以利用柯里化的强大功能，使代码更加模块化和可组合。f xs

再说一次，我们本可以修改accusing acc.push，但这样做优雅吗？这违背了函数式编程 (FP) 所倡导的不变性原则。当然，我是开玩笑的，这些都只是实验。在实际的软件开发中，我们并不希望在自己的 JS 实现中过于函数式化，因为 JS 并没有针对函数式进行优化（除非我们非常清楚自己在做什么）。如果是函数式，我们最好使用 lodash/fp 或 Ramda 等现有的库。

游乐场

上面的每段代码都包含在下面的这个 Playground 中。我还添加了一些示例来展示如何组合使用这些折叠。不过需要注意的是：在移动设备屏幕上看起来会比较杂乱。

就像我在上一篇文章中所说的那样，我们实现折叠的方式是一种黑客行为。

const fold = (reducer, init, xs) => {
    let acc = init;
    for (const x of xs) {
        acc = reducer(acc, x);
    }
    return acc;
};

我们使用了 for 循环并重新赋值了acc变量，这显然违背了不变性原则。下一篇文章会讲解如何实现这一点。

本文的一些想法受到以下启发：

• 关于 Folds 的 Medium 文章
• 《Learn You a Haskell》中的 Folds 部分