函子Map.make中的合併OCaml語義？

Question

我正在寫一個OCaml函數，我需要合併兩個地圖。我一直無法弄清函數Map.Make（在OCaml的3.12.0版本中找到）提供的merge函數的語義。有人能給我提供比OCaml手冊更詳細的解釋嗎？一個例子可能足以讓我弄清楚。

此外，我需要合併的兩個地圖有一些有趣的屬性：鍵具有相同類型（實際上爲int），並且它們的域是不相交的。會有比合並例程更有效的方法嗎？

Answer 1

merge需要一個函數和兩個映射。對於每個地圖中的每個鍵，都會調用該函數。如果鍵只出現在其中一個映射中，另一個鍵的值將以None傳遞（這就是參數爲選項的原因）。如果函數返回Some x，則新映射的值將爲x。否則，密鑰將不存在。

實施例：

let map1 = add 1 2 (add 2 3 empty);; 
let map2 = add 2 5 (add 3 4 empty);; 
let map3 = merge (fun k xo yo -> match xo,yo with 
    | Some x, Some y -> Some (x+y) 
    | _ -> None 
) map1 map2;; 

現在MAP3包含映射2 -> 8。

如果將其更改爲：

let map3 = merge (fun k xo yo -> match xo,yo with 
    | Some x, Some y -> Some (x+y) 
    | None, yo -> yo 
    | xo, None -> xo 
) map1 map2;; 

它將包含映射1 -> 2，2 -> 8和3 -> 4。

Answer 2

基於第一個答案，並考慮額外的問題（合併不相交的域的情況下圖），然後，我會提出下面的一般合併程序：

let merge_disjoint m1 m2 = 
    IntMap.merge 
    (fun k x0 y0 -> 
     match x0, y0 with 
     None, None -> None 
     | None, Some v | Some v, None -> Some v 
     | _, _ -> invalid_arg "merge_disjoint: maps are not disjoint") 
    m1 m2 

會不會有一些更有效的方法去做這個？

- David。

Answer 3

由於您的地圖是不相交的，那麼你可以只通過小地圖環和插入更大：

let disjoint_merge m1 m2 = 
    if (IntMap.cardinal m1) < (IntMap.cardinal m2) then 
    IntMap.fold IntMap.add m1 m2 
    else 
    IntMap.fold IntMap.add m2 m1 

倘若您使用的是舊版本的OCaml的是不包括cardinal函數，您可以選擇一個地圖來始終迭代。至於上面的代碼做什麼，是它使用：

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

這基本上遍歷所有元素的地圖，並調用一個函數，它的關鍵，價值和'b類型的其他一些變量，返回的東西該類型（'b）。在我們的例子中，我們正在傳遞函數IntMap.add，而其他變量是我們的第二張地圖。因此，它遍歷所有元素並將它們添加到其他地圖。

編輯：你最好只是在做：

let disjoint_merge m1 m2 = 
    IntMap.fold IntMap.add m1 m2 

EDIT2：甚至更好：

let disjoint_merge = IntMap.fold IntMap.add;; 

我只是看着的cardinal實施，它走的樹，並返回計數。所以通過檢查大小，你正在做O（n + m + min（n，m）log（max（n，m）））而不是O（nlog（m））。