惰性求值与无穷数据结构

🎞️ 视频网站的”预加载”——但不是全部加载

你看 B 站视频时，网站不会在一开始就下载整部电影——它只加载你当前看的部分和接下来几分钟的内容。如果你只看了开头就关掉了——剩下的数据根本没下载，网费省了。

这就是惰性求值（Lazy Evaluation） 的核心思想：表达式不在定义时计算，而是在”被用到”时才计算。

在求值策略一节中我们已经介绍过惰性求值的基本概念。这一节重点看它带来的一个神奇能力——无穷数据结构。

📐 区分两个概念：

• 惰性求值 = 语言级别的策略——表达式在需要时才求值（Haskell 默认）
• 惰性加载/惰性初始化 = 编程技巧——手动延迟计算（Python 的生成器、JavaScript 的懒加载）

---

∞ 无穷列表——不再是一个矛盾

在严格求值（Eager Evaluation）的语言中，“无穷列表”是一个矛盾——因为计算机内存是有限的。

但在惰性求值的 Haskell 中：

-- 一个"从 1 到无穷"的列表
allNumbers = [1..]  -- 1, 2, 3, 4, 5, ...

-- 取前 5 个——只计算了 5 个元素，不会死循环
take 5 allNumbers  -- [1, 2, 3, 4, 5]

为什么不会死循环？ 因为 [1..] 没有被”一次性计算完”——它只是一个”配方”，告诉你”如果要下一个数字，就是当前数字 + 1”。只有当你真正需要时，它才去计算。

-- 无穷斐波那契数列
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

take 10 fibs  -- [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

fibs 的定义看起来像是”用自己定义自己”——在严格求值中这会导致无限递归。但在惰性求值中，它是按需展开的：

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
     ↓ 当需要第 3 个元素时
     = 0 : 1 : (0+1) : zipWith (+) (tail fibs) (tail (tail fibs))
     = 0 : 1 : 1 : zipWith (+) [1,1,...] [1,...]
     ↓ 需要第 4 个时继续展开
     = 0 : 1 : 1 : 2 : ...

📖 类比：图书馆的”预约取书”

严格求值 = 一次性把所有书从书架上拿下来堆在你面前——你需要多少都给你，非常浪费。

惰性求值 = 你告诉图书管理员”我要所有和计算机相关的书”——但管理员只给你第一本。你看完了，伸手——第二本已经递过来了。你不需要的书，管理员永远不会去拿。

无穷列表就是”所有和计算机相关的书”——理论上无限多，但你可以按需一本一本地看。

---

🔧 惰性求值的机制——thunk

每个惰性求值的表达式被包装成一个 thunk（延迟计算对象）：

let x = 1 + 2 * 3  -- x 是一个 thunk，还没有计算！

内存中的 x：
┌──────────────┐
│   Thunk      │
│  ┌────────┐  │
│  │ 1+2*3  │  │  ← 配方，还没算
│  └────────┘  │
└──────────────┘

当你第一次”用到”x 时：

print x  -- 需要 x 的值 → 计算 thunk → x 变成 7

计算后：
┌──────────────┐
│   7          │  ← 已经计算，结果缓存
└──────────────┘

关键点：thunk 计算后会被缓存——同一个 thunk 不会被计算两次。

let x = expensiveComputation()  -- thunk，还没算
print x  -- 第一次用到 x → 计算（耗时）
print x  -- 第二次 → 直接用缓存的结果（不耗时）

---

💡 惰性求值的其他好处

短路操作是自然的

-- 逻辑运算符本身就是惰性的

-- 在惰性求值中，&& 的定义天然支持短路：
-- True && x = x
-- False && x = False

-- 所以：
False && (1/0 == 2)  -- 不会计算 (1/0)，因为 False && 任何东西都是 False

在严格求值语言中，“短路”是 && 和 || 的特殊语法。在惰性求值语言中，短路是默认行为。

自定义控制结构

-- 在惰性求值语言中，可以定义自己的 "if-then-else"
myIf True t _ = t
myIf False _ f = f

-- 使用
myIf (5 > 3)
    (print "yes")
    (print "no")
    -- 只打印 "yes"——"no" 分支从未被计算！
    
-- 在严格求值语言中，你不能这样定义 if——因为两个分支都会先被计算

---

⚠️ 惰性求值的代价

-- 1. 内存泄漏——thunk 堆积
-- 看这个看似无辜的代码：
let result = foldl (+) 0 [1..1000000]  -- thunk 链！
-- 在严格求值中是 O(1) 空间的
-- 在惰性求值中，所有未计算的 thunk 会堆起来——直到最后才一次性算完
-- 导致 O(n) 的空间！

-- 修复：用 foldl'（严格版本）
let result = foldl' (+) 0 [1..1000000]  -- 立即计算

-- 2. 性能不可预测
-- 你不知道某个表达式什么时候会被计算
-- 一个看似简单的操作可能触发大量堆积的计算

-- 3. 调试困难
-- 因为执行顺序不直观，跟踪程序行为更难

💡 Haskell 的实践经验：Haskell 程序员会在性能关键的地方手动”注入严格性”，防止 thunk 堆积。最常见的做法是用 seq、$! 或 BangPatterns 来强制求值。

---

🐍 Python 中的”手动惰性”——生成器

Python 虽然是严格求值的，但你可以通过生成器（Generator） 实现类似的惰性效果：

# Python 生成器——按需产生值
def fibonacci():
    a, b = 0, 1
    while True:       # "无穷"序列
        yield a       # 产生一个值，暂停
        a, b = b, a + b

fib = fibonacci()

print(next(fib))  # 0 —— 产生了第一个值
print(next(fib))  # 1 —— 产生了第二个值
print(next(fib))  # 1
print(next(fib))  # 2
# ...可以一直 next 下去，不会死循环！

生成器的关键：yield 会暂停函数执行，保留局部变量状态，下次 next() 再从中断处继续。

# range 在 Python 3 中也是惰性的
nums = range(1, 1000000000)  # 瞬间完成！没有创建 10 亿个数字
print(nums[0])               # 1 —— 只计算了第一个
print(nums[999999])          # 1000000 —— 只计算了这一个

---

📝 小结

概念	一句话
惰性求值	表达式在定义时不计算，在用到时才计算
Thunk	未计算的表达式——一个”配方”
记忆化（Memoization）	thunk 结果被缓存——不会重复计算
无穷数据结构	惰性让”无限”数据成为可能——按需生成
生成器（Generator）	Python 中手动实现惰性的方式
空间泄漏	thunk 堆积导致内存暴涨——惰性求值的代价

🎯 小练习：用 Python 生成器实现一个”埃拉托色尼筛法”——一个无限产生质数的序列。提示：你可以 yield 当前找到的质数，同时保留下一个候选。

为什么先学这个？ 惰性求值是函数式语言的标志性特性。接下来进入另一种维度——类型系统的对比。静态 vs 动态类型。