模組類型 Map.S

module type S = sig .. end

函子 Map.Make 的輸出簽名。

映射

type key

映射鍵的類型。

type !+'a t

從類型 key 到類型 'a 的映射類型。

val empty : 'a t

空的映射。

val add : key -> 'a -> 'a t -> 'a t

add key data m 返回一個包含與 m 相同綁定的映射，再加上一個 key 到 data 的綁定。 如果 key 已經在 m 中綁定到一個與 data 物理上相等的值，則 m 會被原封不動地返回（函數的結果與 m 在物理上相等）。 否則，key 在 m 中的先前綁定將會消失。

val add_to_list : key -> 'a -> 'a list t -> 'a list t

add_to_list key data m 是 m，其中 key 映射到 l，使得 l 為 data :: Map.find key m（如果 key 在 m 中有綁定），否則為 [v]。

val update : key -> ('a option -> 'a option) -> 'a t -> 'a t

update key f m 返回一個包含與 m 相同綁定的映射，但 key 的綁定除外。根據 y 的值（其中 y 是 f (find_opt key m)），key 的綁定將會被新增、移除或更新。如果 y 是 None，則綁定會被移除（如果存在）；否則，如果 y 是 Some z，則 key 會在結果映射中與 z 關聯。如果 key 已經在 m 中綁定到一個與 z 物理上相等的值，則 m 會被原封不動地返回（函數的結果與 m 在物理上相等）。

val singleton : key -> 'a -> 'a t

singleton x y 返回一個單元素的映射，其中包含 x 的 y 綁定。

val remove : key -> 'a t -> 'a t

remove x m 返回一個包含與 m 相同綁定的映射，但 x 在返回的映射中沒有綁定。如果 x 不在 m 中，則 m 會被原封不動地返回（函數的結果與 m 在物理上相等）。

val merge : (key -> 'a option -> 'b option -> 'c option) ->
       'a t -> 'b t -> 'c t

merge f m1 m2 計算一個映射，其鍵是 m1 和 m2 的鍵的子集。每個此類綁定的存在以及相應的值由函數 f 決定。就 find_opt 操作而言，我們有 find_opt x (merge f m1 m2) = f x (find_opt x m1) (find_opt x m2)，適用於任何鍵 x，前提是 f x None None = None。

val union : (key -> 'a -> 'a -> 'a option) ->
       'a t -> 'a t -> 'a t

union f m1 m2 計算一個映射，其鍵是 m1 和 m2 的鍵的子集。當相同的綁定在兩個引數中都有定義時，會使用函數 f 來合併它們。這是 merge 的一個特殊情況：union f m1 m2 等同於 merge f' m1 m2，其中

  • f' _key None None = None
  • f' _key (Some v) None = Some v
  • f' _key None (Some v) = Some v
  • f' key (Some v1) (Some v2) = f key v1 v2
val cardinal : 'a t -> int

返回映射的綁定數。

綁定

val bindings : 'a t -> (key * 'a) list

返回給定映射的所有綁定清單。返回的清單根據鍵的順序遞增排序，參照 Ord.compare 的排序，其中 Ord 是給定給 Map.Make 的引數。

val min_binding : 'a t -> key * 'a

返回給定映射中最小鍵的綁定（關於 Ord.compare 排序），如果映射為空，則引發 Not_found。

val min_binding_opt : 'a t -> (key * 'a) option

返回給定映射中最小鍵的綁定（關於 Ord.compare 排序），如果映射為空，則返回 None。

val max_binding : 'a t -> key * 'a

與 Map.S.min_binding 相同，但返回給定映射中最大鍵的綁定。

val max_binding_opt : 'a t -> (key * 'a) option

與 Map.S.min_binding_opt 相同，但返回給定映射中最大鍵的綁定。

val choose : 'a t -> key * 'a

返回給定映射的一個綁定，如果映射為空，則引發 Not_found。選擇哪個綁定是未指定的，但對於相等的映射會選擇相等的綁定。

val choose_opt : 'a t -> (key * 'a) option

返回給定映射的一個綁定，如果映射為空，則返回 None。選擇哪個綁定是未指定的，但對於相等的映射會選擇相等的綁定。

搜尋

val find : key -> 'a t -> 'a

find x m 返回 x 在 m 中的目前值，如果不存在 x 的綁定，則引發 Not_found。

val find_opt : key -> 'a t -> 'a option

find_opt x m 如果 x 在 m 中的目前值為 v，則返回 Some v，如果不存在 x 的綁定，則返回 None。

val find_first : (key -> bool) -> 'a t -> key * 'a

find_first f m，其中 f 是單調遞增函數，返回 m 中鍵最小的 k 的綁定，使得 f k，如果不存在此類鍵，則引發 Not_found。

例如，find_first (fun k -> Ord.compare k x >= 0) m 會返回 m 的第一個綁定 k, v，其中 Ord.compare k x >= 0 (直觀上：k >= x），如果 x 大於 m 的任何元素，則引發 Not_found。

val find_first_opt : (key -> bool) -> 'a t -> (key * 'a) option

