(define lambdacraft)

Transducer:一种可组合的数据处理模式

· typescript, functional-programming

loading... 尚未启动

先从一个普通的数组处理开始。

同样的逻辑,也可以写成一个 for 循环。三步操作还在,只是被放进了一次遍历里。

链式写法的好处是结构清楚:mapfilterslice 各自表达一个独立步骤。

for 写法的好处是执行直接:结果够了就可以返回,不需要继续处理后面的元素。

要解决的问题就是:能不能保留 map/filter/slice 这种可组合的写法,同时让执行过程像 for 一样按需推进。

先把 map 写开。它看起来只是一个函数,但里面其实包含了遍历和收集。

filter 也类似,只是“处理”变成了一个判断。

两个实现的骨架几乎一样:遍历输入、维护结果、把需要的值放进结果里。不同的只是“遇到一个元素时要做什么”。

下一步把“收集集合中的元素”这件事抽出来。

这里的 append 就是前面代码里的“收集”:给它一个累积结果 acc 和当前元素 x,它把 x 放进 acc,再返回 acc

reduce 则固定了“遍历”的部分。它不关心每个元素具体怎么处理,只是在每次遍历时调用一次 step(acc, x)

试试用它写 map 和 filter。

这说明 reduce 不只是“求和”的工具。只要换掉传进去的 reducer,它就能表达 mapfilter,以及更一般的遍历时累积逻辑。

take 呢?它要在拿够之后停下来,而 reduce 现在会把输入吃完。先给 reduce 加一个能停的机制——类似 break

上面这一套(reduced / isReduced / reduce / append)后面要反复用——挂到 globalThis 上,后面的 cell 直接解构出来就行。

回到一开始的例子:

用一个 reducer 写:

想让三步彼此独立——拆成三个 reducer:

三步独立了,但合不回去——三个 reducer 塞不进一次 reduce

组合函数的常用办法是 compose。但 compose 要的是 a => b(单参数);reducer 是 (acc, x) => acc(双参数)——对不上。

先看 composea => b 上:

reducer 自己不是 a => b。但 reducer => reducer 是——输入 reducer,输出 reducer:

reducer => reducer 这种形状,就叫 transducerplusOne 是一个 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 等本文延伸的话题。