Coffee Break Clojure, Transducer

在第三期《 只用圆括号怎么够？ 》里，我讲到了 reduce。

先来简单复习一下：reduce 最少接收两个参数，形如 (reduce f coll)，其中 f 是接收两个参数的函数，形如 (f x y)；reduce 遍历 coll 中的每个元素，先对前两个元素求 (f a1 a2)，然后求 (f (f a1 a2) a3)，以此类推。

(f x y) 这种函数叫作归约函数（reducing function）。

归约、Fold、高阶函数

之前我们用作示例的代码如下：

(def numbers '(1 43 231 23 99))

(reduce + numbers)
;; => 397

+ 可以视作归约函数，因为他可以这样调用：(+ x y)。当我们对上述代码进行求值时，主要执行了以下步骤：

1. (+ 1 43) 得到 44
2. (+ 44 231) 得到 275
3. (+ 275 23) 得到 298
4. (+ 298 99) 得到 397

使用 + 作为归约函数，对 numbers 进行归约（reduce），就实现了累加。

在函数式编程里，归约（reduce）也叫作累积（accumulate）、聚集（aggregate）、压缩（compress）和注入（inject），不过更常见的名字是折叠（fold）。折叠分左折叠（foldl）和右折叠（foldr）。

还记得第三篇讲过的 Cons 和 Lisp 的列表构造方式吗？Fold 的结构就像是函数版本的 Cons。

(reduce f [1 2 3 4 5])
;; 等价于
(f (f (f (f 1 2) 3) 4) 5)

(list 1 2 3 4 5)
;; 等价于
(cons 1 (cons 2 (cons 3 (cons 4 (cons 5 nil)))))

Clojure 的 reduce 默认是左折叠，即 foldl：

要在 Clojure 里实现右折叠，只能把待操作的列表倒序：

(reduce f (reverse [1 2 3 4 5]))
;; 等价于
(f (f (f (f 5 4) 3) 2) 1) ; 实际上还是左折叠
;; 如果 f 和 + 一样满足交换律，就等价于
(f 1 (f 2 (f 3 (f 4 5))))) ; 等价于右折叠

折叠中的 f 本身也可以是折叠。还记得 into 吗？

(into [1 2 3] [4 5])
;; => [1 2 3 4 5]

;; 等价于
(reduce conj [1 2 3] [4 5]) ;; 这里的 reduce 以 [1 2 3] 为初始值
 ;; 如果没有初始值，就会用第一个元素做初始值
;; 等价于
(conj (conj (conj [1 2 3]) 4) 5)

如果要打平一个向量，比如把 [[1] [2 3] [4 5]] 变成 [1 2 3 4 5]，就可以用 into 作为归约函数（reducing function），也就是把 (reduce conj ...) 作为 reduce 的 f。

(reduce into [[1] [2 3] [4 5]])
;; => [1 2 3 4 5]

