Semántica OCaml de fusión en functor Map.make?

Question

Estoy escribiendo una función OCaml donde necesito unir dos mapas. No he podido descifrar la semántica de la función merge proporcionada por el functor Map.Make (que se encuentra en la versión 3.12.0 de OCaml). ¿Podría alguien proporcionarme una explicación más detallada que el manual OCaml? Un ejemplo probablemente sería suficiente para que yo lo resolviera.

Además, los dos mapas que necesito fusionar tienen algunas propiedades interesantes: las claves tienen el mismo tipo (int, en realidad), y su dominio es disjunto. ¿Habría un enfoque más eficiente que la rutina de fusión?

Answer 1

merge toma una función y dos mapas. Para cada clave presente en cualquier mapa, se llamará a la función. Si la clave solo está presente en uno de los mapas, el valor del otro pasará como Ninguno (por lo que los argumentos son opciones). Si las funciones devuelven Some x, el nuevo mapa tendrá el valor x para la clave en cuestión. De lo contrario, la clave no estará presente.

Ejemplo:

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 ahora contiene el mapeo 2 -> 8.

Si lo cambia a:

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

Contendrá las asignaciones 1 -> 2, 2 -> 8 y 3 -> 4.

Answer 2

Sobre la base de la primera respuesta, y teniendo en cuenta la cuestión adicional (combinar mapas en el caso de los dominios disjuntos), me gustaría proponer a continuación la siguiente rutina de combinación genérica:

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 

¿Habría alguna manera más eficiente ¿para hacer esto?

- David.

Answer 3

Desde sus mapas son disjuntos a continuación, puedes recorrer el mapa más pequeño y se insertan en la más grande:

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 

En el caso de que usted está utilizando una versión anterior de OCaml que no incluye la cardinal función puede simplemente elegir un mapa para iterar siempre. En cuanto a lo que hace el código anterior, es que se usa:

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

que básicamente itera a través de todos los elementos de un mapa, y llama a una función que toma una clave, el valor y alguna otra variable de tipo 'b y devuelve algo de ese tipo ('b). En nuestro caso, estamos pasando la función IntMap.add y esa otra variable es nuestro segundo mapa. Por lo tanto, itera a través de todos los elementos y los agrega al otro mapa.

EDIT: Usted es mejor simplemente haciendo:

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

Edit2: aún mejor:

let disjoint_merge = IntMap.fold IntMap.add;; 

Yo miraba a la implementación de cardinal y camina el árbol y devuelve el recuento. Entonces al verificar los tamaños está haciendo O (n + m + min (n, m) log (max (n, m))) en lugar de solo O (n log (m)).