ngữ nghĩa OCaml của hợp nhất trong functor Map.make?

Question

Tôi đang viết một hàm OCaml, nơi tôi cần hợp nhất hai bản đồ. Tôi đã không thể tìm ra ngữ nghĩa của hàm merge do functor Map.Make cung cấp (được tìm thấy trong phiên bản 3.12.0 của OCaml). Ai đó có thể cung cấp cho tôi một lời giải thích chi tiết hơn so với hướng dẫn OCaml? Một ví dụ có thể đủ cho tôi để tìm ra.

Ngoài ra, hai bản đồ mà tôi cần hợp nhất có một số thuộc tính thú vị: các khóa có cùng loại (int, trên thực tế) và miền của chúng bị tách rời. Sẽ có một cách tiếp cận hiệu quả hơn so với thói quen hợp nhất?

Answer 1

merge có chức năng và hai bản đồ. Đối với mỗi chìa khóa hiện diện trong một trong hai bản đồ, chức năng sẽ được gọi. Nếu khóa chỉ xuất hiện ở một trong các bản đồ, giá trị cho khóa còn lại sẽ được chuyển thành None (đó là lý do tại sao các đối số là các tùy chọn). Nếu các hàm trả về Some x, bản đồ mới sẽ có giá trị x cho khóa được đề cập. Nếu không, chìa khóa sẽ không có mặt.

Ví dụ:

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;; 

tại map3 chứa ánh xạ 2 -> 8.

Nếu bạn thay đổi nó để:

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;; 

Nó sẽ chứa các ánh xạ 1 -> 2, 2 -> 8 và 3 -> 4.

Answer 2

Dựa trên câu trả lời đầu tiên, và xem xét các câu hỏi bổ sung (merge bản đồ trong trường hợp tên miền rời nhau), Sau đó tôi sẽ đề nghị thói quen merge chung sau đây:

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 

Nên có một số cách hiệu quả hơn để làm điều này?

- David.

Answer 3

Kể từ khi bản đồ của bạn là rời nhau thì bạn có thể chỉ lặp qua các bản đồ nhỏ hơn và chèn vào lớn hơn:

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 

Trong trường hợp bạn đang sử dụng một phiên bản cũ của OCaml mà không bao gồm các cardinal chức năng bạn chỉ có thể chọn một bản đồ để luôn luôn lặp qua. Đối với những gì đoạn mã trên không, là nó sử dụng:

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

Mà về cơ bản lặp qua tất cả các yếu tố bản đồ, và kêu gọi một chức năng mà phải mất một chìa khóa, giá trị và một số biến khác của loại 'b và trả về một cái gì đó loại đó ('b). Trong trường hợp của chúng ta, chúng ta chuyển hàm IntMap.add và biến kia là bản đồ thứ hai của chúng ta. Vì vậy, nó lặp qua tất cả các phần tử và thêm chúng vào bản đồ khác.

EDIT: Bạn đang tốt hơn hết chỉ cần thực hiện:

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

EDIT2: thậm chí tốt hơn:

let disjoint_merge = IntMap.fold IntMap.add;; 

Tôi chỉ nhìn vào thực hiện cardinal và nó đi cây và trả về số lượng. Vì vậy, bằng cách kiểm tra kích cỡ bạn đang làm O (n + m + min (n, m) log (tối đa (n, m))) thay vì chỉ O (n log (m)).