模組 Seq

module Seq: sig .. end

序列。

類型為 'a Seq.t 的序列可以被視為一個延遲列表，也就是說，只有當消費者需要時才會計算列表中的元素。這使得序列能夠以惰性方式（一次一個元素）而非急切方式（一次所有元素）產生和轉換。這也允許建構概念上無限的序列。

類型 'a Seq.t 被定義為 unit -> 'a Seq.node 的同義詞。這是一個函式類型：因此，它是隱藏的。消費者可以查詢序列以請求下一個元素（如果有的話），但不能以其他方式檢查序列。

因為它是隱藏的，類型 '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。

由於 4.07

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 是序列的其餘部分。

取用序列

本節中的函數會部分或完全地消耗其參數，也就是一個序列

is_empty 和 uncons 會消耗序列到深度 1。也就是說，它們會要求序列的第一個參數（如果有的話）。
iter、fold_left、length 等會將序列一直消耗到其結尾。它們只有在序列為有限時才會終止。
for_all、exists、find 等會將序列消耗到某個深度，這個深度是先驗無法預測的。

同樣地，在消耗兩個序列的函數中，可以區分兩組

iter2 和 fold_left2 會將兩個序列一直消耗到結尾，前提是序列的長度相同。
for_all2、exists2、equal、compare 會將序列消耗到某個深度，這個深度是先驗無法預測的。

消耗兩個序列的函數可以應用於長度不同的兩個序列：在這種情況下，會忽略較長序列中多餘的元素。（可能會需要一個多餘的元素，即使這個元素沒有被使用。）

本節中的函數都不是惰性的。這些函數是消費者：它們會強制進行一些計算。

val is_empty : 'a t -> bool

is_empty xs 判斷序列 xs 是否為空。

建議序列 xs 為持久的。實際上，is_empty xs 會要求序列 xs 的頭部，因此，如果 xs 是短暫的，則可能會在執行此呼叫後無法再使用 xs。

由於 4.14

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

如果 xs 為空，則 uncons xs 為 None。

如果 xs 為非空，則 uncons xs 為 Some (x, ys)，其中 x 是序列的頭部，而 ys 是序列的尾部。

由於 4.14

val length : 'a t -> int

length xs 是序列 xs 的長度。

序列 xs 必須是有限的。

由於 4.14

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

iter f xs 會從左到右，針對序列 xs 的每個元素 x 依次呼叫 f x。

它只有在序列 xs 為有限時才會終止。

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

fold_left f _ xs 會從左到右，針對序列 xs 的每個元素 x 依次呼叫 f _ x。

類型為 'a 的累加器會透過對 f 的呼叫傳遞。

它只有在序列 xs 為有限時才會終止。

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

iteri f xs 會針對序列 xs 中位於索引 i 的每個元素 x 依次呼叫 f i x。

它只有在序列 xs 為有限時才會終止。

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

由於 4.14

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

fold_lefti f _ xs 會針對序列 xs 中位於索引 i 的每個元素 x 依次呼叫 f _ 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)。

由於 4.14

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

for_all p xs 判斷序列 xs 的所有元素 x 是否滿足 p x。

序列 xs 必須是有限的。

由於 4.14

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

exists xs p 判斷序列 xs 中是否至少有一個元素 x 滿足 p x。

序列 xs 必須是有限的。

由於 4.14

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

find p xs 傳回 Some x，其中 x 是序列 xs 中滿足 p x 的第一個元素（如果存在）。

如果不存在這樣的元素，則傳回 None。

序列 xs 必須是有限的。

由於 4.14

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

find_index p xs 返回 Some i，其中 i 是序列 xs 中第一個滿足 p x 條件的元素的索引，如果存在這樣的元素。

如果不存在這樣的元素，則傳回 None。

序列 xs 必須是有限的。

由於 5.1

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 必須是有限的。

由於 4.14

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

與 find_map 相同，但謂詞會將元素的索引（從 0 開始計數）作為第一個參數，元素本身作為第二個參數。

序列 xs 必須是有限的。

由於 5.1

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)。

由於 4.14

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)。

由於 4.14

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 的差異所在：只有當 xs 和 ys 具有相同的長度時，equal eq xs ys 才可能為真。

序列 xs 和 ys 中至少有一個必須是有限的。

for_all2 p xs ys 等同於 for_all (fun b -> b) (map2 p xs ys)。

由於 4.14

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)。

由於 4.14

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

如果函數 eq 定義了元素上的相等性，則 equal eq xs ys 判斷序列 xs 和 ys 是否逐點相等。

序列 xs 和 ys 中至少有一個必須是有限的。

由於 4.14

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

如果函數 cmp 定義了元素上的預序關係，則 compare cmp xs ys 根據字典序預序比較序列 xs 和 ys。

有關比較函數的更多詳細信息，請參閱 Array.sort。

序列 xs 和 ys 中至少有一個必須是有限的。

由於 4.14

建構序列

本節中的函數是惰性的：也就是說，它們返回的序列中的元素僅在需要時才計算。

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))。

由於 4.11

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)。

