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

I have these types :

type position = float * float
type node = position

I've written those modules to create my 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)

I've tried to write functions that used iter but my attempts to formulate my ideas in a correct syntax were unsuccessful.

My goal would be able to have a function that takes a Map as argument and return a tuple of the minimum element and its key.

Thanks.

Solution

If you're asking for the minimum key and its corresponding element, that's easy: use DistMap.min_binding_opt, or DistMap.min_binding if you're fine with raising an exception on an empty map.

If you're asking for the minimum element and its corresponding key, you will want to use a fold. Luckily, the DistMap module returned by Map.Make exposes a fold function, so you don't have to do extra allocation by, say, calling to_seq and doing a fold on the result. In addition, because the type of elements in a map is not constrained by the functor application (i.e., you can create a map with any element type), you will need the client to supply a comparison function for the element type.

DistMap.fold has type (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b, so we'll have to instantiate 'b in such a way as to keep track of both the key and the min element; in other words, we'll instantiate 'a as the element type of the map (let’s call it t), and 'b as (key * t) option (where key = position = float * float).

Here's what the code might look like:

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 will return None on an empty map.

Example client code (which you can run in an ocaml repl) might look like:

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")

In general, anytime that you want to traverse all keys/elements in a data structure and accumulate a value, a fold is the way to go. iter will sort of work, but you'll have to accumulate the value in mutable state instead of accumulating it directly as the return value of the function you're folding with.