惰性:无限列表与 thunk

thunk:没兑现的支票

在急切语言里,val x = expensive() 执行到这行就开算。Haskell 里,x = expensive input 只是登记了一张「支票」:一个包着表达式和环境的小包裹,行话叫 thunk。支票什么时候兑现?当某段代码真的需要 x 的值的时候——比如要打印它、要拿它做分支判断。这个「需要」的动作叫强迫(force)。

最能暴露本性的例子。下面这行在几乎所有语言里都会爆炸,在 Haskell 里安然无恙:

λ> fst (1 + 1, error "炸弹")
2

fst 只需要元组的第一格。第二格的 error "炸弹" 作为 thunk 被原样丢弃,从未被强迫,所以从未爆炸。参数不是「先算好再传入」,而是「打包成支票传入,爱兑不兑」——这套求值策略的学名是 call-by-need(按需调用),区别于 Java/Kotlin 的 call-by-value(先算好值再传)。顺带划清一个常见误解:惰性不是「异步」也不是「延迟执行的任务」,没有线程、没有调度——它只是把「何时计算」的决定权从「写代码的位置」移交给了「用结果的位置」。

逐帧看:图归约现场

口说无凭。下面的求值器和第 2 章的终端共用同一个引擎,但它会在每次强迫一个 thunk 时拍一张快照。⟨尖括号⟩里是还在睡觉的 thunk,高亮的是此刻正被强迫的那个。请先跑默认的 take 3 (map (*2) [1..]),用 ▶ 一步步走:

值得盯住的细节:[1..] 这个「无限列表」从头到尾只被展开了三节——take 要一个,map 才要一个,range 才吐一个。需求从消费端往生产端逐级传导,生产量精确等于消费量。这就是无限数据结构能存在的全部原理:无限的是「定义」,有限的是「被强迫的部分」。

再试预置的第二条 head (filter (>10) (map (*3) [1..])):filter 在无限流上找第一个大于 10 的数,找到 12 就整体收工。你在 Kotlin 里写的 sequence.map{}.filter{}.first(),内部机制就是这个,只是 Haskell 的所有值默认如此。

惰性的招牌菜:自引用的数据

共享 + 惰性,允许一个值在定义里引用自己——不是递归函数,是递归的数据:

λ> let fib = 0 : 1 : zipWith (+) fib (tail fib) in take 10 fib
[0,1,1,2,3,5,8,13,21,34]

读法:fib 的第三项开始,每一项是「fib 自己」和「fib 掉个头」的对应项之和。这个定义在急切语言里是死循环,在这里是 O(n) 的斐波那契流——因为每个新项引用的旧项已经被共享的图算好了。同一招还能写出素数筛:

primes = sieve [2..]
  where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
-- take 10 primes ⇒ [2,3,5,7,11,13,17,19,23,29]

这类代码有个称号叫 wholemeal programming(整粮编程):先定义完整的(哪怕无限的)问题空间,再用 take/filter 裁出要的部分。对比急切思维的「边生成边裁剪」,整粮风格的生成逻辑和消费逻辑完全解耦,各自都简单到可以一眼验证。

强迫到多深:WHNF

「强迫一个值」不是全有全无的。求值有深浅之分,而 Haskell 的默认深度浅得惊人:只剥到最外层构造子露出来为止,行话叫弱头范式(WHNF,weak head normal form)。例子最清楚:

xs = [1 + 1, 2 + 2, error "雷"]

length xs   -- ⇒ 3。只数「有几节车厢」,每节里装的 thunk 一个没拆
head xs     -- ⇒ 强迫到 1+1 这个 thunk,再强迫它,得 2;后面两节没人碰
xs == xs    -- 💥 判等需要拆开每个元素,第三个雷被引爆

「强迫列表」默认只强迫脊椎(spine,车厢的链接结构),不强迫元素;「强迫元组」只确认它是个元组,两格里的 thunk 原封不动。这个分层解释了很多现象:为什么 length 对含 error 的列表安然无恙(试试!),为什么第 5 章说 foldl 的累加器「攒着不算」——foldl 只把列表脊椎走完(WHNF 级别),累加器里的加法一层都没剥。需要「一撸到底」的深度求值时,得动用 deepseq 库或第 16 章的严格性注解——深求值在 Haskell 里是显式操作,浅才是默认,和你的语言正好颠倒。

观察求值:给 thunk 装摄像头

本章的快照器在真实 GHC 里有对应物:Debug.Trace。trace :: String -> a -> a 返回第二个参数,但在自己被强迫的那一刻往终端喷一行字——等于在任意表达式上贴一个求值探针:

λ> import Debug.Trace
λ> let xs = map (\x -> trace ("算了 " ++ show x) (x * 2)) [1..5]
λ> take 2 xs
[算了 1
2,算了 2
4]
λ> length xs
5                    -- 一条 trace 都没喷:length 不碰元素

输出和值穿插在一起,乱,但信息量极大:哪个元素在何时被算、哪些从未被算,一目了然。两个用法提示:其一,trace 是调试专用的「合法作弊」(它偷偷做了 IO 却装作纯函数),上生产前必须清干净;其二,当你对惰性程序的性能疑惑时,先 trace 看求值顺序,再谈优化——凭直觉猜求值顺序,新老手都会猜错。

惰性如何改变 API 设计

一个不起眼但深远的影响:「可能用不上的计算」可以随便定义。看这个模式:

report status = case status of
    Healthy -> "一切正常"
    Degraded -> summary
    Down     -> summary ++ "!!! " ++ details
  where
    summary = buildSummary metrics      -- 有点贵
    details = buildDetails logs         -- 非常贵

where 里两个「贵」的值,急切语言要么每个分支手动传(啰嗦),要么提前全算(浪费),要么包 lambda 延迟(丑)。惰性语言里直接写平:Healthy 分支一个都不算,Degraded 只算 summary,Down 两个都算但 summary 只算一次(两处引用,共享)。控制流自动变成了求值计划。同样的机制让 Haskell 能用普通函数定义 if'、when、短路逻辑——别的语言必须做成宏或语法,这里 thunk 天然就是「没执行的代码块」。

组合的红利:head . sort

惰性最优雅的一笔,是让「朴素组合」自动获得聪明算法的性能。求列表最小值,有人写了这么一行:

smallest :: Ord a => [a] -> a
smallest = head . sort        -- 排个序,取第一个?!

急切语言里这是 O(n log n) 的浪费,代码评审必被打回。惰性语言里不一定:懒惰的快排只会「按需分区」——head 只索要第一个元素,于是 sort 只递归较小的那半边,较大的半边永远停留在 thunk 状态。摊开分析,实际工作量是 O(n)——和手写「找最小值」同阶。「取前 k 名」同理:take k . sort 接近 O(n + k log n),而代码始终是那句人话:「排序,取前 k 个」。

这背后是惰性给出的一个大承诺:组合不吃亏。生产者尽管把完整结果「定义」出来,消费者要多少才算多少,两端谁都不用为对方优化。这也正是 GHC 敢做 fusion 优化(把 map f . map g 熔成一趟遍历)的语义基础——反正没人能观测到中间列表是否真的存在过。