## Monday, August 23, 2010

### 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."`