如何找到 Map 中的最小元素和 return 元组（键，最小元素）？

Question

我有这些类型：

type position = float * float
type node = position

我已经编写了这些模块来创建我的地图：

module MyMap =
  struct
  type t = node
  let compare (a1,b1) (a2,b2) =
    if a1 > a2 then 1
     else if a1 < a2 then -1
     else if b1 > b2 then 1
       else if b1 < b2 then -1

       else 0
  end

module DistMap = Map.Make(MyMap)

我尝试编写使用 iter 的函数，但我试图以正确的语法表达我的想法，但没有成功。

我的目标是能够拥有一个以 Map 作为参数和 return 最小元素及其键的元组的函数。

谢谢。

Answer 1

如果您要求最小键及其对应元素，这很简单：使用 DistMap.min_binding_opt，或者如果您可以在空地图上引发异常则使用 DistMap.min_binding。

如果您要求的是最小元素及其对应的键，则需要使用折叠。幸运的是，由 Map.Make 编写的 return 模块公开了一个 fold 函数，因此您不必通过调用 to_seq 进行额外分配并对结果进行折叠。此外，由于地图中元素的类型不受仿函数应用程序的限制（即，您可以创建具有任何元素类型的地图），因此您需要客户端提供元素类型的比较函数。

DistMap.fold 的类型为 (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b，因此我们必须实例化 'b 以跟踪 key 和 min 元素；换句话说，我们会将 'a 实例化为地图的元素类型（我们称之为 t），并将 'b 实例化为 (key * t) option（其中 key = position = float * float ).

代码可能如下所示：

let min_element_and_its_key map ~compare_element =
  let take_min key element key_and_min_element =
    match key_and_min_element with
    | None -> Some (key, element)
    | Some (key_for_min_element, min_element) ->
      if compare_element element min_element < 0
      then Some (key, element)
      else Some (key_for_min_element, min_element)
  in
  DistMap.fold take_min map None

min_element_and_its_key 将在空地图上 return None。

示例客户端代码（您可以在 ocaml repl 中运行）可能如下所示：

let map = DistMap.(empty |> add (3., 3.) "a" |> add (4., 4.) "b") in
min_element_and_its_key map ~compare_element:String.compare;;

(* Output: *)
- : (node * string) option = Some ((3., 3.), "a")

一般来说，如果您想遍历数据结构中的所有 keys/elements 并累加一个值，fold 就是可行的方法。 iter 会有点工作，但你必须在可变状态下累积值，而不是直接将它累积为你要折叠的函数的 return 值。

如何找到 Map 中的最小元素和 return 元组（键，最小元素）？

How to find the minimum element in a Map and return a tuple (key,minimum element)?

ocaml

dictionary

minimum