掌握reduce

由 David Gao 发布于：

翻译, 编程

在函数式编程时中，reduce是一个非常重要的函数，在日常工作中，我们很多时候需要使用reduce来完成我们的任务。

原文地址: Getting a handle on Reduce

尽管受Algol影响而产生的语言占这整个行业的主导地位，但是在过去的数十年当中，采用不可变的数据结构的函数式编程语言技术也在许多领域中得到了广泛使用。从React和许多前端友好的工具，语言等到基于Map-Reduce的或者是大量受其启发的数据仓库系统，这些产品为世界上一些大型的应用提供了支撑，当今世界理解并使用这些技术，已经是程序员必备的技能了。

本篇博文的主题是reduce这个高阶函数1，同时它有类似fold，aggregate等大量的别名。Reduce是一个非常有用的函数，但是我发现很多开发人员，在理解和使用它时，碰到了一堆麻烦。我希望我的博文能给reduce函数做一个较好的解释。

我想Redux是reduce应用非常好的一个范例。Redux关注的重心是，应用的全局 state， 应用的全局 state 是通过没有关联的 action 和应用中具备 (state, action) => state 形式的 reducer 进行更新的。它将我们琐碎的日常任务中具备相同概念部分进行了抽象，但是我们这里并不是要介绍Redux。

不可变的数据

循环可以说是绝大多数程序员都会学习到的最基本的控制单元：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 
// 陈旧的JavaScript语法
var items = [1, 2, 3, 4];
for (var ii = 0; ii < items.length; ii++) {
    var item = items[ii];
    // do something
}

// 尝试新的语法的人们
items.forEach((item) => {
    // do something
})

1
2
3
4
 
# Python
items = [1, 2, 3, 4]
for item in items:
    # Do something

1
2
3
4
5
 
# Ruby
items = [1, 2, 3, 4]
items.each do |item|
    # Do something
end

1
2
3
4
5
 
// Java
int[] items = new int[]{1, 2, 3, 4};
for(int item: items) {
  // Do something
}

我们绝大多数人，都是在写下第一个_Hello World_程序后，就很快接触到了循环，并且一直在日常工作中使用。但是循环是命令式语言中遍历的设计理念。

然而，当我们刚刚开始使用函数类语言时，我们想全面享受不可变数据的带来的优势，就可能要立刻面对一个问题，如何变更不可变数据集合中的数据。因为循环体并没有使用返回值，而是直接通过副作用完成操作，但是不可变数据集合的设计就是为了不使用这种具有副作用的操作。我们依然可以在函数范式中使用for续完，但是它有些不同就是了，并且程序员非常抗拒在使用不可变数据时，使用for循环，考虑下面这个例子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
 
// 我们在javascript中使用immutable库
import { List } from 'immutable';

const myIds = List(["1", "2", "3", "4"]);
const myObjects = Map({
  1: someObject1,
  2: someObject2,
  3: someObject3,
  4: someObject4,
  // ...
})

//给定一个id列表，返回一个对象列表
const myListOfObjects = // ...?

我们或许以前看过这种东西，或许我们很幸运，可以使用带有列表推导式2的语言，例如python

1
2
3
4
 
my_ids = [1, 2, 3, 4]
my_objects = {1: obj1, 2: obj2, 3: obj3, 4: obj4}

my_list_of_objects = [my_objects[id] for id in my_ids]

或者我们可以使LoDash3或者其它的方式进行同样的操作。但是这不是这篇博文想表达的重点。本篇文章的重点是_任何可以使用循环的地方，我们都可以使用reduce表达式进行替换_:

1
2
3
4
5
 
// Javascript 
const myListOfObjects = myIds.reduce(
  (objs, obj) => objs.push(myObjects.get(obj)),
  List()
)

让我们深入一点。

什么是reduce

在这篇维基百科的文章中它被称为“fold”，但是我发现，在绝大部分语言中它会被称为”reduce“。对某些人来说，把它被称为“aggregate”会更清晰一些。

好了，不管我们怎么称呼它，reduce总是要接受有两个参数的函数（这里我们给这个函数命名为_f_)，一个初始值以及一个数据集合。reduce会使用初始值和集合中的第一个元素调用f，然后再用这个调用的结果和集合中的第二个元素再次调用f，以此类推，直到遍历了集合中所有的值。如何使用reduce的“一目了然”的例子就是对列表元素求和。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
 
const plus = (result, num) => result + num;

const ten = [1, 2, 3, 4].reduce(plus, 0)

/* Equivalent to:

  plus(plus(plus(plus(0, 1), 2), 3), 4)
= plus(plus(plus(1, 2), 3), 4)
= plus(plus(3, 3), 4)
= plus(6, 4)
= 10
*/

让我再次强调下，reduce需要三个部分：

  • 一个数据集合，通常是一个列表或者数组，或者其它可以遍历的数据结构
  • 一个初始值，集合中每个元素都会包含在其中
  • 一个聚合函数，接受两个参数并把它们进行聚合。

我们假设，我们总是有一个数据集合-让我们继续看看其它两个参数吧。

