第 15 章：惰性求值（Lazy evaluation）

原文：Graham Hutton, Programming in Haskell, Second Edition, Chapter 15。维护者已确认本书可翻译并发布用于学习研究。

本章介绍惰性求值，也就是 Haskell 用来对表达式求值的机制。我们先回顾求值的概念，然后考虑求值策略及其性质，接着讨论无限结构和模块化编程，最后介绍一种特殊的函数应用形式，它可以改善程序的空间性能。

15.1 引言（Introduction）

正如全书前面所见，Haskell 中基本的计算方式是把函数应用到参数。例如，假设定义一个递增整数的函数：

inc :: Int -> Int
inc n = n + 1

那么表达式 inc (2*3) 可以按下面方式求值：

inc (2*3)
= { applying * }
inc 6
= { applying inc }
6 + 1
= { applying + }
7

也可以先执行前两个函数应用中的另一个，得到同样的最终结果：

inc (2*3)
= { applying inc }
(2*3) + 1
= { applying * }
6 + 1
= { applying + }
7

改变函数应用顺序不会影响最终结果，这一事实并不只适用于上面这样的简单例子，而是 Haskell 中函数应用的重要一般性质。更形式化地说，在 Haskell 中，对同一个表达式进行求值的任意两种不同方式，只要二者都终止，就总会产生相同的最终值。稍后我们会回到终止问题。

还要注意，上述性质对多数命令式编程语言并不成立。在这些语言中，基本计算方式是改变存储值。例如，考虑命令式表达式 n + (n = 1)，它把变量 n 的当前值加上把 n 改为一所得的结果。假设 n 初始值为零，这个表达式可以先执行加法左侧：

n + (n = 1)
= { applying n }
0 + (n = 1)
= { applying = }
0 + 1
= { applying + }
1

也可以先执行右侧：

n + (n = 1)
= { applying = }
n + 1
= { applying n }
1 + 1
= { applying + }
2

两种情况下最终值不同。这个例子展示的一般问题是：在命令式语言中，赋值发生的精确时间可能影响计算所得的值。相比之下，在 Haskell 中，函数应用到参数的时间从不会影响计算所得的值。不过，正如本章余下部分将看到的，求值过程的顺序和性质仍然涉及重要的实践问题。

15.2 求值策略（Evaluation strategies）

形如函数应用到一个或多个参数、并且可以通过执行应用来“化简”的表达式，称为可化简表达式（reducible expression），简称 redex。这里给“化简”加引号，是因为这类化简并不一定会减小表达式大小，尽管实践中通常如此。

举例来说，假设定义一个函数 mult，它接收一对整数并返回它们的乘积：

mult :: (Int,Int) -> Int
mult (x,y) = x * y

现在考虑表达式 mult (1+2,2+3)。这个表达式包含三个 redex，分别是子表达式 1+2 和 2+3，它们都是加法运算符 + 应用于两个参数；以及整个表达式 mult (1+2,2+3)，它是函数 mult 应用于一对参数。执行对应化简会分别得到表达式 mult (3,2+3)、mult (1+2,5) 和 (1+2) * (2+3)。

对一个表达式求值时，化简应该按什么顺序进行？一种常见策略称为最内层求值（innermost evaluation）：总是选择最内层 redex，也就是不包含其他 redex 的 redex。如果存在多个最内层 redex，按惯例选择表达式中最靠左开始的那个。

例如，在表达式 mult (1+2,2+3) 中，子表达式 1+2 和 2+3 都不包含其他 redex，因此都是最内层 redex；其中 1+2 开始位置最靠左。更一般地，我们的例子使用最内层求值会如下进行：

mult (1+2, 2+3)
= { applying the first + }
mult (3, 2+3)
= { applying + }
mult (3, 5)
= { applying mult }
3 * 5
= { applying * }
15

