(F#) Find Index of element in 2D Array

Question

I'm currently having some issues finding the index of a specific element in a 2D array. I know that a standard array can use findIndex as seen below.

let wantedElemented = 5
let index = Array.findIndex(fun x -> x = wantedElemented) array

My question is, how do you apply this to a 2D array (rectangular). Is there a more efficient way than iterating through the entire array comparing each element?

for row in 0 .. max do
        for col in 0 .. max do
            if array.[row,col] = wantedElement then 
            let index = (row,col)
            index
            else (-1,-1)

If I do have to iterate through the entire array, how would I handle the else conditional without using option types

Answer 1

In response to your comment: yes, arrays cannot be matched with head and tail like lists. But they do have indicies! :-)

A recursive function does not have to recurse over the data structure. The recursing path may be defined by something different. For example: why don't we recurse over the array indicies from zero to max (or back)?

let find2D needle (arr: int [,]) = 
    let rec go x y =
          if   y >= arr.GetLength 1 then None
          elif x >= arr.GetLength 0 then go 0 (y+1)
          elif arr.[x,y] = needle   then Some (x,y)
          else go (x+1) y
    go 0 0

The above solution will scan the array in rows until it finds the needle, at which point it will immediately return.

Alternatively, you can produce yourself a sequence of optional indicies, and then use Seq.tryPick to pick the first element of that sequence that is not None:

let find2D needle (arr: int [,]) = Seq.tryPick id <| seq {
    for i in 0..(arr.GetLength 0 - 1) do
        for j in 0..(arr.GetLength 1 - 1) do
            if arr.[i,j] = needle 
                then yield Some (i,j) 
                else yield None
}

Because of how sequences work (they're lazy), this will only iterate until the first Some is found, and then stop. This is slightly more straightforward (as far as readability goes), but also slightly less performant than the plain recursive solution above, because here we incur the overhead of creating and maintaining the sequence.