如何在 Map 中找到最小元素并返回一个元组（键，最小元素）？

Question

我有这些类型：

type position = float * float
type node = position

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

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 作为参数并返回一个包含最小元素及其键的元组。

谢谢。

Answer 1

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

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

DistMap.fold有 type (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b，所以我们必须以'b这样一种方式实例化，以跟踪 key 和 min 元素；换句话说，我们将实例'a化为地图的元素类型（我们称之为t），以及'b作为(key * t) option(where 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将返回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")

一般来说，任何时候你想要遍历数据结构中的所有键/元素并累积一个值， afold是要走的路。iter会有点工作，但是您必须在可变状态下累积该值，而不是直接将其累积为您正在折叠的函数的返回值。