How does find_first function work for an OCaml Set?

user_4462975 0
Viewed 72

I am struggling to understand why the following code does not find any matching result:

module IntPairs =
struct
  type t = int * int
  let compare (x0,y0) (x1,y1) =
    match Stdlib.compare x0 x1 with
      0 -> Stdlib.compare y0 y1
    | c -> c
end
module PairsSet = Set.Make(IntPairs) 
let m2 = PairsSet.(empty |> add (2,0) |> add (1,2) |> add (0,1)) 
let result = PairsSet.find_first_opt (fun (input,value) -> print_endline ("arg:"^(string_of_int input)^" val:"^(string_of_int value)); input=0) m2;;
match result with
| None -> "nope"
| Some _ -> "yep";;

My understanding based on the documentation: https://ocaml.org/api/Set.S.html is that the find_first function should traverse from the smallest element (in this case it would be the (0,1) pair) checking whether any element meets the condition in provided function.

It does not however work as described above since it starts from the greatest element (2,0) and checks only this one element. I have checked if the order of provided elements has any impact on how find_first function works and it does. If I rearrange the m2 set so that the (0,1) element is first a match will be found.

ocaml
1 Answers

This confused me a fair bit as well, but the key here is in "where f is a monotonically increasing function".

A monotonically increasing function is a function which must not decrease (despite its name it must not necessarily increase). For a function returning a bool, like we have here, that means it cannot go from true to false as the input value increases.

Your function fun (input, value) -> input = 0 is true only for a single value. It is false for any value below 0 and any value greater than 0.

find_first is implemented such that it walks "downwards" as long as f returns true, and "upwards" as long as it returns false, thereby finding the first element for which f returns true.

If instead you use the function fun (input, value) -> input >= 0 you'll hopefully find it will work as you expect.

user_79435640
Related