映射

簡介

Map 模組讓您可以為您的類型建立不可變的鍵值關聯表。這樣的映射永遠不會被修改，而且每個操作都會返回一個新的映射。

注意：本教學中描述的映射不應與 List.map、Array.map、Option.map 等映射函數混淆。本教學中描述的映射也稱為字典或關聯表。

要使用 Map，我們首先必須使用 Map.Make 函子來建立我們自訂的映射模組。請參閱 函子以取得關於函子的更多資訊。此函子有一個模組參數，定義要用於映射的鍵的類型，以及一個用於比較它們的函數。

# module StringMap = Map.Make(String);;

module StringMap :
  sig
    type key = string
    type 'a t = 'a Map.Make(String).t
    val empty : 'a t
    val add : key -> 'a -> 'a t -> 'a t
    val add_to_list : key -> 'a -> 'a list t -> 'a list t
    val update : key -> ('a option -> 'a option) -> 'a t -> 'a t
    val singleton : key -> 'a -> 'a t
    val remove : key -> 'a t -> 'a t
    (* ... *)
  end

在將新建立的模組命名為 StringMap 後，OCaml 的頂層會顯示該模組的簽名。由於它包含大量的函數，此處複製的輸出為了簡潔起見而縮短了 (...)。

此模組未定義值的類型。它將在我們建立第一個映射時定義。

建立映射

StringMap 模組有一個 empty 值，其類型有一個類型參數 'a：empty : 'a t。

這表示我們可以使用 empty 來建立新的空映射，其中值可以是任何類型。

# let int_map : int StringMap.t = StringMap.empty;;
val int_map : int StringMap.t = <abstr>

# let float_map : float StringMap.t = StringMap.empty;;
val float_map : float StringMap.t = <abstr>

可以透過兩種方式指定值的類型

• 當您使用註解建立新的映射時
• 透過將元素新增至映射

# let int_map = StringMap.(empty |> add "one" 1);;
val int_map : int StringMap.t = <abstr>

使用映射

在本教學的其餘部分，我們使用以下映射

# let lucky_numbers = StringMap.of_seq @@ List.to_seq [
    ("leostera", 2112);
    ("charstring88", 88);
    ("divagnz", 13);
  ];;
val lucky_numbers : int StringMap.t = <abstr>

尋找映射中的條目

要在映射中尋找條目，請使用 find_opt 或 find 函數

# StringMap.find_opt "leostera" lucky_numbers;;
- : int option = Some 2112

# StringMap.find "leostera" lucky_numbers;;
- : int = 2112

當搜尋的鍵存在於映射中時

• find_opt 返回關聯的值，並以選項包裝
• find 返回關聯的

當搜尋的鍵不在映射中時

• find_opt 返回 None
• find 會拋出 Not_found 例外

如果我們想要使用謂詞函數，我們也可以使用 find_first_opt 和 find_last_opt

# let first_under_10_chars : (string * int) option =
  StringMap.find_first_opt
    (fun key -> String.length key < 10)
    lucky_numbers;;
val first_under_10_chars : (string * int) option = Some ("divagnz", 13)

find_first 和 find_last 函數的行為類似，只是它們會拋出例外而不是返回選項。

請注意，find_first_opt 和 find_last_opt 返回的是鍵值對，而不僅僅是值。

將條目新增至映射

要將條目新增至映射，請使用 add 函數，該函數接受鍵、值和映射。它會返回一個新增了該鍵值對的新映射

# let more_lucky_numbers = lucky_numbers |> StringMap.add "paguzar" 108;;
val more_lucky_numbers : int StringMap.t = <abstr>

# StringMap.find_opt "paguzar" lucky_numbers;;
- : int option = None

# StringMap.find_opt "paguzar" more_lucky_numbers;;
- : int option = Some 108

如果傳遞的鍵已經與一個值關聯，則傳遞的值會取代它。

請注意，初始映射 lucky_numbers 保持不變。

從映射中移除條目

要從映射中移除條目，請使用 remove 函數，該函數接受鍵和映射。它會返回一個移除了該鍵的條目的新映射。

# let less_lucky_numbers = lucky_numbers |> StringMap.remove "divagnz";;
val less_lucky_numbers : int StringMap.t = <abstr>

# StringMap.find_opt "divagnz" lucky_numbers;;
- : int option = Some 13

# StringMap.find_opt "divagnz" less_lucky_numbers;;
- : int option = None

移除映射中不存在的鍵沒有任何影響。

請注意，初始映射 lucky_numbers 保持不變。

變更與鍵關聯的值

要變更鍵的關聯值，請使用 update 函數。它接受鍵、映射和更新函數。它會返回一個鍵的關聯值被新值取代的新映射。

# let updated_lucky_numbers =
    lucky_numbers
    |> StringMap.update "charstring88" (Option.map (fun _ -> 99));;
