模块 Seq

module Seq: sig .. end

序列。

类型为 'a Seq.t 的序列可以被认为是 延迟列表，也就是说，只有在消费者需要时才会计算其元素的列表。这使得序列能够延迟生成和转换（一次一个元素），而不是急切地（所有元素一次性）。这也使得构建概念上无限的序列成为可能。

类型 'a Seq.t 被定义为 unit -> 'a Seq.node 的同义词。这是一个函数类型：因此它是 opaque 的。消费者可以 查询序列以请求下一个元素（如果有），但不能以任何其他方式检查序列。

由于它是 opaque 的，类型 'a Seq.t 不 揭示序列是否

  • 持久性，这意味着序列可以被使用任意多次，每次都产生相同的元素，就像不可变列表一样；或者
  • 短暂的，这意味着序列不是持久的。查询短暂的序列可能会产生可观察到的副作用，例如增加可变计数器。作为一个常见的特例，短暂的序列可以是 仿射的，这意味着它最多只能被查询一次。

它也不 揭示序列的元素是否

  • 预先计算并存储在内存中，这意味着查询序列是便宜的；
  • 第一次被要求时计算，然后存储在内存中，这意味着第一次查询序列可能很昂贵，但再次查询同一个序列就很便宜了；或者
  • 每次被要求时都重新计算，这可能便宜也可能不便宜。

程序员有责任牢记这些区别，以便了解序列的时间和空间需求。

为了简便起见，以下大多数文档是在隐含假设当前序列是持久的条件下编写的。我们通常不会指出何时或多少次每个函数被调用，因为这将过于冗长。例如，在map 的描述中，我们写道：“如果 xs 是序列 x0; x1; ...，那么 map f xs 是序列 f x0; f x1; ...”。如果我们想要更加明确，我们可以指出转换是在需要时进行的：也就是说，map f xs 的元素只有在被要求时才会被计算。换句话说，定义 let ys = map f xs 会立即终止，不会调用 f。函数调用 f x0 只有在 ys 的第一个元素被要求时才会进行，通过函数调用 ys()。此外，调用 ys() 两次会导致 f x0 也被调用两次。如果希望 f 对 xs 的每个元素最多应用一次，即使在 ys 被查询多次的情况下，那么应该使用 let ys = memoize (map f xs)。

作为一般规则，构建序列的函数，例如 map、filter、scan、take 等，会产生只有在需要时才会计算其元素的序列。急切地使用序列的函数，例如 is_empty、find、length、iter、fold_left 等，是强制计算发生的函数。

在可能的情况下，我们建议使用序列而不是分配器（类型为 unit -> 'a option 的函数，它们在需要时产生元素）。虽然序列可以是持久的或短暂的，但分配器总是短暂的，并且通常比序列更难使用。提供了两个转换函数，Seq.to_dispenser 和 Seq.of_dispenser。

type 'a t = unit -> 'a node

一个类型为 'a t 的序列 xs 是一个延迟列表，其中包含类型为 'a 的元素。这样的序列可以通过执行函数应用 xs() 来查询。此函数应用返回一个节点，使调用者能够确定序列是空的还是非空的，并且在后一种情况下，可以获取其头部和尾部。

type 'a node =
| Nil
| Cons of 'a * 'a t

一个节点要么是 Nil，这意味着序列是空的，要么是 Cons (x, xs)，这意味着 x 是序列的第一个元素，xs 是序列的剩余部分。

使用序列

本节中的函数会使用它们的实参，一个序列，作为部分或完全使用。

类似地，在使用两个序列的函数中，可以区分两组

使用两个序列的函数可以应用于两个长度不同的序列：在这种情况下，较长序列中多余的元素会被忽略。（可能会要求一个多余的元素，即使该元素没有被使用）。

本节中的任何函数都不是延迟的。这些函数是消费者：它们会强制执行一些计算。

val is_empty : 'a t -> bool

is_empty xs 确定序列 xs 是否为空。

建议序列 xs 是持久的。实际上，is_empty xs 会要求序列 xs 的头部，因此，如果 xs 是短暂的，那么在调用后，xs 可能无法再被使用。

val uncons : 'a t -> ('a * 'a t) option

如果 xs 为空，则 uncons xs 为 None。

如果 xs 不为空，则 uncons xs 为 Some (x, ys)，其中 x 是序列的头部，ys 是其尾部。

val length : 'a t -> int

length xs 是序列 xs 的长度。