;; 等价于
(reduce #(reduce conj %1 %2) [[1] [2 3] [4 5]])
;; 等价于
(reduce conj (reduce conj [1] [2 3]) [4 5])
;; 等价于
(conj (conj (conj (conj [1] 2) 3) 4) 5)

在 Clojure 中，能够被放在 reduce 里使用的函数就叫作归约函数（reducing function）。这个概念与函数式编程和 Lambda 演算的高阶函数（Higher-order function）有关，据说微积分中的导数也算一种高阶函数，但我这篇文章不是讲数学的（我也不会数学），所以就点到为止。

改造归约函数

总结一下，归约函数就是这样的一类函数：

(f result input) -> new result

这样的函数可以相互嵌套使用，不过一般传给 reduce 用。

接下来要引入一种新的函数，我没有找到中文译名，暂且称作变约函数（transducer）。它长这样：

(t (f result input)) -> (new-f result input)

Transducer 接收一个归约函数，返回新的归约函数。

返回函数的函数可能有些抽象，但是在 Clojure 中很常见。我举几个例子解释 Transducer 的用法。

假设我们要对向量自增，然后再累加，就要这样写：

;; 下面这个函数先是自增 [1 2 3 4] 得到 [2 3 4 5]
;; 然后再对 [2 3 4 5] 进行累加
(reduce + 0 (map inc [1 2 3 4]))
;; => 14

能不能让 + 这个归约函数，在把之前的结果和下一个元素累加起来之前，先给要累加的元素 + 1？也就是说，我们不用遍历一遍列表，生成新的、自增后的列表，然后再累加这个列表，而是在累加的过程中就把自增的操作也做了。

我们可以这样写：

;; 下面这个函数用 (map inc) 这个 Transducer
;; 把 + 这个归约函数，转换成了新的归约函数
;; 这个新的归约函数的作用是：先给单个元素 +1，然后再累加
(reduce ((map inc) +) 0 [1 2 3 4])
;; => 14

这里我们看到了 Clojure 1.7 引入的 map 的新用法。一般而言，(map f coll) 的作用是把 f 作用在 coll 中的每一个元素上，然后生成新的元素。

而 (map inc) 则是生成了一个 Transducer，我们把 + 作为这个 Transducer 的参数传入，得到了新的归约函数。也就是说，我们将 (map inc) 和 + 组合，构造了新的数据转换算法。 对集合中的元素 inc，然后再折叠 + 实现累加。

这种转换与具体类型无关，与惰性无关，与执行顺序也无关，只是纯粹的算法。非常便于复用。

将具体类型与转换算法解耦

Clojure 的哲学是简洁，这点并不只是体现在语法（syntax）上，还体现在语义（semantics）和语言的设计上。Rich Hickey 在《 Simple Made Easy 》里讲到，简单（simple）的东西就是不和其他东西交织（complect）在一起的东西。

Java 类不简单，因为它既是命名空间，又是数据结构，还定义了数据上的操作——类把三个东西交织在了一起。反观 Clojure，命名空间是单独的概念。

标照 Rich 本人对简单的定义，标准库里的 map、filter、reduce 等操作序列的函数，都不够简单，因为他们不仅涉及做什么操作（what to do），还涉及了怎么做（how to do it）——预设了惰性，预设了数据操作的顺序（序列都是从前往后线性遍历的），预设了数据的表示方式（返回的是序列）。

如果 map、filter、mapcat 等函数，能够与数据类型（序列）解耦呢？也就是说，如果 map 只定义做什么操作（what to do） ，把怎么做（how to do it）交给其他组件呢？

比方说，map 可以这样实现：

(defn map [f]
 (fn [f1]
 (fn [result input]
 (f1 result (f input)))))

这个 map 是构造 Transducer 的函数，它接收函数 f，返回了一个返回函数的函数。我们之前看到的 (map inc) 就返回了一个 Transducer。

这就是对做什么（what to do）的定义。

reduce 则定义了怎么做（how to do it），因为 reduce 是对序列的操作，而且是具有惰性的，返回值是惰性序列。所以把 reduce 的怎么做（惰性地、顺序地、当作序列执行左折叠）与 ((map inc) +) 的做什么（“元素自增后再累加”）组合，就得到了完整的数据操作。

如果不想要折叠呢？我能不能直接用 (map inc) 累加元素？

将 sequence（输入和输出数据为序列、惰性、顺序操作）与 (map inc)（“自增集合里所有的元素”）这些要素组合起来，才能得到完整的数据操作：“自增序列里所有的元素逐一自增，返回惰性序列。”

(sequence (map inc) [1 2 3])
;; => (2 3 4)

如果不想用序列和惰性序列，可以换成向量或者集合：

(into [] (map inc) [1 2 3])
;; => [2 3 4]

(into #{} (map inc) [1 2 3])
;; => #{4 3 2}

如果没有用 Transducer，我们就必须先把向量变成序列，然后再把序列变回向量。因为 map 和许多函数都只操作序列和惰性序列，和具体的数据类型耦合。

(map inc [1 2 3])
;; => (2 3 4) ; <- 这里得到的是序列，而非向量

(vec (map inc [1 2 3])) ; <- 必须手动转换成向量！
;; => [2 3 4]

(into [] (map inc) [1 2 3]) ; <- Transducer 不关心数据类型
;; => [2 3 4]

上一篇《 异步编程和并发控制 》提到的 channel 也可以接收 Transducer，携带 Transuder 的 channel 会对经过它的所有数据做变换。

(def growing-channel (chan 1 (map inc)))
;; => #'user/growing-channel
(put! growing-channel 1)
;; => true
(poll! growing-channel)
;; => 2

Transducer 的好处就是，由于他只定义了抽象的「做什么」，而不关系具体的「怎么做」，所以可以非常轻易地用在任何地方，不像 map 和 filter 只能作用于序列（或者要把向量、集等其他数据类型转换为序列）。

组合 Transducer

一般来说，要做 Clojure 里做一系列数据操作，会组合使用很多序列函数。

(->> [1 2 3 4 5 6 7 8]
 (filter odd?) ; 1. 过滤，只留奇数
 (map #(* 2 %)) ; 2. 全部乘 2
 (reduce +)) ; 3. 累加
;; => 32

有了 Transducer，我们可以把这一系列操作抽象出来，定义成一个独立的、可复用的操作。

(def double-odd-numbers
 (comp 
 (filter odd?)
 (map #(* 2 %))))

; 可以用来累加
(reduce (double-odd-numbers +) 0 [1 2 3 4 5 6 7 8])
;; => 32
; 等价于
(transduce double-odd-numbers + [1 2 3 4 5 6 7 8])
;; => 32

; 可以不加，返回集合
(into #{} double-odd-numbers [1 2 3 4 5 6 7 8])
;; => #{6 2 14 10}

; 如果你想，还能交给 channel
(def double-odd-chan (chan 1 double-odd-numbers))

comp 的作用是把函数组合起来。(comp f g) 就相当于 (f (g ...))。除了用来组合 Transducer，还可以组合普通的函数：

(filter #(not (zero? %)) [1 2 0 3 0 2 0])
;; => (1 2 3 2)

; 等价于
(filter (comp not zero?) [1 2 0 3 0 2 0])
;; => (1 2 3 2)

不妨做个小练习，定义一个 pipe 函数，作用是接收可变数量的函数，将它们构造成类似 -> 箭头宏的流水线结构，但是不执行这个结构，而是返回函数。比如 (pipe f1 f2 f3) 就返回按顺序执行 f1、f2、f3 的函数，(pipe f1 f2 f3) 相当于 (f3 (f2 (f1 data)))。

参考答案

(defn pipe [& functions]
 (apply comp (reverse functions)))

或者：

(defn pipe [& functions]
 (fn [value]
 (reduce (fn [result f] (f result)) value functions)))

要注意 Transducer 和一般函数的区别。

(comp
 #(map (fn [x] (* 2 x)) %)
 #(filter odd?))
; comp 的结果是 (map fn (filter odd? ...))，很符合直觉
; 返回的函数用来直接操作序列

(comp
 (filter odd?)
 (map (fn [x] (* 2 x))))
; comp 的结果看似是反过来的 (filter odd? (map fn ...))，其实不然
; comp 并不是 -> 宏，而是函数，会先对参数求值
; filter 和 map 求值之后得到了 Transducer
; comp 是把两个 Transducer 组合起来了，而不是把 filter 和 map 组合起来
; 返回的函数用来和 reduce, into, sequence, chan 等一起使用

最后

这篇的内容可能略显抽象，因为涉及了很多对函数的操作，而不是对数据的操作。如果没理解也没有关系。Transducer 能让数据类型与算法解耦；能轻易地组合复用；给了 Clojure 程序员更多的控制权，所以能借助它来写出性能更好的代码——这些都是好处，但没有这些好处也照样能写 Clojure 代码。

那么，回见！

1. 也可以指定初始值，(reduce f init coll) 会先求 (f init a1)，再求 (f (f init a1) a2)
2. 用 & 表示参数数量可变，(fn [& args]) 中的 args 就是包含可变参数的序列。