Semantics of OCaml merge in Map.make functor?

Question

I am writing an OCaml function where I need to combine two cards. I was unable to determine the semantics of the merge function provided by the Map.Make functor (found in version 3.12.0 of OCaml). Can someone provide me a more detailed explanation than the OCaml manual? For me, probably an example is enough to understand this.

In addition, the two cards that I need to combine have some interesting properties: the keys are of the same type ( int , in fact), and their domain does not intersect. Would there be a more efficient approach than a merger?

Answer 1

merge accepts a function and two cards. For each key present on any card, a function is called. If the key is present only in one of the cards, the value for the other will be passed as None (therefore, the arguments are parameters). If functions return Some x , the new map will have the value x for the key in question. Otherwise, the key will not be present.

Example:

 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 now contains a map 2 -> 8 .

If you change it to:

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

It will contain the mappings 1 -> 2 , 2 -> 8 and 3 -> 4 .

Answer 2

Since your cards do not intersect, you can simply scroll through the smaller card and insert more into it:

 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 

If you are using an old version of OCaml that does not include the cardinal feature, you can simply select one card to always iterate over it. As for the code above, is it used:

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

which basically iterates over all the elements of the map and calls a function that takes a key, value, and some other variable of type 'b and returns something from that type ( 'b ). In our case, we pass the IntMap.add function and that the other variable is our second map. Thus, it iterates over all elements and adds them to another map.

EDIT: you better do:

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

EDIT2: even better:

 let disjoint_merge = IntMap.fold IntMap.add;; 

I just looked at the implementation of cardinal , and it scans the tree and returns a counter. Thus, checking the sizes, you do O (n + m + min (n, m) log (max (n, m))) instead of just O (nlog (m)).

Answer 3

Based on the first answer and given the additional question (merge cards in case of disjoint domains), I would suggest the following general merge procedure:

 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 

Would there be a more efficient way to do this?

- David.