由於 4.14
如果 n 為負數，則引發 Invalid_argument 異常。

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。

由於 4.11

val repeat : 'a -> 'a t

repeat x 是無限序列，其中元素 x 會無限重複。

repeat x 等同於 cycle (return x)。

由於 4.14

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

forever f 是一個無限序列，其中每個元素都是由函數調用 f()（根據需要）產生。

例如，forever Random.bool 是一個無限隨機位元序列。

forever f 等同於 map f (repeat ())。

由於 4.14

val cycle : 'a t -> 'a t

cycle xs 是一個無限序列，由序列 xs 的無限次重複組成。

如果 xs 是空序列，則 cycle xs 也為空。

消耗（cycle xs 序列的前綴）一次可能會導致序列 xs 被消耗多次。因此，xs 必須是持久的。

由於 4.14

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

iterate f x 是一個無限序列，其元素為 x、f x、f (f x) 等等。

換句話說，它是從 x 開始的函數 f 的軌跡。

由於 4.14

轉換序列

本節中的函數是惰性的：也就是說，它們返回的序列中的元素僅在需要時才計算。

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。

由於 4.14

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

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

換句話說，filter p xs 是序列 xs，去除了 p x 為假的元素 x。

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

filter_map f xs 是滿足 f x = Some y 的元素 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。

由於 4.14

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

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

如果 xs 的元素少於 n 個，則 take n xs 等同於 xs。

n 必須是非負數。

由於 4.14
如果 n 為負數，則引發 Invalid_argument 異常。

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。

由於 4.14
如果 n 為負數，則引發 Invalid_argument 異常。

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

take_while p xs 是序列 xs 的最長前綴，其中每個元素 x 都滿足 p x。

由於 4.14

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

drop_while p xs 是序列 xs，去除了前綴 take_while p xs。

由於 4.14

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 必須是持久的。

由於 4.14

val memoize : 'a t -> 'a t

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

無論 xs 是暫時的還是持久的，memoize xs 都是持久的：即使它被查詢多次，xs 最多只會被查詢一次。

序列 memoize xs 的建構在內部依賴於模組 Lazy 提供的暫停。這些暫停不是執行緒安全的。因此，序列 memoize xs 絕對不能被多個執行緒同時查詢。

由於 4.14

exception Forced_twice

當由 Seq.once 返回的序列（或其後綴）被查詢多次時，會引發此例外。

由於 4.14

val once : 'a t -> 'a t

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

無論 xs 是暫時的還是持久的，once xs 都是一個暫時的序列：它最多只能被查詢一次。如果它（或其後綴）被查詢多次，則會引發例外 Forced_twice。這在除錯或測試時很有用，可以確保序列最多只會被取用一次。

由於 4.14
如果 once xs 或其後綴被查詢多次，則引發 Forced_twice 例外。

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

如果 xss 是一個矩陣（一個行序列），則 transpose xss 是矩陣 xss 的列序列。

矩陣 xss 的行不需要具有相同的長度。

矩陣 xss 不需要是有限的（在任何方向上）。

矩陣 xss 必須是持久的。

由於 4.14

合併序列

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

append xs ys 是序列 xs 和 ys 的串聯。

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

由於 4.11

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

如果 xss 是一個序列的序列，則 concat xss 是它的串聯。

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

由於 4.13

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 的別名。

由於 4.13

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。

由於 4.14

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)。

由於 4.14

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

interleave xs ys 是以 xs 的第一個元素開始，接著是 ys 的第一個元素，依此類推的序列。

當序列 xs 和 ys 其中一個耗盡時，interleave xs ys 會繼續使用另一個序列的剩餘部分。

由於 4.14

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

如果序列 xs 和 ys 根據總預序 cmp 排序，則 sorted_merge cmp xs ys 是合併序列 xs 和 ys 後得到的排序序列。

有關比較函數的更多詳細信息，請參閱 Array.sort。

由於 4.14

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 必須是持久的。

由於 4.14

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)。

由於 4.14

將一個序列分割成兩個序列

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)。

由於 4.14

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

split 是 unzip 的別名。

由於 4.14

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

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

ys 是滿足 f x = Left y 的元素 y 的序列，其中 x 遍歷 xs；

zs 是滿足 f x = Right z 的元素 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)。

由於 4.14

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)。

由於 4.14

在序列和分配器之間轉換

分配器是將序列表示為類型為 unit -> 'a option 的函式。每次呼叫此函式時，它都會返回序列的下一個元素。當沒有更多元素時，它會返回 None。分配器具有可變的內部狀態，因此是暫時的：它所代表的序列最多只能被取用一次。

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

of_dispenser it 是由分配器 it 產生的元素的序列。它是一個暫時的序列：它最多只能被取用一次。如果需要持久序列，請使用 memoize (of_dispenser it)。

由於 4.14

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

to_dispenser xs 是序列 xs 的一個新的分配器。

此分配器具有可變的內部狀態，該狀態不受鎖定保護；因此，它絕對不能被多個執行緒同時使用。

由於 4.14

整數序列

val ints : int -> int t

ints i 是從 i 開始並向上計數的無限整數序列。

由於 4.14