Bound Variables in F#: What Reflection Reveals

It’s been a while since my last post. What can I say? Reading, end of summer stuff, jury call (you don't want to know), etc. But a large part of my time has been spent learning about fuzzy logic and doing some F# experiments in fuzzy logic. I hope to post more about that in the next day or two, but today I like to post something about F# I learned while doing those experiments.

The code below shows two ways to code a binary search. The difference is not great, but to my mind at least, the first example is a more traditional implementation, while the second has more of a functional flavor. In the first example (suffixed with “0”), the test value is passed around as a parameter and the comparison function takes two arguments. In the second example (suffixed with “1”), the test value is bound to a comparison function which only takes a single argument. (As always, all the code here is presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

My questions were: what are the differences between the generated IL, and which method is more efficient? Looking at the IL using reflection, the result was obvious:

In the version of F# that ships with VS2010, compiled in release mode, the two examples generate identical code.

Which I must admit was a pleasant surprise.

let inline bsearch0 (cmp:'V0->'V1->int) (a:'V0[]) (v:'V1) =

  let rec f lo hi =

    match lo>hi with

    | true -> None

    | _ ->

      let mid = lo+(hi-lo)/2

      match cmp a.[mid] v with

      | 0 -> Some(a.[mid])

      | x when x<0 -> f (mid+1) hi

      | _ -> f lo (mid-1)

  f 0 (a.Length-1)

let inline bsearch1 (cmp:'V0->int) (a:'V0[]) =

  let rec f lo hi =

    match lo>hi with

    | true -> None

    | _ ->

      let mid = lo+(hi-lo)/2

      match cmp a.[mid] with

      | 0 -> Some(a.[mid])

      | x when x<0 -> f (mid+1) hi

      | _ -> f lo (mid-1)

  f 0 (a.Length-1)

type T = { A:int; B:int; }

let search0 (a:T[]) i =

  let f (t:T) i = t.A-i

  bsearch0 f a i

let search1 (a:T[]) i =

  let f (t:T) = t.A-i

  bsearch1 f a 

printfn "Your breakpoint here."