序列

介绍

序列非常像列表。但是，从实用的角度来看，应该想象它们可能是无限的。这是理解和使用序列的关键直觉。为了实现这一点，序列元素按需计算，而不是存储在内存中。也许更常见的是，序列也允许将内存消耗从线性空间减少到常数空间。

看待 'a Seq.t 类型的值的一种方式是将其视为列表，但当它不为空时有一个变化：它的尾部被冻结。为了理解这个类比，请考虑标准库中序列是如何定义的。

type 'a node =
  | Nil
  | Cons of 'a * 'a t
and 'a t = unit -> 'a node

这是两种类型的互递归定义：Seq.node，它几乎与 list 相同

type 'a list =
  | []
  | (::) of 'a * 'a list

以及 Seq.t，它仅仅是 unit -> 'a Seq.node 的类型别名。这个定义的要点是 Seq.Cons 的第二个组件的类型，它是一个返回序列的函数，而它的 list 对应部分是一个列表。让我们比较 list 和 Seq.node 的构造函数。

1. 空列表和序列以相同的方式定义，一个没有参数的构造函数：Seq.Nil 和 []。
2. 非空列表和序列都是对，其前一个成员是一段数据。
3. 但是，列表中的后一个成员是递归的 list，而在序列中，它是一个返回 Seq.node 的函数。

Seq.t 类型的值是“冻结的”，因为其中包含的数据无法立即使用。必须提供一个 unit 值才能恢复它，我们可以将其视为“解冻”。但是，解冻只能访问序列的尖端，因为 Seq.Cons 的第二个参数也是一个函数。

由函数尾部冻结解释了为什么序列可以被认为是潜在的无限的。在序列中找到 Seq.Nil 值之前，不能确定是否会永远出现。序列可以是服务器中的传入请求流、嵌入式传感器的读数或系统日志。所有这些都具有不可预知的中止，并且将它们视为潜在的无限更容易。

在 OCaml 中，任何类型为 t 的值 a 可以通过编写 fun _ -> a 或 fun () -> a 转换为常量函数。后一个函数称为 thunk。使用这个术语，Seq.t 值是 thunk。用前面的类比来说，a 在它的 thunk 中被冻结了。

以下是构建看似无限的整数序列的方法

# let rec ints n : int Seq.t = fun () -> Seq.Cons (n, ints (n + 1));;
val ints : int -> int Seq.t = <fun>

函数 ints n 看起来像是构建无限序列 (n; n + 1; n + 2; n + 3;...)。实际上，由于机器整数有界限，因此序列不会无限增加。当达到 max_int 时，它将循环下降到 min_int。

OCaml 标准库包含一个名为 Seq 的序列模块。它包含一个 Seq.iter 函数，它与 List.iter 具有相同的行为。这样写

# Seq.iter print_int (ints 0);;

在 OCaml 顶层意味着“永远打印整数”，并且您必须按 Ctrl-C 中断执行。以下代码是相同的无限循环，没有任何输出

# Seq.iter ignore (ints 0);;

关键点是：它不会泄漏内存。这个例子在常数空间运行。它实际上只是一段无限循环，这可以通过监控程序的空间消耗并注意到它永远旋转而不会崩溃来确认。而使用列表 let rec ints n = n :: ints (n + 1) 的版本将分配一个长度与运行时间成正比的列表，因此会很快由于内存不足而崩溃。

例子

OCaml 标准库的 Seq 模块包含函数 Seq.take 的定义，该函数从序列的开头返回指定数量的元素。这是一个简化的实现

let rec take n seq () =
  if n <= 0 then
    Seq.Nil
  else
    match seq () with
    | Seq.Cons (x, seq) -> Seq.Cons (x, take (n - 1) seq)
    | _ -> Seq.Nil

take n seq 函数返回序列 seq 的前 n 个元素，最多返回 n 个。如果 seq 包含少于 n 个元素，则返回相同的序列。特别是，如果 seq 为空，或 n 为负数，则返回空序列。

