# Set.S.find\_first\_opt returns None

**URL:** <https://discuss.ocaml.org/t/set-s-find-first-opt-returns-none/5420>\
**Category:** Learning\
**Tags:** stdlib\
**Created:** [April 1, 2020, 9:04am UTC](https://discuss.ocaml.org/t/set-s-find-first-opt-returns-none/5420 "2020-04-01T09:04:49Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![cloudyhug](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/cloudyhug/32/2399_2.png) [@cloudyhug](https://discuss.ocaml.org/u/cloudyhug)\
**Post date:** [April 1, 2020, 9:04am UTC](https://discuss.ocaml.org/t/set-s-find-first-opt-returns-none/5420/1 "2020-04-01T09:04:49Z")

</div>

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`:

```ocaml
(* 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" } ]

```

```ocaml
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!

---

<div class="post-metadata">

**Author:** ![octachron](https://avatars.discourse-cdn.com/v4/letter/o/49beb7/32.png) [@octachron](https://discuss.ocaml.org/u/octachron)\
**Post date:** [April 1, 2020, 9:24am UTC](https://discuss.ocaml.org/t/set-s-find-first-opt-returns-none/5420/2 "2020-04-01T09:24:44Z")

</div>

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:

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

```