选择一个初始值

我们通常希望初始值是我们结果类型的单位元。单位元是针对我们的二元操作（在这种情况下，这里是我们的聚合函数）。在给定运算操作，单位元就是一个可以和任意值进行聚合后给不改变该值的一个值。

我们用数字为例子,0对于+操作就是单位元，因为0 + 任意数字A都是返回数字A。当然很多语言重载了+操作，让它在不同的数据类型上有不同的含义：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
 
# Python写伪代码还不错

# Strings
"Hello World" + "" == "Hello World"

# Lists
[1, 2, 3, 4] + [] == [1, 2, 3, 4]

# Booleans

# `true` 是 `and` 的单位元
true and true == true
false and true == false

# `false` 是 `or` 的单位元
true or false == true
false or false == false

由于reduce经常会与加法类似的操作一起使用，因此它的初始值也经常被成为“零值”。但是，请记住，我们要考虑是什么操作。如果我们相对列表求积，那么我们就需要使用1作为单位元。

当然我们的初始值，可以不是标量，我们可以使用一个复杂的数据结构来作为初始值，它可以使用其它数据结构进行更新。

设计一个聚合函数

聚合函数需要两个参数。第一个参数，永远都是聚合值，第二个参数是列表中的下一个元素。它的返回值会在下一次遍历中使用，所以它必须和第一个参数是同类型的。

那么，我为什么说reduce就是一个非常基本的操作？这是因为reduce是为了解决下面问题而存在的工具

给定数据集X，我们计算出Y

为了更进一步说明，事实上我们可以使用reduce来实现其它高阶运算：

1
2
3
4
5
6
 
// Javascript

const map = (f, coll) => coll.reduce(
  (out, val) => [...out, f(val)],  // Combining function
  []  // Initial value
);

我们也可以实现filter

1
2
3
4
 
const filter = (f, coll) => coll.reduce(
  (out, val) => (f(val) ? [...out, val] : out),
  []
);

我还可以举出很多例子，请看这两篇文章Reducers explained (through Python)和 Lose the Loops。

reduce的缺陷

当然任何工具都是有它不擅长的领域。reduce是一个从数学中剥离出来的工具，它和其它许多函数工具一样，其优势在于其概念简单，易于理解和使用，当然它的缺点在于概念和机器之间的边界。（计算机中的时空问题）。

reduce最大的缺陷，它期望是使用不可变数据集来做参数，这是两种数据中较慢的哪一种。例如，在JavaScript数组上使用“拼接“操作（[...out, val]），这样每次调用都会创建一个全新的数组作为结果，这很可能就是性能瓶颈。使用immutable或者mori这种类库对此情况会有很大的改善，他们都利用较为新颖的数据结构共享算法来减少内存使用。这两个库都使用持久数据集合来实现共享数据结构，根据以往的经验，在写入这些数据结构时和相同的可变数据结构比，会慢上2–4倍。从好的方面想，在使用不可变数据结构时，我们可以充分享受这些数据结构的优势，因为它们的不可变性，因此不会发生不可控的数值改变。

reduce的另一个性能缺陷就是，不能提前退出。我最喜欢的全栈语言Clojure， 通过使用标签函数reduced来解决这个问题，将给定的值标记为reduced，并通过reduced?来检查这一标记并提前退出，从而克服这一问题。然而，大多数语言并没有给我们提供变量元数据这一特性供让我们很容易的完成这一操作，即便这些语言提供这一特性，它们也并没有将这一特性包含在他们的标准中，因此这就会存在很多毫无关联的实现方式。当然我们可以变相的使用下异常或者类似的机制绕过这一限制，但是我并不建议这样做。

总结

就如同我前面所提到的那样，reduce的优势之一就是它的概念清晰，简单粗暴。我的意思是，它是一个有用的框架，可以将任务分解成几个小部分。特别是“聚合函数”可以是一个非常通用的操作，什么时候都可以用的得心应手，例如：

1
2
3
4
5
6
7
8
 
const addLineToInvoice = (invoice: Invoice, line: InvoiceLine) => {
    return {
        ...invoice,
        totalHours: invoice.hours + line.hours,
        total: invoice.total + line.total,
        lines: [...invoice.lines, line],
    }
}

我们可以将它和reduce一起使用，但是我们也可以考虑，直接中用该函数为我们的收据增加新的一行。

我的观点是，即便我们不是每天都会用到reduce，但是我们理解它的能力时候，这就会让我们有很大的收获。如果你认为我是对的，那么别客气，感谢阅读该博文。

参考

1 高阶函数

2 列表推导式

3 LoDash英文 & LoDash中文

译注

使用函数类型的语言工作了很多年，经常使用reduce，但是很少深入的去想reduce背后是什么，这篇博文虽然很简单，但是却给我带来了很多新的想法。例如将Clojure的reduced移植到Erlang中使用。或者将很多业务共有的数据字段和数据变更操作，整理成一个业务无关的小库，从而减少自己日常工作量等等。

不管怎么说，写代码更多时候是要考虑我们在写什么，而不是我们写出来了什么。