[publish] /article/clj4

1 files changed, 232 insertions, 11 deletions

diff --git a/content/article/clj4.md b/content/article/clj4.md
index 396d539d..501f2f77 100644
--- a/content/article/clj4.md
+++ b/content/article/clj4.md
@@ -4,14 +4,18 @@ subtitle = 'Functioanlly Lazy'
 slug = 'clj4'
 tags = ["Lisp","编程"]
 categories = '茶歇蔻芥'
-date = 2026-09-29T14:07:57+08:00
-draft = true
+date = 2026-09-29 21:42:08
+draft = false
 toc = true
+endnotes = [
+    '最后一节的练习题参考了 [ClojureDocs](https://clojuredocs.org/) 上的示例代码。'
+]
+fedi = 'https://akk.eltr.ac/objects/b40e3572-921d-45d2-85dd-d61e1550e0d9'
 +++
 
 今天的文章衔接[上一期](/article/clj3/)有关集合（collection）和序列（sequence）的知识，来讨论一种特殊的集合，叫惰性序列（lazy seq）。我们还会接触到函数式编程（functional programing）。
 
-其实在另一门名为 [Haskell](https://www.haskell.org/) 的语言里，也能见到惰性，而 Haskell 是纯函数式的编程语言（不像 Clojure 有很多面向对象的成分）。函数式和惰性非常契合，可以说没了惰性，函数式就不够务实，会消耗更多的计算资源。<!--more-->
+其实在另一门名为 [Haskell](https://www.haskell.org/) 的语言里，也能见到惰性，而 Haskell 是纯函数式的编程语言（Clojure 在很多方面都不如 Haskell 严格）。函数式和惰性非常契合，可以说没了惰性，函数式就不够务实，会消耗更多的计算资源。<!--more-->
 
 ## 编程范式
 
@@ -21,7 +25,7 @@ toc = true
 
 据 Robert C. Martin 在《[架构整洁之道](/library/2026/clean-architecture/#编程范式设计原则和组件原则)》里总结，结构化编程本质是上限制了**程序控制权的直接转移**，即不允许用 `goto` 语句直接变更程序的执行位置。要转移程序的执行位置，只能用**块结构**[^1]表示条件判断、循环体等等。块结构使得程序可以被清晰地划分为可理解的部分，而不是一条一条分散的代码。
 
-面向对象编程（object-oriented programing，后称 OOP）在块结构之上提出了新的组织程序的方式，也就是类。程序员经常需要定义一种数据类型，然后定义对这种数据类型的操作（封装）；对不同的类型和不同的输入而言，相同的操作可能有不同的行为（多态）；数据类型的某些操作是共通的，可以复用（继承）。OOP 引入了更高层的概念和结构。据 Martin 所言，OOP 本质上是限制了对程序控制权的**间接**转移，因为 OOP 用方法（method）代替了函数指针（function pointer）。[^2]
+面向对象编程（object-oriented programing，后称 OOP）在块结构之上提出了新的组织程序的方式，也就是对象（之所以不说「类」，是因为也有无类 OOP，比如[基于原型的编程](https://en.wikipedia.org/wiki/Prototype-based_programming)）。程序员经常需要定义一种数据类型，然后定义对这种数据类型的操作（封装）；对不同的类型和不同的输入而言，相同的操作可能有不同的行为（多态）；数据类型的某些操作是共通的，可以复用（继承）。OOP 引入了更高层的概念和结构。据 Martin 所言，OOP 本质上是限制了对程序控制权的**间接**转移，因为 OOP 用方法（method）代替了函数指针（function pointer）。[^2]
 
 Martin 认为编程范式并没有引入新的东西，反而是提出了更多的限制，比如限制 `goto` 语句和限制函数指针。函数式编程（后称 FP）范式引入的限制是：禁止赋值语句。是的，==不允许给变量赋值==，所以在前四篇里我们一次都没有见到 Clojure 的赋值语句，只见到了定义符号的语句。
 
@@ -32,9 +36,9 @@ Martin 认为编程范式并没有引入新的东西，反而是提出了更多�
     - 说到这里，容许我插一嘴，我前不久修复了一个非常诡异的 Bug，最后我们发现问题出在系统里某个地方加了锁。这个锁是外部的某个库引入的，我们完全不知道那个锁的存在。当时系统出现了大量的超时错误，我们以为是网络阻塞，结果竟然是大量请求等待锁导致的。
 3. 管理状态如何在系统的各个部分之间同步和转移，定义状态如何变更，检验状态的有效性等等，都会极大提升系统的复杂度。
 
-这其实也在逐渐成为共识，我们看到很多编程语言（比如 Rust）的变量默认不可变（immutable）。状态更少会让复杂系统更容易维护，而是 FP 则致力于消除可变状态。
+这其实也在逐渐成为共识，我们看到很多编程语言（比如 Rust）的变量默认不可变（immutable）。状态更少会让复杂系统更容易维护，而 FP 则致力于消除可变状态。
 
-不过整体而言，FP 并不主流。不少人对 Haskell 的第一印象是「学术语言」，尽管 Haskell 的标语是「Enjoy long-term maintainable software you can rely on」（享受你可以依靠的长期可维护的软件），显然是出于工程考虑写下的标语。
+不过整体而言，FP 并不主流。不少人对 Haskell 的第一印象是「学术语言」（一开始的确是）。Haskell 的标语是「Enjoy long-term maintainable software you can rely on」（享受你可以依靠的长期可维护的软件），这显然是出于工程考虑写下的标语。
 
 在过去，FP 受到的不认可往往源自于它的性能问题。由于 FP 系统不维护状态，而是在函数的相互调用之间传递参数，循环结构也往往用递归（recursion）表示，这就导致处理大量数据时，函数栈帧会占用大量内存，而且可能出现栈溢出问题。不过这个问题现在已就有了应用广泛的解决方案，叫作尾部调用优化（Tail Call Optimization，TCO）——简单来说，只要递归函数调用发生在函数尾部，编译器或解释器就可以复用上一个递归调用的栈帧，把递归调用变成循环结构，但语言层面仍然是递归写法。
 
@@ -42,7 +46,7 @@ Martin 认为编程范式并没有引入新的东西，反而是提出了更多�
 
 FP 不仅禁止赋值语句，还避免副作用（side effectse）。FP 把函数想象成和数学函数一样的东西，输入值，然后输出值，这其间不该发生别的事情，比如不该修改系统中其他的状态。
 
-那 FP 程序怎么和外部设备交互呢？照其定义，I/O 操作也是副作用，我还不能把数据写入磁盘了吗？其实，一般只有**纯**函数式语言才会想要完全消除副作用，Haskell 是通过引入 [IO 单子](https://zh.wikipedia.org/wiki/%E5%8D%95%E5%AD%90_(%E5%87%BD%E6%95%B0%E5%BC%8F%E7%BC%96%E7%A8%8B)#IO%E5%8D%95%E5%AD%90%EF%BC%88Haskell%EF%BC%89)的概念消除副作用的。Haskell 把对外部状态的访问和操作当作显式的作用，而非副作用。至于 Clojure，它并不是**纯**函数式语言。副作用是允许的，只是不鼓励。Scheme 也容忍副作用，因此 Scheme 更喜欢用 *procedure*（过程）这个词表示 *function*，因为有副作用的不是纯函数。
+那 FP 程序怎么和外部设备交互呢？照其定义，I/O 操作也是副作用，我还不能把数据写入磁盘了吗？其实，一般只有**纯**函数式语言才会想要完全消除副作用，Haskell 是通过引入 [IO 单子](https://zh.wikipedia.org/wiki/%E5%8D%95%E5%AD%90_(%E5%87%BD%E6%95%B0%E5%BC%8F%E7%BC%96%E7%A8%8B)#IO%E5%8D%95%E5%AD%90%EF%BC%88Haskell%EF%BC%89)的概念消除副作用的。Haskell 把对外部状态的访问和操作当作显式的作用，而非副作用。至于 Clojure，它并不是**纯**函数式语言。副作用是允许的，只是不鼓励。Scheme 也允许副作用，因此 Scheme 更喜欢用 *procedure*（过程）这个词表示 *function*，因为有副作用的不是纯函数。
 
 与副作用相关的概念是引用透明性（[referential transparency](https://en.wikipedia.org/wiki/Referential_transparency)），可以说避免副作用就是为了实现引用透明性。以下面这段 Clojure 代码为例：
 
@@ -74,7 +78,7 @@ add(add(x, x), x)
 
 上述 `add()` 是个闭包函数（因为它访问了外部作用域的 `x` 变量），每执行一次 `add()` 都悄悄地给 `x` 加 `1`，然后再返回 `a + b`。
 
-执行 `add(add(x, x), x)` 的结果是 `1`，因为调用最外层的 `add()` 之前，我们先要得到参数的值。第一个参数是函数调用，求出值为 `0`，同时 `x` 的状态变成了 `1`[^4]；然后将 `0` 作为第一个参数传入，此时求 `x` 的值，发现是 `1`，将 `1` 作为第二个参数传入，也就是 `add(0, 1)`。最后函数返回了 `1`，`x` 的值变成了 `2`。
+执行 `add(add(x, x), x)` 的结果是 `1`。调用最外层的 `add()` 之前，我们先要得到参数的值。第一个参数是函数调用，求出值为 `0`，同时 `x` 的状态变成了 `1`[^4]；然后将 `0` 作为第一个参数传入，此时求 `x` 的值，发现是 `1`，将 `1` 作为第二个参数传入，也就是 `add(0, 1)`。最后函数返回了 `1`，`x` 的值变成了 `2`。
 
 假设现在 `x` 的值还是 `0`，我们把 `add(x, x)` 换成理应等价的 `0`，发现 `add(0, x)` 得到的是 `0` 而不是 `1`。这个程序没有引用透明性，而且 `x` 的状态不可控，`add()` 的结果难以预测。
 
@@ -130,7 +134,7 @@ addWithCounter(numbers, 0, 0, 0)
 
 `lazy-seq` 函数接收一系列表达式，这些表达式最终返回一个序列。不过，写在 `lazy-seq` 里面的表达式并不会被立即执行，而是会在 `lazy-seq` 被访问时执行。也就是说，`lazy-seq` 保存了一系列「如何求值」的步骤，仅在每个步骤被访问时才计算具体的数值。
 
-还记得序列（sequence）的定义吗？仅支持线性访问的集合。还记得 Cons 吗？一个序列就是保存了第一个值（`_first`）和指向下一个 Cons 的“指针”（`_next`）的对象。假如序列的 `next` 并不指向下一个 Cons 的，调用它的 `next()` 方法时，它并不 `return _next`，而是调用函数计算下一个值再返回，调用几次 `next()` 就计算几次值。
+还记得序列（sequence）的定义吗？仅支持线性访问的集合。还记得 Cons 吗？一个序列就是保存了第一个值（`_first`）和指向下一个 Cons 的“指针”（`_next`）的对象。假如序列的 `next` 并不指向下一个 Cons，调用它的 `next()` 方法时，它并不 `return _next`，而是调用函数计算下一个值再返回，调用几次 `next()` 就计算几次值。
 
 听起来像个迭代器（Iterator），两者确实很像。惰性序列就是可以当作序列处理的迭代器，不过我们并不需要手动调用 `next`，只需要正常地把它当作序列处理，剩下的 Clojure 会帮我们解决。
 
@@ -169,9 +173,12 @@ addWithCounter(numbers, 0, 0, 0)
 只想要偶数？当然！
 
 ```clojure 
-;; 其实我本来想用 {2k|k∈ℤ}，可惜不合法
+;; 其实我本来想用 {2k|k∈ℤ} 做符号名，可惜不合法
 (def even-numbers (filter even? ℤ))
 ;; => #'user/even-numbers
+;; or 
+(def even-numbers (map #(* 2 %) ℤ))
+;; => #'user/even-numbers
 
 (take 5 even-numbers)
 ;; => (2 4 6 8 10)
@@ -190,11 +197,223 @@ addWithCounter(numbers, 0, 0, 0)
 public int count(){
 	int c = 0;
 	for(ISeq s = seq(); s != null; s = s.next())
-		++c;                                                                                
+		++c;
 	return c;
 }
 ```
 
+惰性序列和迭代器的另一个区别是，惰性序列会缓存已经计算的值，再次访问时会使用已有的值，不会重复计算。可以用 `realized?` 函数检查序列有没有被计算。
+
+```clojure 
+(realized? (range))
+;; => true
+(realized? (rest (range)))
+;; => false
+```
+
+`(range)` 本身作为一个 Cons，包含 `0` 的初始值，但它之后的 Cons 都还没有被计算，所以返回 `false`。注意 `(realized? (first (range)))` 实际上是 `(realized? 0)`，会报错，因为 `Long` 类型没有是否被实现之分。
+
+## 练习函数式与惰性
+
+接下来我会提出一些需求，读者可以在自己的 REPL 里编写 Clojure 代码实现，我会把参考答案附在题目后面。题目中还会包含一些新的 Clojure 函数的用法介绍，读者可以一边练习一边学习新函数。
+
+### 凯撒密码 
+
+凯撒密码是一种替换加密，即简单地把明文中的每个字母替换为字母表往后偏移 N 个字母之后的字母。比如，如果偏移量是 3，`A` 就会被换成 `D`。
+
+![](https://img.eltr.ac/geedeapro/article/clj4/Caesar3.svg.webp "凯撒密码示意图")
+{.dark:invert}
+
+我们知道 ASCII 编码中，`65` 对应的是大写字母 `A`，`90` 对应 `Y`。如果要将 `A` 变成 `D`，只需要对字符的十进制数表示加 3，然后再转换成字符。
+
+在 Clojure 中，可以调用 Java 方法把数字转换为 ASCII 字符串：
+
+```clojure 
+(Character/toString 65)
+;; => "A"
+(Character/toString (+ 65 3))
+;; => "D"
+```
+
+可以用 `zipmap` 函数把两个序列封装成映射，第一个序列的元素作为键，第二序列的元素作为值。
+
+```clojure 
+(zipmap ["A" "B" "C"] ["D" "E" "F"])
+;; => {"A" "D", "B" "E", "C" "F"}
+```
+
+`range` 可以指定序列的范围：
+
+```clojure
+(range 65 91)
+;; => (65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90)
+```
+
+使用 `range`、`map` 和 `zipmap` 构造出偏移量为 `5` 的凯撒密码对照表。
+
+<details>
+    <summary>参考答案</summary>
+
+```clojure 
+(defn caesar-map [offset]
+  (let [alphabet (map Character/toString (range 65 91))
+        ciphered (concat (drop offset alphabet) 
+                         (take offset alphabet))]
+    (zipmap alphabet ciphered)))
+```
+
+```clojure 
+(caesar-map 5)
+;; => {"T" "Y", "K" "P", "Q" "V", "L" "Q", "G" "L", "J" "O", "M" "R", "S" "X", "Y" "D", "Z" "E", "H" "M", "E" "J", "R" "W", "C" "H", "F" "K", "B" "G", "P" "U", "V" "A", "U" "Z", "O" "T", "X" "C", "N" "S", "A" "F", "I" "N", "W" "B", "D" "I"}
+
+(get (caesar-map 5) "A")
+;; => "F"
+```
+
+</details>
+
+### 钩子
+
+系统的业务逻辑里有几个关键节点设置了钩子，在特定事件发生时可以执行用户自定义的函数，像这样：
+
+```clojure 
+(defn process-large-data [hooks data]
+  (let [todo (map process-data (filter valid? data))]
+    (if (seq todo)
+      ;; todo 非空的时候，执行 todo
+      ;; 然后调用 hooks 里的 :on-finish 函数
+      (do (doall todo)
+          ((:on-finish hooks)))
+      ;; todo 为空，即没有要处理的数据 
+      ;; 调用 hooks 里的 :on-empty 函数
+      ((:on-empty hooks)))))
+```
+
+`todo` 是 `filter` 和 `map` 返回的惰性序列，如果没有被访问就不会执行 `process-data`。之后通过 `seq` 检查 `todo` 是否**非空**，如果是的话就 `doall`，这个函数可以执行惰性序列中所有的元素。外层的 `do` 用来把多个表达式放在一个形式（form）里，不然会被 `if` 当作多个参数处理。
+
+`hooks` 是长这样的映射。
+
+```clojure 
+{:on-finish (fn [] (println "Finished processing"))
+ :on-empty (fn [] (println "Todo is empty"))}
+```
+
+`(:on-finish hooks)` 把函数从映射里取出来，`((:on-finish hooks))` 先把函数取出来，然后执行这个函数。
+
+可以使用 `merge` 函数将两个映射合并，如果有相同的键，用后一个映射覆盖：
+
+```clojure
+(merge {:a 1 :b 2 :c 3} {:a 2 :b 1})
+;; => {:a 2, :b 1, :c 3}
+```
+
+`repeat` 函数返回重复同一个值的序列，如果不指定重复的次数，就会返回无限长的惰性序列。
+
+```clojure 
+(repeat 5 "hello")
+;; => ("hello" "hello" "hello" "hello" "hello")
+
+(take 5 (repeat "hello"))
+;; => ("hello" "hello" "hello" "hello" "hello")
+
+(repeat "hello")
+;; 如果直接访问这个惰性序列
+;;（比如：在 REPL 里输入，REPL 会 print 这个序列）
+;; 就会造成死循环，(range) 也是同理
+```
+
+使用 `merge`、`repeat` 和 `zipmap` 编写 `make-hooks` 函数，接收 `user-hooks` 参数，`user-hooks` 和上文的 `hooks` 结构相同，但键可能不全。默认情况下，`hooks` 中的钩子函数不做任何操作（`println` 也不能有），除非用户传入了钩子函数。
+
+<details>
+    <summary>参考答案</summary>
+
+```clojure 
+(def hook-keys [:on-finish :on-empty])
+
+(def default-hooks 
+  (zipmap hook-keys (repeat (fn []))))
+
+(defn make-hooks 
+  ([] default-hooks)
+  ([user-hooks]
+   (if (seq user-hooks)
+     (select-keys 
+       (merge default-hooks user-hooks)
+       hook-keys))
+     default-hooks))
+```
+
+`select-keys` 只选择映射中指定的键，如果用户提供了不存在的键，可以用这个函数筛掉。不过不筛问题也不大，反正多余的钩子也不会被调用。
+
+</details>
+
+### 无重复的随机数序列 
+
+`repeat` 函数重复值，`repeatedly` 函数可以重复执行函数，返回惰性序列。`(rand-int n)` 返回 `[0, n)` 区间内的随机整数。[^5]
+
+```clojure 
+(take 5 (repeatedly #(rand-int 100)))
+;; => (72 56 54 21 89)
+```
+
+`loop` 和 `recur` 刚才我们已经见过了。可以把 `loop` 里类似 `let` 绑定的向量当作函数的参数和初始值之间的绑定，而 `recur` 则是递归地调用 `loop`，`recur` 的参数数量应该和 `loop` 的绑定数量相同。
+
+```clojure 
+(loop [arg1 0, arg2 "any value" arg3 :not-over]
+  (if (> arg1 10)
+    {:arg1 arg1 :arg2 arg2 :arg3 :over}
+    (recur (inc arg1) "any value" :not-over)))
+;; => {:arg1 11, :arg2 "any value", :arg3 :over}
+```
+
+使用任何你能想到的函数，编写 `uniquely-rand-int` 函数，接收参数 `n` 和 `t`，返回由 `n` 个小于 `t` 的**不重复**的随机整数序列。
+
+<details>
+    <summary>参考答案</summary>
+
+第一种解法，使用 `loop` 并拒绝已经存在的元素。
+
+```clojure 
+(defn uniquely-rand-int [n t]
+  (loop [result '()]
+    (if (>= (count result) n)
+      result
+      (let [randint (rand-int t)]
+        (if (some #{randint} result)
+          (recur result)
+          (recur (conj result randint)))))))
+```
+
+第二种解法，使用 `set`，利用集的特性去重。
+
+```clojure 
+(defn uniquely-rand-int [n t]
+  (loop [result #{}]
+    (if (>= (count result) n)
+      (seq result)
+      (recur (conj result (rand-int t))))))
+```
+
+第三种解法：
+
+```clojure 
+(defn uniquely-rand-int [n t]
+  (->> (range t) shuffle (take n)))
+```
+
+第三种解法不仅更简洁，而且不会出现死循环。试一试，如果是前两种解法，在 `t` 比 `n` 小的情况下就会出现死循环，但第三种解法只会返回数量不足的序列。
+
+```clojure 
+(uniquely-rand-int 5 10)
+;; => (6 8 1 3 9)
+(uniquely-rand-int 5 1)
+;; => (0)
+```
+
+而且第三种解法的时间复杂度是 `O(n)`，瓶颈主要在 `shuffle`，这个函数底下用的是 Java 的 `Collections.shuffle`，[时间复杂度为 `O(n)`](https://zetcode.com/java/collections-shuffle/#:~:text=The%20time%20complexity%20is%20O(n)%20where%20n%20is%20the%20list%20size.)。
+
+</details>
+
 [^1]: 比如 C 语言中 `{}` 包裹的块。
 
 [^2]: 不过我对这个说法存疑，因为 C++ 作为 OOP 语言，甚至有方法指针（method pointerp）这种东西。
@@ -202,3 +421,5 @@ public int count(){
 [^3]: Go 语言的 `channel` 其实用 FP 以外的方式解决了这个问题
 
 [^4]: 为什么这个 `add(x, x)` 没有受到 `x = 1` 的影响？因为函数的参数是作为**值**传入的，不是变量引用。`add()` 接收到的就是两个 `0` 而不是两个 `x`。 
+
+[^5]: 你可能注意到了：是的，`rand-int` 不具有引用透明性，不是函数式的，除非确定种子。