diff options
Diffstat (limited to 'content/article')
| -rw-r--r-- | content/article/clj8.md | 188 |
1 files changed, 122 insertions, 66 deletions
diff --git a/content/article/clj8.md b/content/article/clj8.md index a8f58758..2c92405e 100644 --- a/content/article/clj8.md +++ b/content/article/clj8.md @@ -4,15 +4,18 @@ subtitle = '' slug = 'clj8' tags = ["Clojure","Lisp","编程"] categories = '茶歇蔻芥' -date = 2026-10-17T17:45:13+08:00 -draft = true +date = 2026-10-18 12:26:01 +draft = false toc = true endnotes = [ '本文参考了 Rich Hickey 写就的《[Anatomy of a Reducer](https://clojure.org/news/2012/05/15/anatomy-of-reducer)》《[Transducers are coming](https://clojure.org/news/2014/08/06/transducers-are-coming)》《[Reducers](https://clojure.org/news/2012/05/08/reducers)》和 Clojure 参考文档里的 [Transducers](https://clojure.org/reference/transducers) 一节。' ] +fedi = 'https://akk.eltr.ac/objects/bf9d0f91-8af0-4f64-80d3-f10a6b08970c' +++ -在第三期《[只用圆括号怎么够？](/article/clj3/#reduce)》里，我讲到了 `reduce` 函数，先来简单复习一下：`reduce` 最少接收两个参数，形如 `(reduce f coll)`，其中 `f` 是接收两个参数的函数，形如 `(f x y)`；`reduce` 遍历 `coll` 中的每个元素，现对前两个元素求 `(f coll1 coll2)`，然后对第三个参数求 `(f (f coll1 coll2) coll3)`，以此类推。<!--more--> +在第三期《[只用圆括号怎么够？](/article/clj3/#reduce)》里，我讲到了 `reduce`。 + +先来简单复习一下：`reduce` 最少接收两个参数，形如 `(reduce f coll)`，其中 `f` 是接收两个参数的函数，形如 `(f x y)`；`reduce` 遍历 `coll` 中的每个元素，先对前两个元素求 `(f a1 a2)`，[^2]然后求 `(f (f a1 a2) a3)`，以此类推。<!--more--> `(f x y)` 这种函数叫作归约函数（reducing function）。 @@ -34,7 +37,9 @@ endnotes = [ 3. `(+ 275 23)` 得到 `298` 4. `(+ 298 99)` 得到 `397` -使用 `+` 作为归约函数，对 `numbers` 这个数字列表进行归约（reduce），就达到了累加的效果。在函数式编程里，归约（reduce）也叫作累积（accumulate）、聚集（accumulate）、压缩（compress）和注入（inject），不过更常见的名字是折叠（fold）。 +使用 `+` 作为归约函数，对 `numbers` 进行归约（reduce），就实现了累加。 + +在函数式编程里，归约（reduce）也叫作累积（accumulate）、聚集（aggregate）、压缩（compress）和注入（inject），不过更常见的名字是**折叠**（fold）。折叠分左折叠（`foldl`）和右折叠（`foldr`）。 还记得第三篇讲过的 [Cons](/article/clj3/#圆括号和列表) 和 Lisp 的列表构造方式吗？Fold 的结构就像是函数版本的 Cons。 @@ -62,22 +67,26 @@ endnotes = [ </div> -Fold 有方向，Clojure 的 `reduce` 默认是左折叠，即 `foldl`： +Clojure 的 `reduce` 默认是左折叠，即 `foldl`：  -要实现右折叠很简单，只要把待操作的列表倒序就好： +要在 Clojure 里实现右折叠，只能把待操作的列表倒序： ```clojure (reduce f (reverse [1 2 3 4 5])) ;; 等价于 -(f (f (f (f 5 4) 3) 2) 1) +(f (f (f (f 5 4) 3) 2) 1) ; 实际上还是左折叠 +;; 如果 f 和 + 一样满足交换律，就等价于 +(f 1 (f 2 (f 3 (f 4 5))))) ; 等价于右折叠 ``` -Fold 中的 `f` 本身也可以是 Fold。还记得 `into` 吗？ +折叠中的 `f` 本身也可以是折叠。还记得 `into` 吗？ ```clojure (into [1 2 3] [4 5]) +;; => [1 2 3 4 5] + ;; 等价于 (reduce conj [1 2 3] [4 5]) ;; 这里的 reduce 以 [1 2 3] 为初始值 ;; 如果没有初始值，就会用第一个元素做初始值 @@ -85,10 +94,12 @@ Fold 中的 `f` 本身也可以是 Fold。还记得 `into` 吗？ (conj (conj (conj [1 2 3]) 4) 5) ``` -如果要打平一个向量，比如把 `[[1] [2 3] [4 5]]` 变成 `[1 2 3 4 5]`，就可以用 `into` 作为归约函数（reducing function），也就是 Fold 中的 `f`。 +如果要打平一个向量，比如把 `[[1] [2 3] [4 5]]` 变成 `[1 2 3 4 5]`，就可以用 `into` 作为归约函数（reducing function），也就是把 `(reduce conj ...)` 作为 `reduce` 的 `f`。 ```clojure (reduce into [[1] [2 3] [4 5]]) +;; => [1 2 3 4 5] + ;; 等价于 (reduce #(reduce conj %1 %2) [[1] [2 3] [4 5]]) ;; 等价于 @@ -99,7 +110,7 @@ Fold 中的 `f` 本身也可以是 Fold。还记得 `into` 吗？ 在 Clojure 中，能够被放在 `reduce` 里使用的函数就叫作归约函数（reducing function）。这个概念与函数式编程和 Lambda 演算的高阶函数（Higher-order function）有关，据说微积分中的导数也算一种高阶函数，但我这篇文章不是讲数学的（我也不会数学），所以就点到为止。 -## 归约变化 +## 改造归约函数 总结一下，归约函数就是这样的一类函数： @@ -119,45 +130,41 @@ Transducer 接收一个归约函数，返回新的归约函数。 返回函数的函数可能有些抽象，但是在 Clojure 中很常见。我举几个例子解释 Transducer 的用法。 -我们已经知道 `+` 可以用作归约函数，我们也知道 `map` 可以把一个函数作用到一个集合的每一个函数上。 +假设我们要对向量自增，然后再累加，就要这样写： -```clojure -(reduce + [1 2 3]) -;; => 6 -(map + [1 2 3]) -;; => (2 3 4) +```clojure +;; 下面这个函数先是自增 [1 2 3 4] 得到 [2 3 4 5] +;; 然后再对 [2 3 4 5] 进行累加 +(reduce + 0 (map inc [1 2 3 4])) +;; => 14 ``` -但我们不知道的是，`map` 也可以当成一个 Transducer 来用。如果只传入一个归约函数给 `map`，`map` 就会把这个函数变成作用于集合（而非单条数据）的新归约函数。 +能不能让 `+` 这个归约函数，在把之前的结果和下一个元素累加起来之前，先给要累加的元素 `+ 1`？也就是说，我们不用遍历一遍列表，生成新的、自增后的列表，然后再累加这个列表，而是在累加的过程中就把自增的操作也做了。 -```clojure -(inc 1) ;; inc 作用于单个数字，返回 +1 后的结果 -;; => 2 +我们可以这样写： -(def inc-all (map inc)) ;; inc-all 作用于集合，返回每个集合元素 +1 后的结果 -(sequence inc-all [1 2 3]) -;; => (2 3 4) +```clojure +;; 下面这个函数用 (map inc) 这个 Transducer +;; 把 + 这个归约函数，转换成了新的归约函数 +;; 这个新的归约函数的作用是：先给单个元素 +1，然后再累加 +(reduce ((map inc) +) 0 [1 2 3 4]) +;; => 14 ``` -为什么不能直接 `(inc-all [1 2 3])`，而是要用 `sequence` 函数？不妨试试看直接调用 `inc-all` 会发生什么。 - -```clojure -(inc-all [1 2 3]) -;; => #object[clojure.core$map$fn__5950$fn__5951 0x72889280 "clojure.core$map$fn__5950$fn__5951@72889280"] +这里我们看到了 [Clojure 1.7](https://clojure.org/news/2015/06/30/clojure-17) 引入的 `map` 的新用法。一般而言，`(map f coll)` 的作用是把 `f` 作用在 `coll` 中的每一个元素上，然后生成新的元素。 -(type (inc-all [1 2 3])) -;; => clojure.core$map$fn__5950$fn__5951 -``` +而 `(map inc)` 则是生成了一个 Transducer，我们把 `+` 作为这个 Transducer 的参数传入，得到了新的归约函数。也就是说，我们将 `(map inc)` 和 `+` 组合，**构造**了新的**数据转换算法**。 +对集合中的元素 `inc`，然后再折叠 `+` 实现累加。 -看起来 `(inc-all [1 2 3])` 返回的不是序列，而是定义在 `clojure.core/map` 下的函数（`fn`）？要理解为什么，就要先理解 Rich Hickey 引入 Transducer 的时候在想什么。 +这种转换与具体类型无关，与惰性无关，与执行顺序也无关，只是**纯粹的算法**。非常便于复用。 ## 将具体类型与转换算法解耦 Clojure 的哲学是简洁，这点并不只是体现在语法（syntax）上，还体现在语义（semantics）和语言的设计上。Rich Hickey 在《[Simple Made Easy](https://www.infoq.com/presentations/Simple-Made-Easy/)》里讲到，简单（simple）的东西就是不和其他东西交织（complect）在一起的东西。 -Java 类不简单，因为它既是命名空间，又是数据结构，还定义了数据上的操作——类（Class）把三个东西交织在了一起。反观 Clojure，命名空间是单独的概念。 +Java 类不简单，因为它既是命名空间，又是数据结构，还定义了数据上的操作——类把三个东西交织在了一起。反观 Clojure，命名空间是单独的概念。 -标照 Rich 本人对简单的定义，准库里的 `map`、`filter`、`reduce` 等操作序列的函数，都不够简单，因为他们不仅涉及做什么操作（what to do），还涉及了怎么做（how to do it）——预设了惰性，预设了数据操作的顺序（序列都是从前往后线性遍历的），预设了数据的表示方式（返回的是序列）。 +标照 Rich 本人对简单的定义，标准库里的 `map`、`filter`、`reduce` 等操作序列的函数，都不够简单，因为他们不仅涉及做什么操作（what to do），还涉及了怎么做（how to do it）——预设了惰性，预设了数据操作的顺序（序列都是从前往后线性遍历的），预设了数据的表示方式（返回的是序列）。 如果 `map`、`filter`、`mapcat` 等函数，能够与数据类型（序列）**解耦**呢？也就是说，如果 `map` 只定义做什么操作（what to do） ，把怎么做（how to do it）交给其他组件呢？ @@ -170,60 +177,45 @@ Java 类不简单，因为它既是命名空间，又是数据结构，还定义 (f1 result (f input))))) ``` -这个 `map` 是构造 Transducer 的函数[^1]，它接收函数 `f`，返回了一个返回函数的函数。 +这个 `map` 是构造 Transducer 的函数，它接收函数 `f`，返回了一个返回函数的函数。我们之前看到的 `(map inc)` 就返回了一个 Transducer。 -最内层的 `(fn [result input])` 就是典型的 `(f x y)` 形式的归约函数。中间的 `(fn [f1])` 接收 `f1` 这个归约函数，返回了最内层的归约函数。在外层的 `mapping` 这个函数定义，返回的就是中间的这个 Transducer。 +这就是对做什么（what to do）的定义。 -这个 `mapping` 定义的操作和 `map` 是一样的，要怎么用呢？这是 Rich 举的例子，下面两种写法输出的结果一样： +`reduce` 则定义了怎么做（how to do it），因为 `reduce` 是对序列的操作，而且是具有惰性的，返回值是惰性序列。所以把 `reduce` 的怎么做（惰性地、顺序地、当作序列执行左折叠）与 `((map inc) +)` 的做什么（“元素自增后再累加”）组合，就得到了完整的数据操作。 -```clojure -;; 下面这个函数先是自增 [1 2 3 4] 得到 [2 3 4 5] -;; 然后再对 [2 3 4 5] 进行累加 -(reduce + 0 (map inc [1 2 3 4])) - -;; 下面这个函数用 (map inc) 这个 Transducer -;; 把 + 这个归约函数，转换成了新的归约函数 -;; 这个新的归约函数的作用是：先给单个元素 +1，然后再累加 -(reduce ((map inc) +) 0 [1 2 3 4]) -``` +如果不想要折叠呢？我能不能直接用 `(map inc)` 累加元素？ -也就是说，我们将 `(map inc)` 和 `+` 组合，**构造**了新的**数据转换算法**。这里的数据转换算法，就是对做什么（what to do）的定义。 - -`reduce` 则定义了怎么做（how to do it），因为 `reduce` 是对序列的操作，而且是具有惰性的，返回值是惰性序列。所以把 `reduce` 的怎么做（惰性地做、顺序地做、当作序列做）与 `((map inc) +)` 的做什么（“元素自增后把所有元素累加起来”）组合，就得到了完整的数据操作。 - -回到一开始的问题，为什么一定要用 `sequence`，不直接用 `inc-all`？因为 `inc-all` 只是抽象的数据转换算法（“自增集合里所有的元素”），但不知道这个集合是什么类型、要不要惰性、最后要返回什么类型。 - -将 `sequence`（输入和输出数据为序列、惰性、顺序操作）与 `inc-all`（“自增集合里所有的元素”）这些要素组合起来，才能得到完整的数据操作：“自增**序列**里所有的元素**逐一**自增，返回**惰性**序列。” +将 `sequence`（输入和输出数据为序列、惰性、顺序操作）与 `(map inc)`（“自增集合里所有的元素”）这些要素组合起来，才能得到完整的数据操作：“自增**序列**里所有的元素**逐一**自增，返回**惰性**序列。” ```clojure -(sequence inc-all [1 2 3]) +(sequence (map inc) [1 2 3]) ;; => (2 3 4) ``` 如果不想用序列和惰性序列，可以换成向量或者集合： ```clojure -(into [] inc-all [1 2 3]) +(into [] (map inc) [1 2 3]) ;; => [2 3 4] -(into #{} inc-all [1 2 3]) +(into #{} (map inc) [1 2 3]) ;; => #{4 3 2} ``` -如果没有用 Transducer 把 `inc` 包装成 `inc-all`，我们就必须先把向量变成序列，然后再把序列变回向量。因为 `map` 和许多函数都只操作序列和惰性序列。 +如果没有用 Transducer，我们就必须先把向量变成序列，然后再把序列变回向量。因为 `map` 和许多函数都只操作序列和惰性序列，和具体的数据类型耦合。 ```clojure (map inc [1 2 3]) -;; => (2 3 4) ; <- 这里得到的是序列，而非向量 +;; => (2 3 4) ; <- 这里得到的是序列，而非向量 -(vec (map inc [1 2 3])) ; <- 必须手动转换成向量！ -;; => [2 3 4] +(vec (map inc [1 2 3])) ; <- 必须手动转换成向量！ +;; => [2 3 4] -(into [] (map inc) [1 2 3]) ; <! Transducer 不关心数据类型 +(into [] (map inc) [1 2 3]) ; <- Transducer 不关心数据类型 ;; => [2 3 4] ``` -上一篇提到的 *channel* 也可以接收 Transducer，携带 Transuder 的 *channel* 会对经过它的所有数据做变换。 +上一篇《[异步编程和并发控制](/article/clj7/)》提到的 *channel* 也可以接收 Transducer，携带 Transuder 的 *channel* 会对经过它的所有数据做变换。 ```clojure (def growing-channel (chan 1 (map inc))) @@ -242,9 +234,9 @@ Transducer 的好处就是，由于他只定义了抽象的「做什么」，而 ```clojure (->> [1 2 3 4 5 6 7 8] - (filter odd?) - (map #(* 2 %)) - (reduce +)) + (filter odd?) ; 1. 过滤，只留奇数 + (map #(* 2 %)) ; 2. 全部乘 2 + (reduce +)) ; 3. 累加 ;; => 32 ``` @@ -257,6 +249,9 @@ Transducer 的好处就是，由于他只定义了抽象的「做什么」，而 (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 @@ -268,3 +263,64 @@ Transducer 的好处就是，由于他只定义了抽象的「做什么」，而 (def double-odd-chan (chan 1 double-odd-numbers)) ``` +`comp` 的作用是把函数组合起来。`(comp f g)` 就相当于 `(f (g ...))`。除了用来组合 Transducer，还可以组合普通的函数： + +```clojure +(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` 函数，作用是接收可变数量的函数[^3]，将它们构造成类似 `->` 箭头宏的流水线结构，但是不执行这个结构，而是返回函数。比如 `(pipe f1 f2 f3)` 就返回按顺序执行 `f1`、`f2`、`f3` 的函数，`(pipe f1 f2 f3)` 相当于 `(f3 (f2 (f1 data)))`。 + +<details> + <summary>参考答案</summary> + +```clojure +(defn pipe [& functions] + (apply comp (reverse functions))) +``` + +或者： + +```clojure +(defn pipe [& functions] + (fn [value] + (reduce (fn [result f] (f result)) value functions))) +``` + +</details> + +要注意 Transducer 和一般函数的区别。 + +```clojure +(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 代码。 + +那么，回见！ + +[^2]: 也可以指定初始值，`(reduce f init coll)` 会先求 `(f init a1)`，再求 `(f (f init a1) a2)` + +[^3]: 用 `&` 表示参数数量可变，`(fn [& args])` 中的 `args` 就是包含可变参数的序列。 |