时间戳

首页 > 解决方案 > 如何在 Map 中找到最小元素并返回一个元组（键，最小元素）？

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

问题描述

我有这些类型：

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

谢谢。

标签： dictionaryocamlminimum

解决方案

如果您要求最小键及其对应元素，这很容易：使用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) optionwhere 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会起作用，但是您必须以可变状态累积值，而不是直接将其累积为您要折叠的函数的返回值。

推荐阅读