序列 xs 必须是有限的。

val iter : ('a -> unit) -> 'a t -> unit

iter f xs 会依次调用 f x，针对序列 xs 中的每个元素 x，从左到右。

它只有在序列 xs 是有限的时才会终止。

val fold_left : ('acc -> 'a -> 'acc) -> 'acc -> 'a t -> 'acc

fold_left f _ xs 会依次调用 f _ x，针对序列 xs 中的每个元素 x，从左到右。

一个类型为 'a 的累加器会贯穿调用 f 的过程。

它只有在序列 xs 是有限的时才会终止。

val iteri : (int -> 'a -> unit) -> 'a t -> unit

iteri f xs 会依次调用 f i x，针对序列 xs 中位于索引 i 的每个元素 x。

它只有在序列 xs 是有限的时才会终止。

iteri f xs 等同于 iter (fun (i, x) -> f i x) (zip (ints 0) xs)。

val fold_lefti : ('acc -> int -> 'a -> 'acc) -> 'acc -> 'a t -> 'acc

fold_lefti f _ xs 会依次调用 f _ i x，针对序列 xs 中位于索引 i 的每个元素 x。

一个类型为 'b 的累加器会贯穿调用 f 的过程。

它只有在序列 xs 是有限的时才会终止。

fold_lefti f accu xs 等同于 fold_left (fun accu (i, x) -> f accu i x) accu (zip (ints 0) xs)。

val for_all : ('a -> bool) -> 'a t -> bool

for_all p xs 确定序列 xs 中的所有元素 x 是否都满足 p x。

序列 xs 必须是有限的。

val exists : ('a -> bool) -> 'a t -> bool

exists xs p 确定序列 xs 中至少有一个元素 x 是否满足 p x。

序列 xs 必须是有限的。

val find : ('a -> bool) -> 'a t -> 'a option

find p xs 返回 Some x，其中 x 是序列 xs 中第一个满足 p x 的元素，如果存在这样的元素。

如果不存在这样的元素，则返回 None。

序列 xs 必须是有限的。

val find_index : ('a -> bool) -> 'a t -> int option

find_index p xs 返回 Some i，其中 i 是序列 xs 中第一个满足 p x 的元素的索引，如果存在这样的元素。

如果不存在这样的元素，则返回 None。

序列 xs 必须是有限的。

val find_map : ('a -> 'b option) -> 'a t -> 'b option

find_map f xs 返回 Some y，其中 x 是序列 xs 中第一个使得 f x = Some _ 成立的元素，如果存在这样的元素，并且 y 由 f x = Some y 定义。

如果不存在这样的元素，则返回 None。

序列 xs 必须是有限的。

val find_mapi : (int -> 'a -> 'b option) -> 'a t -> 'b option

与 find_map 相同，但谓词以元素的索引作为第一个参数（从 0 开始计数），以元素本身作为第二个参数。

序列 xs 必须是有限的。

val iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit

iter2 f xs ys 对从序列 xs 和 ys 同步提取的每一对元素 (x, y) 依次调用 f x y。

如果序列 xs 和 ys 长度不同，则迭代在其中一个序列耗尽时停止；另一个序列中多余的元素将被忽略。

只有在序列 xs 和 ys 中至少有一个序列是有限的时候，迭代才会终止。

iter2 f xs ys 等价于 iter (fun (x, y) -> f x y) (zip xs ys)。

val fold_left2 : ('acc -> 'a -> 'b -> 'acc) -> 'acc -> 'a t -> 'b t -> 'acc

fold_left2 f _ xs ys 对从序列 xs 和 ys 同步提取的每一对元素 (x, y) 依次调用 f _ x y。

一个类型为 'a 的累加器会贯穿调用 f 的过程。

如果序列 xs 和 ys 长度不同，则迭代在其中一个序列耗尽时停止；另一个序列中多余的元素将被忽略。

只有在序列 xs 和 ys 中至少有一个序列是有限的时候，迭代才会终止。

fold_left2 f accu xs ys 等价于 fold_left (fun accu (x, y) -> f accu x y) (zip xs ys)。

val for_all2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool

for_all2 p xs ys 确定从序列 xs 和 ys 同步提取的每一对元素 (x, y) 是否满足 p x y。

如果序列 xs 和 ys 长度不同，则迭代在其中一个序列耗尽时停止；另一个序列中多余的元素将被忽略。特别地，如果 xs 或 ys 为空，则 for_all2 p xs ys 为真。 这是 for_all2 和 equal 的区别所在：equal eq xs ys 只有在 xs 和 ys 长度相同时才可能为真。

序列 xs 和 ys 中至少有一个必须是有限的。

for_all2 p xs ys 等价于 for_all (fun b -> b) (map2 p xs ys)。

val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool

exists2 p xs ys 确定从序列 xs 和 ys 同步提取的某一对元素 (x, y) 是否满足 p x y。

如果序列 xs 和 ys 长度不同，则迭代必须在其中一个序列耗尽时停止；另一个序列中多余的元素将被忽略。

序列 xs 和 ys 中至少有一个必须是有限的。

exists2 p xs ys 等价于 exists (fun b -> b) (map2 p xs ys)。

val equal : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool

假设函数 eq 在元素上定义了一个相等性，equal eq xs ys 确定序列 xs 和 ys 是否逐点相等。

序列 xs 和 ys 中至少有一个必须是有限的。

val compare : ('a -> 'b -> int) -> 'a t -> 'b t -> int

假设函数 cmp 在元素上定义了一个预序，compare cmp xs ys 根据字典序预序比较序列 xs 和 ys。

有关比较函数的更多详细信息，请参见 Array.sort.

序列 xs 和 ys 中至少有一个必须是有限的。

构建序列

本节中的函数是惰性的：也就是说，它们返回的序列只有在需要时才会计算其元素。

val empty : 'a t

empty 是空序列。 它没有元素。 它的长度为 0。

val return : 'a -> 'a t

return x 是唯一的元素为 x 的序列。 它的长度为 1。

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

cons x xs 是以元素 x 开头的序列，后面跟着序列 xs。

写 cons (f()) xs 会导致函数调用 f() 立即发生。 为了推迟此调用，直到查询序列时才进行，必须改为写 (fun () -> Cons(f(), xs))。

val init : int -> (int -> 'a) -> 'a t

init n f 是序列 f 0; f 1; ...; f (n-1)。

n 必须是非负数。

如果需要，可以将无限序列 f 0; f 1; ... 定义为 map f (ints 0)。

val unfold : ('b -> ('a * 'b) option) -> 'b -> 'a t

unfold 使用步进函数和初始状态构建序列。

如果 f u 为 None，则 unfold f u 为空序列。 如果 f u 为 Some (x, u')，则 unfold f u 为非空序列 cons x (unfold f u')。

例如，unfold (function [] -> None | h :: t -> Some (h, t)) l 等价于 List.to_seq l。

val repeat : 'a -> 'a t

repeat x 是一个无限序列，其中元素 x 被无限重复。

repeat x 等价于 cycle (return x)。

val forever : (unit -> 'a) -> 'a t

forever f 是一个无限序列，其中每个元素都是通过函数调用 f()（按需）生成的。

例如，forever Random.bool 是一个由随机位组成的无限序列。

forever f 等价于 map f (repeat ())。

val cycle : 'a t -> 'a t

cycle xs 是一个无限序列，它由无限次重复序列 xs 组成。

如果 xs 是一个空序列，则 cycle xs 也是空的。

消费（序列 cycle xs 的前缀）一次会导致序列 xs 被消费多次。 因此，xs 必须是持久性的。

val iterate : ('a -> 'a) -> 'a -> 'a t

iterate f x 是一个无限序列，其元素为 x、f x、f (f x) 等。

换句话说，它是函数 f 的轨道，从 x 开始。

转换序列

本节中的函数是惰性的：也就是说，它们返回的序列只有在需要时才会计算其元素。

val map : ('a -> 'b) -> 'a t -> 'b t

map f xs 是序列 xs 通过变换 f 的图像。

如果 xs 是序列 x0; x1; ...，则 map f xs 是序列 f x0; f x1; ...。

val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t

mapi 与 map 相似，但将函数 f 应用于索引和元素。

mapi f xs 等价于 map2 f (ints 0) xs。

val filter : ('a -> bool) -> 'a t -> 'a t

filter p xs 是满足 p x 的 xs 中元素 x 的序列。

换句话说，filter p xs 是序列 xs，剔除了所有使 p x 为假的元素 x。

val filter_map : ('a -> 'b option) -> 'a t -> 'b t

filter_map f xs 是元素 y 的序列，其中 f x = Some y，而 x 在 xs 中遍历。

filter_map f xs 等价于 map Option.get (filter Option.is_some (map f xs))。

val scan : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b t

如果 xs 是一个序列 [x0; x1; x2; ...]，则 scan f a0 xs 是一个累加器序列 [a0; a1; a2; ...]，其中 a1 为 f a0 x0，a2 为 f a1 x1，依此类推。

因此，scan f a0 xs 从概念上来说与 fold_left f a0 xs 相关。 但是，它没有执行急切迭代并立即返回最终累加器，而是返回一个累加器序列。

例如，scan (+) 0 将整数序列转换为其部分和序列。

如果 xs 的长度为 n，则 scan f a0 xs 的长度为 n+1。

val take : int -> 'a t -> 'a t

take n xs 是 xs 的前 n 个元素的序列。

如果 xs 的元素少于 n 个，则 take n xs 等价于 xs。

n 必须是非负数。

val drop : int -> 'a t -> 'a t

drop n xs 是序列 xs，剔除了其前 n 个元素。

如果 xs 的元素少于 n 个，则 drop n xs 为空。

n 必须是非负数。

drop 是惰性的：只有在需要序列 drop n xs 的第一个元素时才会请求序列 xs 的前 n+1 个元素。 因此，drop 1 xs 不 等价于 tail xs，它会立即查询 xs。

val take_while : ('a -> bool) -> 'a t -> 'a t

take_while p xs 是序列 xs 的最长前缀，其中每个元素 x 都满足 p x。

val drop_while : ('a -> bool) -> 'a t -> 'a t

drop_while p xs 是序列 xs，剔除了前缀 take_while p xs。

val group : ('a -> 'a -> bool) -> 'a t -> 'a t t

假设函数 eq 在元素上定义了一个相等性，group eq xs 是序列 xs 中相邻重复元素的最大运行序列。

group eq xs 的每个元素都是一个非空序列，其中包含相等的元素。

连接 concat (group eq xs) 等于 xs。

消费 group eq xs，以及消费它包含的序列，可能会导致 xs 被消费多次。 因此，xs 必须是持久性的。

val memoize : 'a t -> 'a t

序列 memoize xs 与序列 xs 具有相同的元素。

无论 xs 是短暂的还是持久性的，memoize xs 都是持久性的：即使它被查询多次，xs 也最多被查询一次。

序列 memoize xs 的构建在内部依赖于模块 Lazy 提供的挂起。 这些挂起不是 线程安全的。 因此，序列 memoize xs 不能 被多个线程同时查询。

exception Forced_twice

当由 Seq.once 返回的序列（或其后缀）被查询多次时，会引发此异常。

val once : 'a t -> 'a t

序列 once xs 与序列 xs 具有相同的元素。

无论 xs 是短暂的还是持久性的，once xs 都是一个短暂的序列：它最多可以被查询一次。 如果它（或其后缀）被查询多次，则会引发异常 Forced_twice。 在调试或测试时，这很有用，可以确保序列最多被消费一次。

val transpose : 'a t t -> 'a t t

如果 xss 是一个矩阵（行序列），则 transpose xss 是矩阵 xss 的列序列。

矩阵 xss 的行不需要具有相同的长度。

矩阵 xss 不需要是有限的（无论是哪个方向）。

矩阵 xss 必须是持久性的。

组合序列

val append : 'a t -> 'a t -> 'a t

append xs ys 是序列 xs 和 ys 的连接。

它的元素是 xs 的元素，接着是 ys 的元素。

val concat : 'a t t -> 'a t

如果 xss 是一个序列的序列，那么 concat xss 是它的串联。

如果 xss 是序列 xs0; xs1; ...，那么 concat xss 是序列 xs0 @ xs1 @ ...。

val flat_map : ('a -> 'b t) -> 'a t -> 'b t

flat_map f xs 等价于 concat (map f xs)。

val concat_map : ('a -> 'b t) -> 'a t -> 'b t

concat_map f xs 等价于 concat (map f xs)。

concat_map 是 flat_map 的别名。

val zip : 'a t -> 'b t -> ('a * 'b) t

zip xs ys 是从序列 xs 和 ys 同步绘制的元素对 (x, y) 的序列。

如果序列 xs 和 ys 长度不同，那么序列在其中一个序列耗尽时结束；另一个序列中的多余元素将被忽略。

zip xs ys 等价于 map2 (fun a b -> (a, b)) xs ys。

val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t

map2 f xs ys 是元素 f x y 的序列，其中元素对 (x, y) 是从序列 xs 和 ys 同步绘制的。

如果序列 xs 和 ys 长度不同，那么序列在其中一个序列耗尽时结束；另一个序列中的多余元素将被忽略。

map2 f xs ys 等价于 map (fun (x, y) -> f x y) (zip xs ys)。

val interleave : 'a t -> 'a t -> 'a t

interleave xs ys 是以 xs 的第一个元素开头，接着是 ys 的第一个元素，等等的序列。

当序列 xs 和 ys 中的一个耗尽时，interleave xs ys 将继续使用另一个序列的剩余部分。

val sorted_merge : ('a -> 'a -> int) -> 'a t -> 'a t -> 'a t

如果序列 xs 和 ys 根据总预序 cmp 进行排序，那么 sorted_merge cmp xs ys 是通过合并序列 xs 和 ys 获得的排序序列。

有关比较函数的更多详细信息，请参见 Array.sort.

val product : 'a t -> 'b t -> ('a * 'b) t

product xs ys 是序列 xs 和 ys 的笛卡尔积。

对于 xs 的每个元素 x 和 ys 的每个元素 y，元素对 (x, y) 作为 product xs ys 的元素出现一次。

元素对出现的顺序未指定。

序列 xs 和 ys 不需要是有限的。

序列 xs 和 ys 必须是持久性的。

val map_product : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t

序列 map_product f xs ys 是序列 xs 和 ys 的笛卡尔积通过 f 的映射。

对于 xs 的每个元素 x 和 ys 的每个元素 y，元素 f x y 作为 map_product f xs ys 的元素出现一次。

这些元素出现的顺序未指定。

序列 xs 和 ys 不需要是有限的。

序列 xs 和 ys 必须是持久性的。

map_product f xs ys 等价于 map (fun (x, y) -> f x y) (product xs ys)。

将序列拆分为两个序列

val unzip : ('a * 'b) t -> 'a t * 'b t

unzip 将元素对的序列转换为一对序列。

unzip xs 等价于 (map fst xs, map snd xs)。

查询 unzip xs 返回的任何一个序列都会导致查询 xs。因此，查询它们都会导致查询 xs 两次。所以，xs 必须是持久且廉价的。如果不是这样，请使用 unzip (memoize xs)。

val split : ('a * 'b) t -> 'a t * 'b t

split 是 unzip 的别名。

val partition_map : ('a -> ('b, 'c) Either.t) -> 'a t -> 'b t * 'c t

partition_map f xs 返回一对序列 (ys, zs)，其中

  • ys 是元素 y 的序列，其中 f x = Left y，其中 x 遍历 xs；
  • zs 是元素 z 的序列，其中 f x = Right z，其中 x 遍历 xs。

partition_map f xs 等价于一对 filter_map Either.find_left (map f xs) 和 filter_map Either.find_right (map f xs)。

查询 partition_map f xs 返回的任何一个序列都会导致查询 xs。因此，查询它们都会导致查询 xs 两次。所以，xs 必须是持久且廉价的。如果不是这样，请使用 partition_map f (memoize xs)。

val partition : ('a -> bool) -> 'a t -> 'a t * 'a t

partition p xs 返回一对序列，分别是满足 p 的 xs 元素的子序列和不满足 p 的 xs 元素的子序列。

partition p xs 等价于 filter p xs, filter (fun x -> not (p x)) xs。

使用 partition p xs 返回的两个序列都会导致 xs 被使用两次，也会导致函数 f 对列表的每个元素应用两次。因此，f 应该是纯的且廉价的。此外，xs 应该是持久且廉价的。如果不是这样，请使用 partition p (memoize xs)。

在序列和分配器之间转换

分配器是用类型为 unit -> 'a option 的函数表示序列。每次调用此函数时，它都会返回序列的下一个元素。当没有更多元素时，它会返回 None。分配器具有可变的内部状态，因此是短暂的：它所表示的序列最多只能使用一次。

val of_dispenser : (unit -> 'a option) -> 'a t

of_dispenser it 是分配器 it 生成的元素的序列。它是一个短暂的序列：它最多只能使用一次。如果需要一个持久序列，请使用 memoize (of_dispenser it)。

val to_dispenser : 'a t -> unit -> 'a option

to_dispenser xs 是序列 xs 上的一个全新分配器。

此分配器具有可变的内部状态，该状态不受锁的保护；因此，它不能由多个线程同时使用。

整数序列

val ints : int -> int t

ints i 是从 i 开始并向上计数的整数的无限序列。