2
\$\begingroup\$

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.
Improve this question
\$\endgroup\$
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ I agree with your symmetry argument, but I think the last match should return guess and not x \$\endgroup\$ – user73941 May 13 '17 at 5:03
0
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$ – Shaun Luttin May 13 '17 at 16:00
  • 1
    \$\begingroup\$ 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". \$\endgroup\$ – Fyodor Soikin May 13 '17 at 16:00
  • \$\begingroup\$ "Look: there are no patterns." The existence of guards for pattern matching suggests that guards are a certain type of pattern. \$\endgroup\$ – Shaun Luttin May 13 '17 at 16:04
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Fyodor Soikin May 13 '17 at 16:07
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Shaun Luttin May 13 '17 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.