Семантика слияния OCaml в функторе Map.make?

Question

Я пишу функцию OCaml, где мне нужно объединить две карты.Мне не удалось выяснить семантику функции merge, предоставленной functor Map.Make (найдена в версии 3.12.0 OCaml).Может ли кто-нибудь дать мне более подробное объяснение, чем руководство 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 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 (n log (m)).

Answer 3

На основании первого ответа и с учетом дополнительного вопроса (карты слияния в случае непересекающихся доменов) я бы тогда предложил следующую общую процедуру слияния:

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

Будут ли еще более эффективныеспособ сделать это?

- Дэвид.