从 Clojure sequence 到 transducer
Table of Contents
sequence, map, filter & reduce
Clojure 很多算法/函数基于 sequence 定义. sequence 是一个逻辑列表，其接口很简单1：
;;; (first coll)(first '(0 1 2)) ;=> 0;;; (rest coll)(rest '(0 1 2)) ;=> (1 2);;; (cons item seq)(cons 0 '(1 2)) ;=> '(0 1 2)
诸如 map, filter 之类的函数默认实现基于 sequence 接口，比如 map 和 filter 最天真的实现方式如下：
;;; 这个实现假设你知道;;; 1. (seq coll) 在 coll 为空返回 nil (是逻辑 false);;; 2. nil 是空 sequence, 即 (cons 1 nil) -> '(1)(defn map [f coll](when (seq coll)(cons (f (first coll)) (map f (rest coll)))))(defn filter [f coll](when (seq coll)(if (f (first coll))(cons (first coll) (filter f (rest coll)))(recur f (rest coll)))))
类似的 reduce 可以实现成：
(defn reduce([f coll](assert (seq coll))(reduce f (first coll) (rest coll)))([f val coll](if (seq coll)(recur f (f val (first coll)) (rest coll))val)))
为什么把 reduce 的实现单独列出来？它特殊的点在于 map 和 filter 可以基于它实现：
(defn reverse [coll](reduce (fn [r v] (cons v r)) nil coll))(defn map [f coll](reduce (fn [r v] (cons (f v) r)) nil (reverse coll)))(defn filter [f coll](reduce (fn [r v] (if (f v) (cons v r) r)) nil (reverse coll)))
因此，可以说 reduce 是某种更为基础的操作。可以看出 reduce 函数实际为 map 和 filter 这种相对“上层”的操作提供了遍历数据的接口。
既然
reduce 函数可以用于封装对于数据的遍历，我们可以直接定义一个
CollReduce 协议：
;; 取自 clojure.core.protocols(defprotocol CollReduce(coll-reduce [coll f] [coll f val]))
这样我们可以反转下思维模型，我们不是通过 sequence 接口实现了 reduce
函数，而是为 sequence 数据类型实现了
CollReduce 协议2。
这个说法的变化不只是文字游戏。观察 sequence 接口能看出 sequence
数据是有序的，你需要通过 (first d), (first (rest d)), (first
… (rest d)) 去依次遍历所有条目。而
CollReduce
协议并不隐含这一点，即你可以为底层数据实现更为高效的遍历逻辑（比如并行的遍历）。
Reducing 函数 & Reducer
上面定义了 CollReduce 协议之后，reduce
函数可以直接定义成：
(defn reduce[f init coll] (clojure.core.protocols/coll-reduce coll f init))
这样，对于数据的 reduce 依赖于我们对于特定数据给出的
CollReduce 协议实现.
Reducing 函数即上面我们传给
reduce 函数的那个函数，它的形状是：
(f result input) -> new-result
对于 reducing 函数的转换函数（一般用
xf 表示）形状如下：
(xf reducing-fn) -> reducing-fn
正如实现了 sequence 接口 (first, rest, cons) 的数据是 sequence
数据一样，实现了 CollReduce 协议的数据是一个 reducible
的抽象数据类型。对于 sequence, 我们期望 map/filter
等函数返回一个逻辑的集合，对于 reducible 我们也可以对其应用 reducing
函数以得到一个新的 reducible：
(defn reducer([coll xf](reifyclojure.core.protocols/CollReduce(coll-reduce [_ f1 init](clojure.core.protocols/coll-reduce coll (xf f1) init)))));; map 基于 sequence 接口 (vector 实现了 sequence 接口) 实现, 应用于 sequence,;; 得到一个新的 sequence(reduce + 0 (map inc [1 2 3 4]));; reducer 应用于 reducible (vector 实现了 CollReduce 协议), 得到一个新的;; reducible 数据(reduce + 0 (reducer [1 2 3 4](fn [reducing-fn](fn [result input](reducing-fn result (inc input))))))
将上面这个针对 reducible 数据每个条目执行特定操作的 reducing 转换函数 (xf) 做一下抽象可以得到：
(defn mapping [f](fn [reducing-fn](fn [result input](reducing-fn result (f input)))))(reduce + 0 (reducer [1 2 3 4] (mapping inc)));;; 针对 reducible 数据的 map 实现:(defn rmap [f coll] (reducer coll (mapping f)))(reduce + 0 (rmap inc [1 2 3 4]))