最内层求值也可以从参数如何传给函数的角度来刻画。特别地，使用这种策略会确保参数总是在函数应用之前被完全求值。也就是说，参数按值传递（passed by value）。例如，如上所示，使用最内层求值计算 mult (1+2,2+3) 时，会先计算参数 1+2 和 2+3，然后再应用 mult。总是选择最靠左的最内层 redex，确保第一个参数先于第二个参数求值。

另一种常见求值策略与最内层求值对偶：总是选择最外层 redex，也就是不包含在其他 redex 中的 redex。如果存在多个这样的 redex，也像前面一样选择开始位置最靠左的那个。毫不意外，这种求值策略称为最外层求值（outermost evaluation）。

例如，表达式 mult (1+2,2+3) 不包含在任何其他 redex 中，因此它本身就是最外层 redex。更一般地，使用最外层求值计算这个表达式会如下进行：

mult (1+2, 2+3)
= { applying mult }
(1+2) * (2+3)
= { applying the first + }
3 * (2+3)
= { applying + }
3 * 5
= { applying * }
15

从参数如何传给函数的角度看，使用最外层求值允许函数在其参数被求值之前就被应用。因此，我们说参数按名传递（passed by name）。例如，如上所示，使用最外层求值计算 mult (1+2,2+3) 时，会先把函数 mult 应用于两个尚未求值的参数 1+2 和 2+3，然后再依次计算这两个表达式。

本节最后注意，即使使用最外层求值，许多内置函数在被应用之前也要求其参数先被求值。例如，如上面的计算所示，像 * 和 + 这样的内置算术运算符，只有在两个参数都已经求值为数字之后才能应用。具有这种性质的函数称为严格函数（strict functions），本章末尾会进一步讨论。

Lambda 表达式

现在定义 mult 的柯里化版本，它一次接收一个参数，并使用 lambda 表达式显式展示柯里化的用法：

mult :: Int -> Int -> Int
mult x = \y -> x * y

例如，使用最内层求值有：

mult (1+2) (2+3)
= { applying the first + }
mult 3 (2+3)
= { applying mult }
(\y -> 3 * y) (2+3)
= { applying + }
(\y -> 3 * y) 5
= { applying the lambda }
3 * 5
= { applying * }
15

也就是说，现在两个参数会一次一个地代入函数 mult 的主体中，正如使用柯里化时所预期的那样，而不是像上一节那样同时代入。出现这种行为，是因为在表达式 mult 3 (2+3) 中，mult 3 是最靠左的最内层 redex；而在表达式 mult (3,2+3) 中则是 2+3。上面计算第二步对 mult 3 执行化简，会得到 lambda 表达式 \y -> 3 * y，它等待第二个参数的求值结果。

注意，在 Haskell 中，不允许选择 lambda 表达式主体内部的 redex。不在 lambda 下化简的理由是：函数被视为黑盒，我们不允许查看其内部。更形式化地说，对函数唯一能执行的操作就是把它应用到参数。因此，只有当函数已经被应用之后，才允许对函数主体内部进行化简。

例如，函数 \x -> 1 + 2 被认为已经完全求值，尽管它的主体包含 redex 1 + 2。但一旦这个函数被应用到某个参数，对这个 redex 的求值就可以继续：

(\x -> 1 + 2) 0
= { applying the lambda }
1 + 2
= { applying + }
3

使用最内层和最外层求值，但不在 lambda 表达式内部求值，通常分别称为按值调用（call-by-value）和按名调用（call-by-name）。接下来两节会比较这两种求值策略在两个重要性质上的差异：终止行为，以及所需的化简步骤数量。

15.3 终止性（Termination）

考虑下面这个递归定义：

inf :: Int
inf = 1 + inf

也就是说，整数 inf（infinity 的缩写）被定义为它自身的后继。无论使用哪种求值策略，对 inf 求值都会产生越来越大的表达式，因此不会终止：

inf
= { applying inf }
1 + inf
= { applying inf }
1 + (1 + inf)
= { applying inf }
1 + (1 + (1 + inf))
= { applying inf }
...