观察 take 函数的第一行，这是序列递归函数的常用模式。最后两个参数是

• 一个名为 seq 的序列
• 一个 unit 值

执行时，该函数首先解冻 seq（即调用 seq ()），然后进行模式匹配以查看可用数据的内部。然而，除非将 unit 参数传递给 take，否则不会发生这种情况。写 take 10 seq 不会计算任何东西，它是一个部分应用，返回一个函数，需要一个 unit 来产生结果。

这可以用于打印整数，而不会像之前那样无限循环。

# Seq.ints 0 |> Seq.take 43 |> List.of_seq;;
- : int list =
[0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21;
 22; 23; 24; 25; 26; 27; 28; 29; 30; 31; 32; 33; 34; 35; 36; 37; 38; 39; 40;
 41; 42]

Seq 模块还有一个函数 Seq.filter

# Seq.filter;;
- : ('a -> bool) -> 'a Seq.t -> 'a Seq.t = <fun>

它构建一个满足条件的元素序列。

使用 Seq.filter 并借鉴 试除法 算法，可以定义一个函数，该函数似乎可以生成所有素数的列表。

let rec trial_div seq () = match seq () with
  | Seq.Cons (m, seq) -> Seq.Cons (m, trial_div (Seq.filter (fun n -> n mod m > 0) seq))
  | seq -> seq
let primes = Seq.ints 2 |> trial_div;;
val trial_div : int Seq.t -> int Seq.t = <fun>
val primes : int Seq.t = <fun>

例如，以下是前 100 个素数的列表

# primes |> Seq.take 100 |> List.of_seq;;
- : int list =
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;
 73; 79; 83; 89; 97; 101; 103; 107; 109; 113; 127; 131; 137; 139; 149; 151;
 157; 163; 167; 173; 179; 181; 191; 193; 197; 199; 211; 223; 227; 229; 233;
 239; 241; 251; 257; 263; 269; 271; 277; 281; 283; 293; 307; 311; 313; 317;
 331; 337; 347; 349; 353; 359; 367; 373; 379; 383; 389; 397; 401; 409; 419;
 421; 431; 433; 439; 443; 449; 457; 461; 463; 467; 479; 487; 491; 499; 503;
 509; 521; 523; 541]

trial_div 函数在 OCaml 中是递归的，也是常识性的。它使用 rec 关键字定义，并调用自身。然而，有些人将这种类型的函数称为 协递归。这个词用于强调，尽管它可能不会终止，但它可以无限地产生有效的输出。

展开序列

标准的高阶迭代函数在序列上可用。例如

• Seq.iter
• Seq.map
• Seq.fold_left

所有这些函数也适用于 Array、List 和 Set，并且行为基本相同。注意，没有 fold_right 函数。从 OCaml 4.11 开始，有一个在其他类型上（尚未）可用的东西：unfold。以下是它的实现方式

let rec unfold f x () = match f x with
  | None -> Seq.Nil
  | Some (x, seq) -> Seq.Cons (x, unfold f seq)

以下是它的类型