find_first_opt f m，其中 f 是單調遞增函數，返回一個選項，其中包含 m 中鍵最小的 k 的綁定，使得 f k，如果不存在此類鍵，則返回 None。

val find_last : (key -> bool) -> 'a t -> key * 'a

find_last f m，其中 f 是單調遞減函數，返回 m 中鍵最大的 k 的綁定，使得 f k，如果不存在此類鍵，則引發 Not_found。

val find_last_opt : (key -> bool) -> 'a t -> (key * 'a) option

find_last_opt f m，其中 f 是單調遞減函數，返回一個選項，其中包含 m 中鍵最大的 k 的綁定，使得 f k，如果不存在此類鍵，則返回 None。

遍歷

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

iter f m 將 f 應用於映射 m 中的所有綁定。f 接收鍵作為第一個引數，相關值作為第二個引數。綁定會按照鍵類型的排序順序遞增地傳遞給 f。

val fold : (key -> 'a -> 'acc -> 'acc) -> 'a t -> 'acc -> 'acc

fold f m init 計算 (f kN dN ... (f k1 d1 init)...)，其中 k1 ... kN 是 m 中所有綁定的鍵（依遞增順序），而 d1 ... dN 是相關的資料。

轉換

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

map f m 返回一個與 m 具有相同域的映射，其中 m 的所有綁定的相關值 a 已被應用 f 到 a 的結果取代。綁定會按照鍵類型的排序順序遞增地傳遞給 f。

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

與 Map.S.map 相同，但是該函數會接收映射中每個綁定的鍵和相關值作為引數。

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

filter f m 返回 m 中滿足斷言 p 的所有綁定的映射。如果 m 中的每個綁定都滿足 f，則 m 會被原封不動地返回（函數的結果與 m 在物理上相等）。

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

filter_map f m 將函數 f 應用於 m 的每個綁定，並從結果建構映射。對於輸入映射中的每個綁定 (k, v)

  • 如果 f k v 是 None，則 k 不在結果中，
  • 如果 f k v 是 Some v'，則綁定 (k, v') 在輸出映射中。

例如，以下關於其值為清單的映射的函數

        filter_map
          (fun _k li -> match li with [] -> None | _::tl -> Some tl)
          m

會捨棄 m 中所有其值為空清單的綁定，並彈出每個非空值的首個元素。

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

partition f m 函式會回傳一對映射 (map) (m1, m2)，其中 m1 包含 m 中所有滿足謂詞 (predicate) f 的綁定 (binding)，而 m2 則包含 m 中所有不滿足 f 的綁定。

val split : key -> 'a t -> 'a t * 'a option * 'a t

split x m 函式會回傳一個三元組 (triple) (l, data, r)，其中 l 是包含 m 中所有鍵 (key) 嚴格小於 x 的綁定的映射；r 是包含 m 中所有鍵嚴格大於 x 的綁定的映射；如果 m 沒有 x 的綁定，則 data 為 None，如果 m 將 v 綁定到 x，則 data 為 Some v。

斷言與比較

val is_empty : 'a t -> bool

測試一個映射是否為空。

val mem : key -> 'a t -> bool

mem x m 函式在 m 包含 x 的綁定時回傳 true，否則回傳 false。

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

equal cmp m1 m2 函式測試映射 m1 和 m2 是否相等，亦即它們是否包含相同的鍵並且將其與相同的資料關聯。cmp 是用於比較與鍵相關聯的資料的相等謂詞。

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

映射之間的總排序 (Total ordering)。第一個參數是用於比較兩個映射中具有相同鍵的相關資料的總排序。

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

for_all f m 函式檢查映射的所有綁定是否滿足謂詞 f。

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

exists f m 函式檢查映射中是否至少有一個綁定滿足謂詞 f。

轉換

val to_list : 'a t -> (key * 'a) list

to_list m 等同於 Map.S.bindings m。

val of_list : (key * 'a) list -> 'a t

of_list bs 函式按照列表順序將 bs 的綁定加入到空映射 (empty map) 中（如果一個鍵在 bs 中被綁定兩次，則最後一次的綁定會覆蓋先前的綁定）。

val to_seq : 'a t -> (key * 'a) Seq.t

依鍵的遞增順序對整個映射進行迭代。

val to_rev_seq : 'a t -> (key * 'a) Seq.t

依鍵的遞減順序對整個映射進行迭代。

val to_seq_from : key -> 'a t -> (key * 'a) Seq.t

to_seq_from k m 函式從鍵 k 或更高的鍵開始，依鍵的遞增順序對 m 的綁定的子集進行迭代。

val add_seq : (key * 'a) Seq.t -> 'a t -> 'a t

依序將給定的綁定加入到映射中。

val of_seq : (key * 'a) Seq.t -> 'a t

從給定的綁定建立一個映射。