现在考虑包含值 inf 的表达式 fst (0,inf)，其中 fst 是选择一对值中第一个组成部分的库函数，定义为 fst (x,y) = x。对这个表达式使用按值调用求值，会以类似 inf 本身的方式导致不终止：

fst (0, inf)
= { applying inf }
fst (0, 1 + inf)
= { applying inf }
fst (0, 1 + (1 + inf))
= { applying inf }
fst (0, 1 + (1 + (1 + inf)))
= { applying inf }
...

相反，使用按名调用求值只需一步就会以结果零终止，因为它会立即应用 fst 的定义，从而避免对不终止表达式 inf 求值：

fst (0, inf)
= { applying fst }
0

这个简单例子表明：当按值调用求值无法终止时，按名调用求值可能仍能产生结果。更一般地说，我们有下面这个重要性质：如果对于某个表达式存在任何会终止的求值序列，那么按名调用求值也会对这个表达式终止，并产生相同的最终结果。

总之，从尽可能确保求值终止这一目的来说，按名调用优于按值调用。

15.4 化简次数（Number of reductions）

现在考虑下面这个定义：

square :: Int -> Int
square n = n * n

例如，使用按值调用求值有：

square (1+2)
= { applying + }
square 3
= { applying square }
3 * 3
= { applying * }
9

相反，使用按名调用求值需要额外一个化简步骤，因为应用函数 square 时会复制参数表达式 1+2，因此它必须被求值两次：

square (1+2)
= { applying square }
(1+2) * (1+2)
= { applying the first + }
3 * (1+2)
= { applying + }
3 * 3
= { applying * }
9

这个例子表明：按名调用求值可能比按值调用需要更多化简步骤，尤其是在函数主体中一个参数被使用多次时。更一般地说，我们有下面这个性质：在按值调用求值中，参数会被精确求值一次；但在按名调用中，参数可能会被求值多次。

幸运的是，按名调用求值的上述效率问题很容易通过使用指针共享表达式来解决。也就是说，如果某个参数在函数主体中被使用多次，我们并不物理复制该参数，而是只保留这个参数的一份副本，并创建多个指向它的指针。这样，对该参数执行的任何化简都会自动在所有指针之间共享。例如，使用这种策略有：

square (1+2)
= { applying square }
let p = 1+2 in p * p
= { applying + }
let p = 3 in p * p
= { applying * }
9

也就是说，在第一步应用定义 square n = n * n 时，我们保留参数表达式 1+2 的单份副本，并创建两个指向它的引用。这样，在第二步化简表达式 1+2 时，表达式中的两个引用会共享结果。

把按名调用求值与共享结合起来，称为惰性求值（lazy evaluation）。这就是 Haskell 使用的求值策略，因此 Haskell 被称为惰性编程语言。由于基于按名调用求值，惰性求值具有这样一个性质：它确保求值会尽可能多地终止。此外，共享确保惰性求值所需步骤数从不会多于按值调用求值。下一节会解释“惰性”这个术语的含义。

15.5 无限结构（Infinite structures）

按名调用求值以及由此而来的惰性求值还有一个额外性质：它允许我们使用乍看不可能的无限结构来编程。前面已经看到过这个思想的一个简单例子，即对 fst (0,inf) 求值时，会避免产生由 inf 定义的无限结构 1 + (1 + (1 + ...))。

考虑无限列表时，会出现更有趣的行为。例如，考虑下面这个递归定义：

ones :: [Int]
ones = 1 : ones

也就是说，列表 ones 被定义为一个一，后面接着它自身。与 inf 一样，无论使用哪种策略，直接对 ones 求值都不会终止：

ones
= { applying ones }
1 : ones
= { applying ones }
1 : (1 : ones)
= { applying ones }
1 : (1 : (1 : ones))
= { applying ones }
...

实践中，使用 GHCi 求值 ones 会产生一个永不结束的一列表，直到用户最终决定终止这个过程：

