4
\$\begingroup\$

I come from a C#/JavaScript/TypeScript background and am learning F# by implementing fundamental algorithms. This is finding the minimum value in an array:

let findMinimumValueIndex (array: int[]): int =
    let rec find (index: int) (minimumValueIndex: int) = 
        let findNext = find (index + 1)
        match index with 
        | i when i >= array.Length -> minimumValueIndex // base case
        | i when array.[i] < array.[minimumValueIndex] -> findNext i
        | _ -> findNext minimumValueIndex
    find 0 0

It works. I like the partial application of arguments in the findNext function. I like the nested rec function.

Questions

  1. How can we make this code more readable?
  2. How can we make this code a better match of canonical F# style?
  3. Should we be using if... then... else instead of match when?
  4. Should we be using more explanatory variables?

Test

[<Fact>]
let ``findMinimum returns the index of the minimum value in an array`` () = 
    let array = [|4; 5; 6; 7; 3; 2; 7; 4; 6; 8; 3|]
    let result = findMinimumValueIndex array
    Assert.StrictEqual(result, 5);
\$\endgroup\$
6
\$\begingroup\$
  • I think there's no need to use the match keyword here because you're not actually doing any pattern matching, only shadowing the name index with i. I've change it to use if/then/else.

  • Removing all of the type annotations makes the function more generic and more concise. I've done this below and used the function Array.length to allow the compiler to infer that array is an array. The input type has changed from int [] to 'a [] where 'a has comparison, making the function reusable for other array types. However, this also makes the function a lot slower for some reason so I've marked it as inline to get the re-usability benefits without the performance hit.

  • I think the findNext function isn't really necessary for readability, but that is probably down to personal preference. I noticed that it makes the function much much slower for a large array so I have removed it. Making it inline has a similar effect.

That leaves us with this:

let inline findMinimumValueIndex array =
    let rec find i minimumValueIndex = 
        if i >= Array.length array then minimumValueIndex // base case
        elif array.[i] < array.[minimumValueIndex] then find (i + 1) i
        else find (i + 1) minimumValueIndex
    find 0 0

If I actually needed to do this in code, I would probably do this instead:

array |> Seq.indexed |> Seq.minBy snd |> fst

This is simple enough that it might not even be worth defining a function for, though it is quite slow compared to my refactoring of your function above.

However, for an empty input array this throws an exception, which isn't very functional. And your function returns 0 for an empty array, which can be ambiguous as it's also the result if the first item is smallest. So you could handle that case and return int option instead of int:

let inline minIndexSafe array =
    if array = [||] then None
    else array |> Seq.indexed |> Seq.minBy snd |> fst |> Some
\$\endgroup\$

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.