其实第一次听说 transducer 的概念，是在某个周末时间学习 Clojure 的时候。一开始觉得概念很复杂，因此就没有深入了解，内部的实现机制并不清楚。

直到后来尝试写一个 JavaScript 的函数式编程的函数库时，才做了一番功课去研究。

本文就是记录我对学习过程的思考和结果。

我们不讲概念，而是从一个简单的问题开始。

问题

假设你现在在检查上个月的开支清单，里面的条目大概如下：

1
const list = [
2
  { type: '早餐', amount: 12 },
3
  { type: '午餐', amount: 18 },
4
  { type: '咖啡', amount: 19 },
5
  { type: '零食', amount: 8 },
6
  { type: '晚餐', amount: 22 },
7
  { type: '水果', amount: 20 },
8
  { type: '早餐', amount: 12 },
9
  { type: '午饭', amount: 20 },
10
  { type: '咖啡', amount: 24 },
11
  { type: '晚饭', amount: 21 },
12
]

如果你现在想知道喝了多少钱的咖啡，按照以往的经验，我们可能会这么做：

1
const filterCoffee = item => item.type === '咖啡'
2
const getAmount = item => item.amount
3
const add = (a, b) => a + b
4

5
list
6
  .filter(filterCoffee)
7
  .map(getAmount)
8
  .reduce(add, 0)
9

10
// 结果为 43

这是一个非常典型的数据处理过程，我们现在来分析，这个过程发生了什么。

列表处理：过滤数据

1
.filter(filterCoffee)
2

3
// 结果为
4
// [
5
//   { type: '咖啡', amount: 19 },
6
//   { type: '咖啡', amount: 24 },
7
// ]

总共迭代了 10 个条目，逐个检查 type
创建了一个新列表，存放滤出的 2 个符合条件的条目。

列表处理：映射数据

1
map(getAmount)
2
// 结果为
3
// [
4
//   19,
5
//   24,
6
// ]

对 filter 的结果，进行了迭代处理，总共处理了 2 个条目
创建了一个新列表，存放得到的 2 个金额数值。

执行计算：求和

1
reduce(add, 0)
2
// 结果为 43

对 map 的结果，进行了累加，总共处理了两个条目
得到一个数值 43

以上过程，我们可以总结出一些特点：

对列表的每项操作都是独立连续完成的，做完一项，再进行下一项。
每一次操作，都创建自己的结果存储（中间数据），传递给下一个操作作为输入。

这中间存在着什么问题？

中间数据算一个问题，我们并不关心计算的中间过程，这些中间生成的过程数据，只是我们使用这种流式的实现方式不得已产生的。那么，能否消除这些中间数据的创建呢？使用本文的主题，transducer 即可改善这一点。

但是，为了讲清楚，暂时先不展开，我们还需要理解一些铺垫的概念。

reduce

让我们重新审视下 reduce 函数。

reduce 可能是我们常用的列表处理方法中，最复杂的一个了。它的回调除了接受每个列表元素，还有个特别的“累积值”，而且除了回调，还接受一个初始值（非必须）。它可以：

可以对列表做完整的遍历，访问到所有元素（current）及其 index
提供（累积值）acc 作为操作结果的存取变量

实际上，reduce 这么复杂，是因为，它其实是将对列表的递归操作模版化了。所以，通过递归或者迭代列表能做到的事情，用 reduce 一样能做。

有了这个基础之后，我们就可以基于 reduce 来做各种各样的列表操作。

看一个例子：

1
list.map(item => item.type)
2
// ["早餐", "午餐", "咖啡", "零食", "晚餐", "水果", "早餐", "午饭", "咖啡", "晚饭"]

我们如果使用 reduce 来实现同样的行为，可以这么做：

1
list.reduce((acc, item) => (acc.push(item.type), acc), [])
2
// ["早餐", "午餐", "咖啡", "零食", "晚餐", "水果", "早餐", "午饭", "咖啡", "晚饭"]

上面两种写法，它们表达的含义是一样的：

将数据做变换（提取 type ）
返回所有数据变换后的结果列表

结论是，reduce 可以做到 map 能做到的事情。

再看一个例子：

1
list.filter(item => item.type === '咖啡')
2
// [{type: "咖啡", amount: 19}, {type: "咖啡", amount: 24}]

改用 reduce 实现：

1
list.reduce((acc, item) => (item.type === '咖啡' ? (acc.push(item), acc) : acc), [])

同样，这两段代码也是一样的含义

使用谓语 ( type 为“咖啡” ) 对数据做过滤
返回所有过滤的结果列表

同样可以得出结论，reduce 可以做到 filter 能做到的事情。

综合上面两个例子，我们可以找出一个共同点，如果使用 reduce 来做列表操作，所有功能实现的核心，都是由两个子部分组成的：