> ones
[1,1,1,1,1,1,1,1,1,1,1,...

现在考虑表达式 head ones，其中 head 是选择列表第一个元素的库函数，定义为 head (x:_) = x。在这种情况下，使用按值调用求值也会导致不终止：

head ones
= { applying ones }
head (1 : ones)
= { applying ones }
head (1 : (1 : ones))
= { applying ones }
head (1 : (1 : (1 : ones)))
= { applying ones }
...

相反，使用惰性求值（或者按名调用求值，因为这个例子不需要共享）会在两步中终止：

head ones
= { applying ones }
head (1 : ones)
= { applying head }
1

出现这种行为，是因为惰性求值正如其名，会以惰性的方式进行：只有当确实需要参数来产生结果时，才会对参数求值。例如，选择列表第一个元素时，不需要列表其余部分，因此在 head (1 : ones) 中会避免进一步求值无限列表 ones。更一般地说，我们有下面这个性质：使用惰性求值时，表达式只会按其使用上下文所需的程度被求值。

借助这个思想，现在可以看到，在惰性求值下，ones 并不是一个实际已经完全生成的无限列表，而是一个潜在无限列表；它只会按上下文需要的程度被求值。这个思想并不局限于列表，而是同样适用于 Haskell 中任何形式的数据结构。例如，本章练习会考虑无限树。

15.6 模块化编程（Modular programming）

惰性求值还允许我们在计算中把控制与数据分离。例如，可以通过选择无限一列表（数据）的前三个元素（控制）来产生由三个一组成的列表：

> take 3 ones
[1,1,1]

使用标准 Prelude 中 take 的定义：

take 0 _      = []
take _ []     = []
take n (x:xs) = x : take (n-1) xs

这个行为在惰性求值下会如下产生：

take 3 ones
= { applying ones }
take 3 (1 : ones)
= { applying take }
1 : take 2 ones
= { applying ones }
1 : take 2 (1 : ones)
= { applying take }
1 : 1 : take 1 ones
= { applying ones }
1 : 1 : take 1 (1 : ones)
= { applying take }
1 : 1 : 1 : take 0 ones
= { applying take }
1 : 1 : 1 : []
= { list notation }
[1,1,1]

也就是说，数据只会按控制所需的程度求值，而这两部分会轮流执行化简。没有惰性求值时，控制部分和数据部分就需要合并成一个单独函数，用来产生由 n 个相同元素组成的列表，例如：

replicate :: Int -> a -> [a]
replicate 0 _ = []
replicate n x = x : replicate (n-1) x

能够把程序模块化为逻辑上相互独立的部分，是编程中的重要目标；而能够把控制与数据分离，是惰性求值最重要的好处之一。

注意，使用无限列表编程时仍然需要小心，以避免不终止。例如，表达式：

filter (<= 5) [1..]

其中 [n..] 会产生从 n 开始的无限整数列表。这个表达式会产生整数 1, 2, 3, 4, 5，然后永远循环，因为函数 filter (<= 5) 会继续测试无限列表中的元素，徒劳地寻找另一个小于等于五的元素。相比之下，表达式：

takeWhile (<= 5) [1..]

会产生相同的整数，然后终止，因为 takeWhile (<= 5) 一旦遇到大于五的元素就会停止。

本节最后看一个关于素数的例子。回忆第 5 章中，我们写过一个函数，用于生成不超过给定上限的素数。与之不同，下面是一种生成所有素数这一无限序列的简单过程，而不是生成该序列的某个有限前缀：

• 写下无限序列 2, 3, 4, 5, 6, ...；
• 把序列中的第一个数 p 标记为素数；
• 从序列中删除 p 的所有倍数；
• 回到第二步。

注意，第一步和第三步各自都需要无限工作量，因此实践中这些步骤必须交错进行。这个过程的前几轮可以粗略表示如下：

2  3  4  5  6  7  8  9  10 11 12 13 14 15 ...
3  5  7  9  11 13 15 ...
5  7  11 13 ...
7  11 13 ...
11 13 ...
13 ...

每一行对应过程的一次迭代：第一行是初始序列（第一步）；每行的第一个数被标记为素数（第二步）；在进入下一轮之前，所有这个数的倍数都会被删除（第三步）。通过这种方式，可以想象初始数字序列向下流动，而某些数字在每一阶段被筛掉，标记出的数字形成无限素数序列：

2, 3, 5, 7, 11, 13, ...

上述生成素数的过程称为埃拉托斯特尼筛法，以最先描述它的希腊数学家命名。这个过程可以直接翻译为 Haskell：

primes :: [Int]
primes = sieve [2..]

sieve :: [Int] -> [Int]
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

也就是说，从无限列表 [2..] 开始（第一步），应用函数 sieve，它保留第一个数字 p 作为素数（第二步），然后递归调用自身，参数是通过从这个列表中过滤掉 p 的所有倍数而得到的新列表（第三步和第四步）。惰性求值确保这个程序确实会产生所有素数构成的无限列表：

> primes
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,...

通过把素数生成从有限性的约束中解放出来，我们得到了一个模块化程序，可以在不同情形中搭配不同的控制部分。例如，前十个素数以及小于十的素数可以分别如下产生：

> take 10 primes
[2,3,5,7,11,13,17,19,23,29]

> takeWhile (< 10) primes
[2,3,5,7]

15.7 严格应用（Strict application）

Haskell 默认使用惰性求值，但也提供了一种特殊的严格函数应用版本，写作 $!，它有时很有用。非正式地说，形如 f $! x 的表达式与普通函数应用 f x 行为相同，只是会在应用函数 f 之前，强制先对参数表达式 x 的最外层进行求值。

例如，如果参数具有基本类型，例如 Int 或 Bool，那么最外层求值就是完整求值。另一方面，对于像 (Int,Bool) 这样的对类型，会一直求值到得到一对表达式为止，但不会进一步求值。类似地，对于列表类型，会一直求值到得到空列表或由两个表达式构成的 cons 为止。

更形式化地说，形如 f $! x 的表达式只有在参数 x 按通常的惰性求值方式已经求值到可以知道结果不是未定义值时，才成为 redex；到那时，这个表达式可以被化简为普通应用 f x。例如，使用定义 square n = n * n，应用 square $! (1+2) 的求值会以按值调用的方式进行：先把参数表达式 1+2 求值为值 3，然后再应用函数 square：

square $! (1+2)
= { applying + }
square $! 3
= { applying $! }
square 3
= { applying square }
3 * 3
= { applying * }
9

用于带多个参数的柯里化函数时，严格应用可以强制任意组合参数的最外层求值。例如，如果 f 是带两个参数的柯里化函数，那么形如 f x y 的应用可以改写成三种不同行为：

(f $! x) y    forces top-level evaluation of x
(f x) $! y    forces top-level evaluation of y
(f $! x) $! y forces top-level evaluation of x and y

在 Haskell 中，严格应用主要用于改善程序的空间性能。例如，考虑函数 sumwith，它使用一个累积值来计算整数列表之和：

sumwith :: Int -> [Int] -> Int
sumwith v []     = v
sumwith v (x:xs) = sumwith (v+x) xs

使用惰性求值时有：

sumwith 0 [1,2,3]
= { applying sumwith }
sumwith (0+1) [2,3]
= { applying sumwith }
sumwith ((0+1)+2) [3]
= { applying sumwith }
sumwith (((0+1)+2)+3) []
= { applying sumwith }
((0+1)+2)+3
= { applying the first + }
(1+2)+3
= { applying the first + }
3+3
= { applying + }
6

注意，整个求和表达式 ((0+1)+2)+3 会在任何组成加法实际执行之前被构造出来。更一般地说，sumwith 会构造一个大小与原始列表中整数数量成比例的求和表达式；对于长列表，这可能需要大量空间。实践中，更希望每个加法一旦被引入就立即执行，以改善函数的空间性能。

可以通过使用严格应用重新定义 sumwith 来实现这种行为，强制求值它的累积值：

sumwith v []     = v
sumwith v (x:xs) = (sumwith $! (v+x)) xs

例如，现在有：

sumwith 0 [1,2,3]
= { applying sumwith }
(sumwith $! (0+1)) [2,3]
= { applying + }
(sumwith $! 1) [2,3]
= { applying $! }
sumwith 1 [2,3]
= { applying sumwith }
(sumwith $! (1+2)) [3]
= { applying + }
(sumwith $! 3) [3]
= { applying $! }
sumwith 3 [3]
= { applying sumwith }
(sumwith $! (3+3)) []
= { applying + }
(sumwith $! 6) []
= { applying $! }
sumwith 6 []
= { applying sumwith }
6

由于使用严格应用带来了额外开销，这个求值过程比之前需要更多步骤，但现在每个加法一经引入就会执行，而不是构造一个很大的求和表达式。

从上面的例子推广开来，库 Data.Foldable 提供了高阶库函数 foldl 的严格版本，它会在处理列表尾部之前强制求值累积值：

foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f v []     = v
foldl' f v (x:xs) = ((foldl' f) $! (f v x)) xs

