Transducer:一种可组合的数据处理模式
先从一个普通的数组处理开始。
同样的逻辑,也可以写成一个 for 循环。三步操作还在,只是被放进了一次遍历里。
链式写法的好处是结构清楚:map、filter、slice 各自表达一个独立步骤。
for 写法的好处是执行直接:结果够了就可以返回,不需要继续处理后面的元素。
要解决的问题就是:能不能保留 map/filter/slice 这种可组合的写法,同时让执行过程像 for 一样按需推进。
先把 map 写开。它看起来只是一个函数,但里面其实包含了遍历和收集。
filter 也类似,只是“处理”变成了一个判断。
两个实现的骨架几乎一样:遍历输入、维护结果、把需要的值放进结果里。不同的只是“遇到一个元素时要做什么”。
下一步把“收集集合中的元素”这件事抽出来。
这里的 append 就是前面代码里的“收集”:给它一个累积结果 acc 和当前元素 x,它把 x 放进 acc,再返回 acc。
reduce 则固定了“遍历”的部分。它不关心每个元素具体怎么处理,只是在每次遍历时调用一次 step(acc, x)。
试试用它写 map 和 filter。
这说明 reduce 不只是“求和”的工具。只要换掉传进去的 reducer,它就能表达 map、filter,以及更一般的遍历时累积逻辑。
那 take 呢?它要在拿够之后停下来,而 reduce 现在会把输入吃完。先给 reduce 加一个能停的机制——类似 break。
上面这一套(reduced / isReduced / reduce / append)后面要反复用——挂到 globalThis 上,后面的 cell 直接解构出来就行。
回到一开始的例子:
用一个 reducer 写:
想让三步彼此独立——拆成三个 reducer:
三步独立了,但合不回去——三个 reducer 塞不进一次 reduce。
组合函数的常用办法是 compose。但 compose 要的是 a => b(单参数);reducer 是 (acc, x) => acc(双参数)——对不上。
先看 compose 在 a => b 上:
reducer 自己不是 a => b。但 reducer => reducer 是——输入 reducer,输出 reducer:
reducer => reducer 这种形状,就叫 transducer。plusOne 是一个 transducer。
写一个 mapping transducer:
再写一个 filtering transducer——参数换成判断:
用 compose 把它们串起来:
把这套动作起个名字。
还差 take——也做成一个 transducer:
到这里,开头那个目标就完成了:保留 .map.filter.slice 那种可组合的写法(compose 一串 transducer),同时让执行像 for 一样按需推进(taking 拿够就停,输入不必扫完)。
接下来再看一个类似的例子——从 range(1000) 取前 3 个含 7 的素数:
taking 拿够 3 个就停,所以 range(1000) 实际只读了几十个。
源头甚至可以是无限的——换成一个不带上限的 generator 也照跑:
换一个无限源——Fibonacci,再把”含 7 的素数”叠上去:
输出不一定是数组——换种收法。
换一种迭代方式——把上面 Fibonacci 那个例子换成异步:fibs 改成 async generator,reduce 改成 asyncReduce。但 xf 一字未改:
迭代方式(同步 / 异步)变了,使用方式(mapping / filtering / taking 串)不变——pipeline 跟迭代解耦了。
延伸阅读
-
Rich Hickey, Transducers are Coming。Clojure 1.7 引入 transducer 时的官方公告,解释 transducer 这个概念为什么必要、它和 reducer / sequence operation 的关系。
-
Clojure Reference, Transducers。Clojure 官方文档,覆盖了核心的
transduce/into/eduction接口、stateful transducer、early termination 等本文延伸的话题。