11.4.1 无穷列表

这一节的标题听起来可能有点奇怪（或疯狂），所以，需要解释一下。函数式列表是我们经常使用的一种数据结构。如果我们想要表示逻辑上无穷的列表，例如，所有质数的列表。当然，我们不可能用到所有的数字，只是像这样使用数据结构，而不必考虑长度。如果列表是无穷的，我们就能够访问尽可能多的数字，只要我们需要。

除了数学上的挑战以外，同样的概念在许多主流编程中也是有用的。当我们在第四章绘制饼图时，用的是随机颜色，而如果使用以无穷列表方式生成颜色，会使得图表外观清晰。在下一章，我们将会看到所有这些例子，但现在，我们要把这种用延迟值表示出来。

在内存中存储无穷数字的列表，就是非常棘手的问题。很明显，我们不可能完整地存储完整的数据结构，因此，需要存储一部分，而其余部分用延迟计算表示。我们已经知道，用延迟值表示延迟计算的部分是一个好方法。

表示简单的无穷列表的方法，与普通列表类似，单元格包含一个值和对列表其余部分[的引用]；唯一不同的是，列表的其余部分需要延迟计算，当执行的时候，会给出另一个单元格。在 F# 中，我们使用差别联合来表示这种列表，如清单 11.19 所示。

清单 11.19 整数的无穷列表 (F#)

type InfiniteInts =

  |LazyCell of int *     [1]

           Lazy<InfiniteInts>    [2]

这个差别联合只有一个识别器，因此，与记录类似。当然，我们可以用记录来写代码，但对于这个示例，用差别联合更方便，因为我们可以用优美的模式匹配语法，来提取包含的值。唯一的识别器称LazyCell（延迟单元格），在单元格存储了当前值[1]，以及对“尾”的引用[2]。尾是延迟值，因此，将在需要时进行计算。用这种方式，当我们计算单元格时，通过逐个单元格就能计算出列表，结果会被缓存起来。

F# 和 Haskell 中的延迟列表

如前所述，Haskell 中各处都使用延迟计算，因此，Haskell 中标准的列表类型，自动就是延迟的，尾直到值在代码中被访问时才计算。

而在 F# 中，延迟列表的使用并不非常频繁。在下一章，我们将会看到用 F# 以及 C# 2.0，以更优雅方法写无穷集合。F# 对延迟列表的实现方法，与我们在这一节实现的类型相似，在 LazyList FSharp.PowerPack.dll 库中可以找到LazyList<‘a>。

已经有了我们自己的类型以后，就可以用它来创建简单的无穷列表，存储整数0、1、2、3…了。清单 11.20 演示了如何访问列表中的值。

清单 11.20 创建包含 0, 1, 2, 3, 4, … 的列表(F# Interactive)

> let rec numbers(num) =   [1]

    LazyCell(num, lazy numbers(num + 1));;  <-- 创建下一个单元格为延迟计算

val numbers : int -> InfiniteInts

> numbers(0);;   [2]

val nums : InfiniteInts = LazyCell(0, Valueis not created.)

> let next(LazyCell(hd, tl)) =   [3]

    tl.Value;;   <-- 计算表示下一个单元格的延迟值

val next : InfiniteInts -> InfiniteInts

> numbers(0) |> next |> next |>next |> next |> next;;   <-- 访问列表中的六个值

val nums : InfiniteInts = LazyCell(5, Valueis not created.)

我们首先写一个递归函数 numbers [1]，它返回整数的无穷列表，从作为参数值给定的数字开始，直到无穷。返回的单元格包含第一个值和尾，尾是延迟值，（在计算时）递归方式调用 numbers，得到下一个单元格。

如果我们以 0 作为参数值，调用函数，得到从 0 开始的无穷列表[2]。F# Interactive 的输出可读性不强，但可以发现，第一个值是 0，尾是 <InfiniteInts> 类型的值。随后的命令声明函数 next，得到列表中下一个单元格[3]。我们使用声明中的模式匹配，来分解唯一的参数值。这看起来有点怪，因为我们通常不使用只有一个识别器的差别联合，但与把元组分解组件的原理是相同的。在函数体中，我们读取 Value 属性，计算下一个单元格。最后一行多次使用 next 函数，从列表中读第六次值。

我们可以用延迟列表做更多的事情，但是，在这里我们不会太深入，在下一章，我们会看到F# 更多的习惯用法。有些情况下，LazyList<‘T> 类型是很有用的。虽然我们没有直接使用 F#库中的类型，只要懂得了原理，使用起来也不会有问题。

在这一节介绍无穷数据结构中，我们更多地关注了函数式风格，甚至没有展示 C# 示例。因为我们知道可以用 C# 写延迟值，那么，用 C# 写出同样的类型，是有可能的；而在下一章，我们将用更自然的方式，在 C# 中表示无穷结构或者流的值。

在此示例中，延迟列表有一个很重要方面。只要我们在某一点计算过列表，计算的值在内存中一直可用，因此，不必要每次重新计算。正如我们在下一节将要看到，延迟值的这个特征可以用作简单而优雅的缓存机制。

写处理无穷列表的函数

处理标准的列表类型时，我们可以用函数，如 List.map 和 List.filter；对于无穷列表，我们也可以实现同样的函数，但是，当然不是所有的都可以。例如，List.fold 和 List.sort 需要读所有元素，而对于延迟列表灭族，这是不可能的。作为一个可能的例子，这里实现了 map 函数：

let rec map f (LazyCell(hd, tl)) =

 LazyCell(f(hd), lazy map f tl.Value)

结构类似于正常的 map 函数，把给定的函数应用到单元格中的第一个值，然后，递归处理列表中的其余部分。对尾的处理，由于使用 lazy 关键字而延迟。其他常见的列表处理函数也类似。

11.4.1 无穷列表