val unfold : ('a -> ('b * 'a) option) -> 'a -> 'b Seq.t = <fun>

与前面提到的迭代器不同，Seq.unfold 没有序列参数，而是序列结果。unfold 提供了一种构建序列的通用方法。Seq.unfold f x 返回的结果是通过累积对 f 的连续调用结果而构建的序列，直到它返回 None 为止。这是

(fst p₀, fst p₁, fst p₂, fst p₃, fst p₄, ...)

其中 Some p₀ = f x 且 Some pₙ₊₁ = f (snd pₙ)。

例如，Seq.ints 可以使用 Seq.unfold 以相当紧凑的方式实现

# let ints = Seq.unfold (fun n -> Some (n, n + 1));;
val ints : int -> int Seq.t = <fun>

有趣的是，应该观察到序列上的 map 可以使用 Seq.unfold 来实现。以下是编写它的方法

# let map f = Seq.unfold (fun seq -> seq |> Seq.uncons |> Option.map (fun (x, seq) -> (f x, seq)));;
val map : ('a -> 'b) -> 'a Seq.t -> 'b Seq.t = <fun>

以下是快速检查

# Seq.ints 0 |> map (fun x -> x * x) |> Seq.take 10 |> List.of_seq;;
- : int list = [0; 1; 4; 9; 16; 25; 36; 49; 64; 81]

Seq.uncons 函数返回序列的头部和尾部，如果序列非空。否则，它返回 None。

使用此函数

let input_line_opt chan =
  try Some (input_line chan, chan)
  with End_of_file -> None

可以使用 Seq.unfold 读取文件

let cin = open_in "README.md" in
cin |> Seq.unfold input_line_opt |> Seq.iter print_endline;
close_in cin

序列是函数

Seq 模块包含以下定义

val cons : 'a -> 'a Seq.t -> 'a Seq.t

虽然 Seq.cons x seq 和 Seq.Cons (x, seq) 相同，但 Seq.cons 是一个函数，而 Seq.Cons 是一个变体的构造函数，在 OCaml 中并不相同。这会导致一些微妙的错误。本节说明了这一点。

虽然这看起来是定义 斐波那契数列 的一种可能方法

# let rec fibs m n = Seq.cons m (fibs n (n + m));;
val fibs : int -> int -> int Seq.t = <fun>

但实际上并非如此。它是一个无休止的递归，会耗尽堆栈。

# fibs 0 1;;
Stack overflow during evaluation (looping recursion?).

此定义按预期工作（找出差异，有四个）

# let rec fibs m n () = Seq.Cons (m, fibs n (n + m));;
val fibs : int -> int -> int Seq.t = <fun>

它可以用来生成一些斐波那契数

# fibs 0 1 |> Seq.take 10 |> List.of_seq;;
- : int list = [0; 1; 1; 2; 3; 5; 8; 13; 21; 34]

为什么呢？关键的区别在于递归调用 fibs n (n + m)。在第一个定义中，应用是完整的，因为 fibs 收到了它期望的所有参数。在第二个定义中，应用是不完整的，因为缺少 () 参数。由于 OCaml 中的求值是 急切求值，在第一个情况下，会触发递归调用的求值，并出现非终止循环。相反，在第二个情况下，部分应用的函数会立即作为 闭包 返回。

序列是函数，正如它们的类型所表明的那样

# #show Seq.t;;
type 'a t = unit -> 'a Seq.node

处理序列的函数必须相应地编写。

• 序列消费者：部分应用的函数参数
• 序列生产者：部分应用的函数结果

当处理序列的代码行为异常时，例如崩溃或挂起，很有可能像 fibs 的第一个定义中那样发生了错误。

用于转换的序列

在整个标准库中，序列被用作桥梁，用于在许多数据类型之间进行转换。例如，以下是一些这些函数的签名

• 列表

  val List.to_seq : 'a list -> 'a Seq.t
  val List.of_seq : 'a Seq.t -> 'a list
  

• 数组

  val Array.to_seq : 'a array -> 'a Seq.t
  val Array.of_seq : 'a Seq.t -> 'a array
  

• 字符串

  val String.to_seq : string -> char Seq.t
  val String.of_seq : char Seq.t -> string
  

类似的函数也适用于集合、映射、哈希表 (Hashtbl) 等。在实现数据类型模块时，建议公开 to_seq 和 of_seq 函数。

杂项注意事项

有几个相关的库，都提供了处理大量数据流的方法

• Rizo I 流
• Simon Cruanes 和 Gabriel Radanne Iter
• Simon Cruanes OSeq（Seq 的扩展，包含更多函数）
• Jane Street Base.Sequence

OCaml 标准库中曾经有一个名为 Stream 的模块。它在 2021 年的 OCaml 4.14 版本中被 删除。注意，在之前编写的书籍和文档中可能仍然提到它。