Immutable recursive binary search of a generic array

Question

I am new to F#. Is the following code, which represents about three hours of work, a canonical way to achieve binary search? If not, how can it be improved for readability and maintainability?

let binarySearch (array: 'a[]) (target: 'a) = 
 let rec search min max =
 match (min, max) with 
 | (min, max) when max < min -> -1 
 | _ -> 
 let guess = ((min + max) / 2);
 match array.[guess] with
 | x when x = target -> guess 
 | x when x < target -> search (guess + 1) (max) 
 | _ -> search (min) (guess - 1) 
 search (0) (array.Length - 1) 

Aspects that I already like:

• hiding the recursive function within the non-recursive function.
• using pattern matching instead of if-else-then, based on suggestions here,
• accepting generic types with `a.

Answer 1

I would strive for symmetry:

 match array.[guess] with
 | x when x > target -> search (min) (guess - 1) 
 | x when x < target -> search (guess + 1) (max) 
 | _ -> guess

• user73941: I agree with your symmetry argument, but I think the last match should return guess and not x

Answer 2

This is abuse of pattern matching. Look: there are no actual patterns! You misunderstood what Mr. Wlaschin is saying in the link you provided: pattern matching is not always better than if-then-else, only in cases when there are actual patterns. In this case, if-then-else leads to much more comprehensible code:

let binarySearch (array: 'a[]) (target: 'a) = 
 let rec search min max =
 if max < min then -1 
 else
 let guess = ((min + max) / 2);
 let x = array.[guess]
 if x > target then search (min) (guess - 1) 
 elif x < target then search (guess + 1) (max) 
 else guess
 search (0) (array.Length - 1) 

• Shaun Luttin: That reminds me of Mr. Wlashin's comment: "avoid using imperative control flow when you are learning to think functionally." [emphasis added]. Once I've learned to think functionally, using if-else-then might be better. A suggestion for your answer: I think it's more realistic to say that if-else-then might be a better approach, rather than saying that this is an abuse of pattern matching.
• Fyodor Soikin: if-then-else is not inherently "imperative control flow". It might look like that to the uninitiated, because it looks, on the surface, similar to constructs widely used in imperative languages. However, if-then-else of F# is different from similar construct of C# in a critical way: it is an expression, not a"command". In this capacity, it is widely used even in mathematics, e.g. "modulus of x is x if x >= 0, and -x otherwise".
• Shaun Luttin: "Look: there are no patterns." The existence of guards for pattern matching suggests that guards are a certain type of pattern.
• Fyodor Soikin: No, they are not. Guards and patterns are two different things. The point is, if your pattern-matching expression has nothing but guards, it is equivalent to if-then in power, but is longer and less readable.
• Shaun Luttin: This corroborates what you said: "Pattern matching is based on patterns only -- it can't use functions or other kinds of conditional tests." fsharpforfunandprofit.com/posts/match-expression It then suggests guards as an alternative when patterns are not available. So, as you said, they are two different things. The same article does fizzBuzz entirely with guards. It seems that doing a match with entirely guards is an alternative to if-then-else, and that the choice between the two is stylistic.