# Is this binary search close to idiomatic OCaml?

let binsearch ~arr ~cmp x = (
let cmpx = cmp x in
(* Assuming arr is ordered according to cmp, then (bs min max) is an   *)
(* index of a value v in arr such that ((cmp x value) = 0) between     *)
(* min (inclusive) and max (exclusive).                                *)
let rec bs min max =
if min >= max then (
None
) else (
(* mid is always strictly less than max because min < max. *)
let mid = (min + max) / 2 in
let delta = (cmpx (Array.get arr mid))
in (
if delta = 0 then (
Some mid
) else if delta < 0 then (
(* since mid < max, we make progress *)
bs min mid
) else (
bs (mid + 1) max
)))
in bs 0 (Array.length arr));;


and then it can be used thus

let a = [|1; 2; 4; 4; 4; 7; 9; 9; 11; 16|];;

let bs = binsearch ~arr:a ~cmp:compare;;

let results = (bs 0, bs 1, bs 2, bs 3, bs 4, bs 5, bs 6, bs 7, bs 8,
bs 9, bs 10, bs 11, bs 12, bs 13, bs 14, bs 15, bs 16, bs 17);;

(results = (None, Some 0, Some 1, None, Some 2, None, None, Some 5, None,
Some 7, None, Some 8, None, None, None, None, Some 9, None));;


Generally speaking, yes. I only have a couple of minor remarks.

let cmpx = cmp x in


Using partially-applied functions is actually slightly slower with the native-code compiler. The cmp function (like most functions) isn't going to do anything until it gets all its arguments, so cmpx under the hood is fun y => cmp x y. It's faster (not by much, but it can matter in an inner loop) if you write let delta = cmpx x (Array.get arr mid) below.

Speaking of which, arr.(mid) is exactly identical to (Array.get arr mid), but more usual. If you're going for speed, write Array.unsafe_get arr mid, which will save a few cycles, at the expense of putting the onus on you to verify that you are not making an array access out of bounds (here, it's easy to see that you are not).

You have many superfluous parentheses; they are a little surprising to a habitual Ocaml programmer. let … in … has lower precedence than anything else, and if … then … else … has lower precedence than arithmetic and function calls. This is how I'd write your function:

let binsearch ~arr ~cmp x =
(* Assuming arr is ordered according to cmp, then [bs min max] is an   *)
(* index of a value v in arr such that [(cmp x value) = 0] between     *)
(* min (inclusive) and max (exclusive).                                *)
let rec bs min max =
if min >= max then
None (* we are down to an empty slice of the array *)
else
(* mid is always strictly less than max because min < max. *)
let mid = (min + max) / 2 in
let delta = cmp x (Array.unsafe_get arr mid) in
if delta = 0 then Some mid else
if delta < 0
then bs min mid
else bs (mid + 1) max
in bs 0 (Array.length arr);;


(Details of when to put newlines, especially relative to in, are matters of taste.)

• Thanks. I'm a little leery of dropping parentheses since I'm learning the language and haven't wrapped my head around the operator precedence yet. The abbreviated member access is a good point though, and thanks for the performance tips on partial evaluation. Your style of one keyword at the beginning of each line and one at the end makes things flow nicely. Commented May 21, 2012 at 22:52
• the let cmpx = cmp x in is a bad idea not only because it is not good for performance but also because you use this function only once and it is never a good idea to declare a function to use it only once. Commented Jun 4, 2012 at 20:57