Простой способ найти ключ на карте с помощью привязки, Ocaml - PullRequest
Новая
       15

Простой способ найти ключ на карте с помощью привязки, Ocaml

3 голосов
/ 03 июля 2011

Я не очень знаком с модулем карты в Ocaml.

У меня есть простая карта m: string Map.Make(Int).t от int до string, и я знаю, что каждая привязка (:string) уникальна. Я хотел бы написать функцию find_from_string_to_int: string -> string Map.Make(Int).t -> int, кто-нибудь может помочь? Большое спасибо!

1 Ответ

3 голосов
/ 03 июля 2011

Если это нечастая операция, самый простой способ - сложить все привязки (ключ, значение) карты SMap.fold: 

# module SMap = Map.Make(String);;
# let reverse v t =
  SMap.fold (fun k v' acc -> if v = v' then Some k else acc) t None;;
val reverse : 'a -> 'a SMap.t -> SMap.key option = <fun>

Если это обычная операция, вам нужна двунаправленная карта (карта, которую можно запрашивать в обоих «направлениях»). Самый простой способ - носить с собой пару карт: int IMap.t * string SMap.t (доступ в обоих направлениях является логарифмическим, в то время как reverse выше является линейным по размеру карты). Вы также можете реализовать выделенную структуру данных, но это, вероятно, не стоит дополнительной сложности.

PS: reverse можно оптимизировать так, чтобы досрочно завершить итерацию, если найдено значение, но если это необычная операция, это все равно не так важно.

...