例如，使用这个函数可以定义 sumwith = foldl' (+)。不过，重要的是要注意：严格应用并不是自动改善 Haskell 程序空间行为的万能办法。即使对相对简单的例子，使用严格应用也是一个专门主题，需要仔细考虑惰性求值的行为。

15.8 章注（Chapter remarks）

关于求值顺序及其性质的更多细节可见文献 [29]；关于使用惰性求值进行模块化编程的更多例子，可见经典文章 Why Functional Programming Matters [30]。文献 [31] 给出了惰性求值的形式化含义，文献 [32] 则是关于高效实现惰性求值的综合教程。

15.9 练习（Exercises）

1. 找出下面表达式中的 redex，并判断每个 redex 是最内层、最外层、二者皆是，还是二者皆非：

1 + (2*3)
(1+2) * (2+3)
fst (1+2, 2+3)
(\x -> 1 + x) (2*3)

2. 说明为什么在求值表达式 fst (1+2,2+3) 时，最外层求值优于最内层求值。
3. 给定定义 mult = \x -> (\y -> x * y)，说明如何把 mult 3 4 的求值分解为四个独立步骤。
4. 使用列表推导式，定义表达式 fibs :: [Integer]，生成无限 Fibonacci 数列：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

使用下面这个简单过程：

• 前两个数是 0 和 1；
• 下一个数是前两个数之和；
• 回到第二步。

提示：使用库函数 zip 和 tail。注意，Fibonacci 数列中的数字很快会变大，因此上面使用任意精度整数类型 Integer。

5. 为下面这种二叉树类型定义合适版本的库函数 repeat、take 和 replicate：

repeat :: a -> [a]
repeat x = xs where xs = x:xs

take :: Int -> [a] -> [a]
take 0 _      = []
take _ []     = []
take n (x:xs) = x : take (n-1) xs

replicate :: Int -> a -> [a]
replicate n = take n . repeat

树类型如下：

data Tree a = Leaf | Node (Tree a) a (Tree a)
    deriving Show

6. 用牛顿方法计算非负浮点数 n 的平方根，可以表示如下：

• 从一个初始近似值开始；
• 给定当前近似值 a，下一个近似值由函数 next a = (a + n/a) / 2 定义；
• 重复第二步，直到最近两个近似值之间的距离在某个期望范围之内，此时把最近的值作为结果返回。

定义函数 sqroot :: Double -> Double 来实现这个过程。提示：先使用库函数 iterate 产生一个无限近似值列表。为简单起见，把数字 1.0 作为初始近似值，把 0.00001 作为距离值。

练习 1-3 的解答见附录 A。