val updated_lucky_numbers : int StringMap.t = <abstr>

# StringMap.find_opt "charstring88" lucky_numbers;;
- : int option = Some 88

# StringMap.find_opt "charstring88" updated_lucky_numbers;;
- : int option = Some 99

您應該嘗試使用不同的更新函數；有多種可能的行為。

檢查映射中是否包含鍵

要檢查映射是否包含鍵，請使用 mem 函數

# StringMap.mem "paguzar" less_lucky_numbers;;
- : bool = false

合併映射 (Merging Maps)

要合併兩個映射，請使用 union 函式，該函式接受兩個映射，以及一個決定如何處理具有相同鍵的條目的函式。它會傳回一個新的映射。請注意，輸入的映射不會被修改。

# StringMap.union;;
- : (string -> 'a -> 'a -> 'a option) ->
    'a StringMap.t -> 'a StringMap.t -> 'a StringMap.t
= <fun>

以下是一些重複鍵解析函式的範例

# let pick_fst key v1 _ = Some v1;;
val pick_fst : 'a -> 'b -> 'c -> 'b option = <fun>

# let pick_snd key _ v2 = Some v2;;
val pick_snd : 'a -> 'b -> 'c -> 'c option = <fun>

# let drop _ _ _ = None;;
val drop : 'a -> 'b -> 'c -> 'd option = <fun>

• pick_fst 從第一個映射中選擇結果的值
• pick_snd 從第二個映射中選擇結果的值
• drop 在結果映射中捨棄兩個條目

# StringMap.(
    union pick_fst lucky_numbers updated_lucky_numbers
    |> find_opt "charstring88"
  );;
- : int option = Some 88

# StringMap.(
    union pick_snd lucky_numbers updated_lucky_numbers
    |> find_opt "charstring88"
  );;
- : int option = Some 99

# StringMap.(
    union drop lucky_numbers updated_lucky_numbers
    |> find_opt "charstring88"
  );;
- : int option = None

篩選映射 (Filtering a Map)

要篩選映射，請使用 filter 函式。它接受一個用來篩選條目的謂詞和一個映射。它會傳回一個新的映射，其中包含滿足謂詞的條目。

# let even_numbers =
  StringMap.filter
    (fun _ number -> number mod 2 = 0)
    lucky_numbers;;
val even_numbers : int StringMap.t = <abstr>

映射映射 (Map a Map)

映射模組有一個 map 函式

StringMap.map;;
- : ('a -> 'b) -> 'a StringMap.t -> 'b StringMap.t = <fun>

lucky_numbers 映射將字串鍵與整數值關聯起來。

# lucky_numbers;;
- : int StringMap.t = <abstr>

使用 StringMap.map，我們建立一個將鍵與字串值關聯的映射

# let lucky_strings = StringMap.map string_of_int lucky_numbers;;
val lucky_strings : string StringMap.t = <abstr>

兩個映射中的鍵是相同的。對於每個鍵，lucky_numbers 中的值會使用 string_of_int 轉換為 lucky_strings 中的值。

# lucky_numbers |> StringMap.find "leostera" |> string_of_int;;
- : string = "2112"

# lucky_strings |> StringMap.find "leostera";;
- : string = "2112"

具有自訂鍵類型的映射 (Maps With Custom Key Types)

如果您需要建立具有自訂鍵類型的映射，可以使用您自己的模組呼叫 Map.Make 函式，前提是您的模組實作了兩件事

1. 一個沒有類型參數的 t 類型
2. 一個 compare : t -> t -> int 函式，用於比較 t 值

讓我們在下面定義我們的自訂映射，用於非負數。

我們將首先定義一個模組，用於以不區分大小寫的方式比較字串。

# module Istring : sig
    type t
    val compare : t -> t -> int
  end = struct
    type t = string
    let compare a b = String.(compare (lowercase_ascii a) (lowercase_ascii b))
  end;;
module Istring : sig type t val compare : t -> t -> int end

請注意，我們的模組有一個 type t 以及一個 compare 函式。現在我們可以呼叫 Map.Make 函式來取得非負數的映射

# module IstringMap = Map.Make(Istring);;
module IstringMap :
  sig
    type key = Istring.t
    type 'a t = 'a Map.Make(Istring).t
    val empty : 'a t
    val is_empty : 'a t -> bool
    val mem : key -> 'a t -> bool
    val add : key -> 'a -> 'a t -> 'a t
    val update : key -> ('a option -> 'a option) -> 'a t -> 'a t
    val singleton : key -> 'a -> 'a t
    val remove : key -> 'a t -> 'a t
    (* ... *)
end

結論 (Conclusion)

這是 OCaml 的 Map 模組的概述。映射相當有效率，可以作為命令式 Hashtbl 模組的替代方案。

如需更多資訊，請參閱標準函式庫文件中的 Map。