数据加工
结果处理

对于 map 来说，数据加工，就是将数据的映射方法，作用到每个元素上；对于 filter 来说，就是使用谓语来检查数据是否需要累积。而结果处理，则是将加工后的结果添加入结果列表中。

扩展一下，通过同样的思路，我们可以将所有常用的列表操作，都改成使用 reduce 来做。

上面铺垫这么多，就是为了得出一个结论，我们可以借助 reduce ，使用统一的方式来做列表操作，这种统一，是下一步实现的前提。

现在我们先回到开头的例子，我们统一使用 reduce 来做列表操作，可以将代码改成：

1
const filterCoffeeReducer = (acc, item) => (item.type === '咖啡' ? (acc.push(item), acc) : acc)
2
const mapAmountReducer = (acc, item) => (acc.push(item.amount), acc)
3
const sumReducer = (acc, amount) => (acc + amount)
4

5
list
6
  .reduce(filterCoffeeReducer, [])
7
  .reduce(mapAmountReducer, [])
8
  .reduce(sumReducer, 0)

transducer

上面使用流式的函数处理列表过程，每一步变换，其实可以抽取出来。在数据变换环节中，组合这些变换操作成一个单独的变换操作，最后将这个组合而成的变换加工出来的数据，累积到结果上，从而一步到位，无需生成中间列表数据就获得最终结果。这就是 tansducer 做的事情。

那么要如何来抽取组合变换逻辑呢？

我们手工做一次改写，将 filterCoffeeReducer 和 mapAmountReducer 部分组合起来：

1
list
2
  .reduce((acc, item) => (item.type === '咖啡' ? (acc.push(item), acc) : acc), [])
3
  .reduce((acc, item) => (acc.push(item.amount), acc), [])
4
  .reduce((acc, amount) => (acc + amount), 0)

如果使用 transducer 来解决问题，伪代码描述，大概是这样的：

1
result = list.transduce(
2
  Transformer,
3
  数据累积方法,
4
  列表数据
5
)

其中，Transformer，即变换操作的方法，描述如何将一组操作用于变换原始数据到可以被最后累积处理数据。对应上面的例子，就是 filter 和 map 的逻辑部分：

检查是否 “咖啡”
转换成金额

Transformer 将这两个操作应用于每个原始数据，直接一步到位，得到可以最后用于计算的金额数据。

数据累积方法，则是最后如何 “累积” 上一环节转换的结果。对应上面的例子，就是 reduce 部分的逻辑：

累加金额

怎么实现

可以看我 github 中的一个简单的 transduce 实现。

（由于比较复杂，暂时不展开解释，有兴趣就看代码跟注释吧…）

下面贴一些核心的代码：

1
// 协议
2
const INIT = '@@transducer/init'
3
const RESULT = '@@transducer/result'
4
const STEP = '@@transducer/step'
5
const REDUCED = '@@transducer/reduced'
6
const VALUE = '@@transducer/value'
7
const ITERATOR = '@@iterator'
8

9
// reducer，即每一步执行 reducing 的函数
10
interface Reducer {
11
  (accumulator, currentValue): any
12
}
13

14
interface Reduced<T> {
15
  [VALUE]: T
16
  [REDUCED]: boolean
17
}
18

19
interface Transformer {
20

21
  // 返回初始化值
22
  [INIT]: () => any
23
  // 返回最终结果
24
  [RESULT]: (accumulator: any) => any
25
  // reducer
26
  [STEP]: (accumulator: any, currentValue: any) => any
27
}
28

29
interface Transducer {
30
  (tarnsformer: Transformer): Transformer
31
}
32

33
interface _Iterator {
34
  [ITERATOR]: (value: any) => any
35
}
36

37
const ITER_SYMBOL = typeof Symbol !== 'undefined' ? Symbol.iterator : ITERATOR
38

39
// Transformer 的基类
40
class BaseTransformer implements Transformer {
41
  [INIT]() {
42
    throw new Error('init not implemented')
43
  }
44
  [STEP](accumulator, currentValue) {
45
    throw new Error('step not implemented')
46
  }
47
  [RESULT](accumulator) {
48
    return accumulator
49
  }
50
}
51

52
function _reduced<T>(obj: T | Reduced<T>): Reduced<T> {
53
  if (obj && obj[REDUCED]) {
54
    return obj as Reduced<T>
55
  }
56
  return { [VALUE]: obj as T, [REDUCED]: true }
57
}
58

59
// 将普通 reducer 包装成 transformer
60
class XfWrap extends BaseTranducer {
61
  constructor(private reducer: Reducer) {
62
    super()
63
  }
64
  [STEP](accumulator, currentValue) {
65
    return this.reducer(accumulator, currentValue)
66
  }
67
}
68

