6.2. 惰性列表¶
6.2.1. 无限序列¶
实现按名调用
宏扩展可以通过双重文本替换（如 C++ 预处理器）或通过单次替换和动态作用域来实现。结果是调用者环境中对整个函数体进行求值。但是如何实现按名调用呢？如何在调用者环境中求值参数，而在被调用者环境中求值函数的其余部分？
我们不是简单地传递参数的文本表示，而是传递一个不带参数的匿名函数，该函数返回参数。这种匿名函数被称为 thunk。
理解在调用函数之前评估参数与传递 thunk 之间的区别，就是理解
和
前者，当作为参数传递时，已经求值。函数可以使用该值，而无需对其做任何其他操作。然而，后者，当作为参数传递时，需要调用 thunk 来“解包”函数在其计算中应使用的值。
与在调用函数之前评估参数并使用该值不同，每次在函数体中引用参数时，都会评估 thunk 以获取参数的值。评估过程通常被称为 解冻 thunk。
如果 thunk 包含对自由变量的引用，例如以下示例中的 x：
此时，被调用函数（即接收 thunk 作为参数的函数）将能够访问在调用者环境中定义的自由变量。这是因为 thunk 是一个函数，换句话说，它是一个闭包，包含了创建 thunk 时存在的环境（即包含 x 定义的调用者环境）。
按名调用的列表
为了说明 thunk 的用法，我们将实现按名调用的列表，这种方式与 Haskell 中默认使用的列表方式类似，或者作为程序员在 Python 和 Scala 中选择的选项。按名调用的列表本质上给你提供了 惰性列表，我们会看到它们也可以被视为“无限序列”。这种视角提供了一种非常不同的方法来处理此类列表。
下面是我们即将在无限序列 JavaScript 模块中提供的部分函数的文档，该模块称为 is 模块。
序列的构造函数（即 cons 函数）接受两个参数，即我们希望在序列头部放置的元素，以及一个延迟求值的 thunk，该 thunk 若需要访问第一个元素之后的部分则返回序列的尾部。 为了简化起见，我们只操作整数无限序列。
// Construct a new sequence comprised of the given integer and thunk
var cons = function (n,thunk) { ... };
// Get the first integer in the sequence
var hd = function (seq) { ... };
// Get the infinite sequence following the first element. This
// will itself be in the form of an integer followed by a thunk
var tl = function (seq) { ... };
// Return the (finite, non-lazy) list containing the first n
// integers in the given sequence
var take = function (seq,n) { ... };
以下幻灯片演示了我们如何利用这些操作来构建并暴露无限个 1 的序列的若干部分。
现在让我们关注 is 模块中这四个基本函数，即 cons, hd, tl 和 take，是如何实现的。惰性列表的底层表示是一个二元素数组 seq。seq[0] 存储列表的头部（已经求值），seq[1] 存储必须求值才能展现出列表其余部分的 thunk。
// Construct a new sequence comprised of the given integer and thunk
var cons = function (x, thunk) {
return [x, thunk];
};
// Get the first integer in the sequence
var hd = function (seq) {
return seq[0];
};
// Get the infinite sequence following the first element. This
// will itself be in the form of an integer followed by a thunk
var tl = function (seq) {
return thaw(seq[1]);
};
// thaw is a helper function for tl. It returns the result
// of evaluating the function given as argument
var thaw = function (thunk) { return thunk(); };
// Return the (finite, non-lazy) list containing the first n
// integers in the given sequence
var take = function (seq, n) {
if (n === 0)
return [];
else {
// Get a copy of the result of recursive call with n - 1
var result = take(tl(seq), n - 1).slice(0); // slice(0) gives a copy of the array
// And use Javascript's unshift to put the hd at the beginning of result
result.unshift(hd(seq));
return result;
}
};
到目前为止，我们所能创建的序列仅是一个由全 1 组成的无聊序列。为了更容易构造更有趣的序列，除了 cons、hd、tl 和 take 之外， is 模块还提供了一些工具函数，它们是有限列表（我们的 fp 模块）中对应函数的“无限类似物”。这些工具函数（即 from、map、filter、iterates 和 drop）将在下方讨论并演示。
from 操作：
map 操作
filter 操作
drop 操作：
iterates 操作：
埃拉托斯特尼筛法：利用惰性列表的一个示例
计算各种素数的需求出现在多种应用中，例如公钥加密。一种早已为人所知的、以合理效率计算不超过上限 n 的所有素数的技术是 埃拉托斯特尼筛法。下面的幻灯片演示了在具有及早求值（而非惰性求值）的语言中该筛法的算法。
然而，从该算法的实用性角度来看，存在一个问题。想一想它对可能提出的素数请求响应得如何。虽然它能处理“找出所有小于等于 n 的素数”这样的请求，但在“找出前 1000 个素数”或“找出大于 10 亿的第一个素数”这样的请求上就力不从心。原因在于，该算法底层及早求值受限于它所获得的有限值 n。而另一方面，用惰性求值处理列表，我们不必受制于有限的 n，可以构造素数的无限序列，依靠反复应用 thunk 来到达序列中任意需要的位置。下面的幻灯片演示了如何用惰性列表实现埃拉托斯特尼筛法。
按需调用
我们的无限序列的按名调用实现与 Haskell 中的实现方式有何不同？在 Haskell 中， is.tl 和 is.take 函数的对应实现使用的是 按需调用 而非 按名调用。在按需调用中，当 thunk 第一次被解冻后，其返回值会被存储（即缓存）。这样做效率更高，因为 thunk 永远不会被解冻超过一次。
现在，机会来了，你可以在以下问题中练习无限序列。
以下问题将帮助你更好地理解创建按名调用无限序列的代码。
6.2.2. 练习无限序列¶
以下问题将帮助您编写递归代码来处理无限序列。要获得该问题的学分，您必须连续三次正确完成这个随机问题。
6.2.3. 练习与无限序列 (2)¶
以下问题回顾了序列的递归定义。要获得该问题的学分，你必须连续三次正确完成这个随机化问题。
6.2.4. 练习与无限序列（3）¶
以下问题涉及序列递归定义的另一个例子。
