Set.S.find_first_opt returns None

Learning
1

Hello.

For one of my projects, I need a data structure that is filled at the beginning of the execution, and which is almost only used for testing membership afterwards. I chose to use a set. However, at a point I need a find_opt, and I am not sure I understood well how its equivalent to List.find_opt works. Here is the set declaration, and a short code snippet that (in my head) should return Some _ but actually returns None:

(* the type t to consider *)
type morphism =
  { from_type: c_type
  ; to_type: c_type
  ; name: string
  }

(* declaration of the associated set *)
module Morphism = struct
  type t = morphism
  let compare = Stdlib.compare
end
module MorphismSet = Set.Make(Morphism)

(* example of set instance *)
let known_morphisms = MorphismSet.of_list
  [ { from_type = c_int; to_type = c_Z; name = "Z_of_int" };
    { from_type = c_Z; to_type = c_int; name = "int_of_Z" };
    { from_type = c_nat; to_type = c_Z; name = "Z_of_nat" };
    { from_type = c_Z; to_type = c_nat; name = "nat_of_Z" } ]

MorphismSet.find_first_opt (fun m -> m.from_type = c_Z && m.to_type = c_int) known_morphisms;;
(* - : MorphismSet.elt option = None *)

Does it come from the difference between find_first and find_last, which I neglected, whereas it might be important? Thanks in advance for your help!

2

The find_first and find_last function only works for monotonic functions f. In particular, find_first only works for increasing functions: if x < y for two set elements, then the function f must be such that f x < f y. This limitation is here because it is possible to do the search in logarithmic time for those functions. Otherwise, the search is linear in the size of the set.

Your function is not monotonic. You need thus to use the linear search:

let x =
      known_morphisms 
  |> Set.filter (fun m -> m.from_type = c_Z && m.to_type = c_int)
  |> Set.choose_opt
1 Like