69
class XMap extends BaseTransformer {
70
  constructor(private fn, private transformer) {
71
    super()
72
  }
73
  [STEP](accumulator, currentValue) {
74
    return this.transformer[STEP](accumulator, this.fn(currentValue))
75
  }
76
}
77

78
class XFilter extends BaseTransformer {
79
  constructor(private predicate, private transformer) {
80
    super()
81
  }
82
  [STEP](accumulator, currentValue) {
83
    return this.predicate(currentValue) ? this.transformer[STEP](accumulator, currentValue) : accumulator
84
  }
85
}
86

87
function _isArrayLike(test: any): boolean {
88
  if (Array.isArray(test)) return true
89
  if (!test || typeof test.length !== 'number' || typeof test === 'string') return false
90
  if (test.length === 0 && typeof test !== 'function') return true
91
  if (test.length > 0) return test.hasOwnProperty(0) && test.hasOwnProperty(test.length - 1)
92
  return false
93
}
94

95
// curry 见上一篇的实现
96
const mappingTransducer = curry(function(
97
  fn: (value: any) => any, transformer: Transformer
98
): Transformer {
99
  return new XMap(fn, transformer)
100
})
101

102
const filterTransducer = curry(function transducer(
103
  pred: (value: any) => boolean,
104
  transformer: Transformer
105
): Transformer {
106
  return new XFilter(pred, transformer)
107
})
108

109
// 包装 reducing function 为 Transformer
110
function wrap(reducer: Reducer | Transformer): Transformer {
111
  return typeof reducer === 'function'
112
    ? new XfWrap(reducer)
113
    : reducer
114
}
115

116
function _arrayReduce(tarnsformer, initialValue, iterable) {
117
  const size = iterable.length
118
  const stepFn = tarnsformer[STEP].bind(tarnsformer)
119
  let accumulator = initialValue
120
  for (let index = 0; index < size; index += 1) {
121
    const current = iterable[index]
122
    accumulator = stepFn(accumulator, current)
123
    if (accumulator && accumulator[REDUCED]) {
124
      accumulator = accumulator[VALUE]
125
      break
126
    }
127
  }
128

129
  return tarnsformer[RESULT](accumulator)
130
}
131

132
function _iterableReduce(tarnsformer, initialValue, iterable) {
133
  let step = iterable.next()
134
  const stepFn = tarnsformer[STEP].bind(tarnsformer)
135
  let accumulator = initialValue
136
  while (!step.done) {
137
    accumulator = stepFn(accumulator, step.value)
138
    if (accumulator && accumulator[REDUCED]) {
139
      accumulator = accumulator[VALUE]
140
      break
141
    }
142
    step = iterable.next()
143
  }
144

145
  return tarnsformer[RESULT](accumulator)
146
}
147

148
function _methodReduce(tarnsformer, initialValue, object, methodName) {
149
  let accumulator = initialValue
150
  return tarnsformer[RESULT](
151
    object[methodName](tarnsformer[STEP].bind(tarnsformer), accumulator)
152
  )
153
}
154

155
export default function _reduce(
156
  // Reducer | Transformer
157
  tarnsformer,
158
  initialValue,
159
  // Array<any> | ArrayLike<any> | Iterable<any> | Iterator<any> | _Iterator
160
  iterable
161
) {
162
  if (typeof tarnsformer === 'function') {
163
    tarnsformer = wrap(tarnsformer)
164
  }
165

166
  if (_isArrayLike(iterable)) {
167
    return _arrayReduce(tarnsformer, initialValue, iterable)
168
  }
169

170
  if (iterable[ITER_SYMBOL] != null) {
171
    const iterator = iterable[ITER_SYMBOL]()
172
    return _iterableReduce(tarnsformer, initialValue, iterator)
173
  }
174

175
  if (typeof (iterable as any).next === 'function') {
176
    const iterator = iterable
177
    return _iterableReduce(tarnsformer, initialValue, iterator)
178
  }
179

180
  if (typeof (iterable as any).reduce === 'function') {
181
    return _methodReduce(tarnsformer, initialValue, iterable, 'reduce')
182
  }
183

184
  throw new TypeError('reduce: list must be array or iterable')
185
}
186

187
function transduce(transducer, reducer, initialValue, iterable) {
188
  const transformer = wrap(reducer)
189
  return _reduce(transducer(transformer), initialValue, iterable)
190
}

协议，实现更多 transducer 例子

实际上，关于在 JavaScript 中实现 transduce，已经有一个主流遵守的协议了，感兴趣可以看看一些典型的实现，例如 Ramda.js 的相关代码。

全文完（待有空会补充更多细节，展开阐述）

JavaScript 实现 Transducers

问题

reduce

transducer

怎么实现

协议，实现更多 transducer 例子