Testing whether a matrix contains a submatrix

Question

As part 2 of my other question concerning this long running project I've been inquiring about on CR, I reimplemented my generic function for determining if an array of arrays is a sub-array or submatrix of a larger array of arrays.

I'm looking for advice on better implementation, ways to improve code clarity, advice on best practices and anything else that might be useful. This is my new implementation:

---

namespace MathAlgorithms

module ArrayFunctions = 
    // Generic because it makes testing easier, yay math
    let IsSubMatrix (smallArray:'a[][]) (largeArray:'a[][]) (startCoordinate:(int * int)) =
        let searchHeight , searchWidth = smallArray.Length - 1 , smallArray.[0].Length - 1
        let startHeight  , startWidth  = startCoordinate

        try 
            let WidthLoop heightIndex = 
                let rec WidthLoopRec heightIndex widthIndex =
                    let largeValue = largeArray.[startHeight + heightIndex].[startWidth + widthIndex]
                    let smallValue = smallArray.[heightIndex].[widthIndex]

                    match ( smallValue = largeValue , widthIndex < searchWidth ) with
                    | ( true  , true  ) -> WidthLoopRec heightIndex (widthIndex + 1)
                    | ( true  , false ) -> true 
                    | ( false , _     ) -> false
                WidthLoopRec heightIndex 0

            let HeightLoop () =
                let rec HeightLoopRec heightIndex = 
                    let isMatch = WidthLoop heightIndex

                    match ( isMatch , heightIndex < searchHeight) with
                    | ( true  , true  ) -> HeightLoopRec ( heightIndex + 1 )
                    | ( true  , false ) -> true
                    | ( false , _     ) -> false
                HeightLoopRec 0

            HeightLoop ()
            
        with // Not really sure what I want to do with error handling atm
            | :? System.ArgumentOutOfRangeException -> false
            | :? System.ArgumentNullException       -> false
            | :? System.ArgumentException           -> false

---

I ran this code through my tests, and it's functionally the same as the old while-do version which I'm including for comparison's sake:

---

namespace MathAlgorithms

module ArrayFunctions = 
    // Generic because it makes testing easier, yay math
    let SearchSubset (tSmallArray:'a[][]) (tLargeArray:'a[][]) (pCoordinate:(int * int)) =
        let tSmallHeight = tSmallArray.Length
        let tSmallWidth = tSmallArray.[0].Length

        let tHeightIndex = fst pCoordinate
        let tWidthIndex = snd pCoordinate
        let mutable tSmallHeightIndex = 0
        let mutable tSmallWidthIndex = 0
        let mutable tMatch = true

        try 
            while ( tSmallHeightIndex < tSmallHeight - 1 ) && tMatch do
                while ( tSmallWidthIndex < tSmallWidth - 1 ) && tMatch do
                    let tLargeCurrentValue = tLargeArray.[tHeightIndex + tSmallHeightIndex].[tWidthIndex + tSmallWidthIndex]
                    let tSmallCurrentValue = tSmallArray.[tSmallHeightIndex].[tSmallWidthIndex]

                    if tSmallCurrentValue = tLargeCurrentValue then
                        tSmallWidthIndex <- tSmallWidthIndex + 1         
                    else
                        tMatch <- false

                tSmallWidthIndex  <- 0
                tSmallHeightIndex <- tSmallHeightIndex + 1

            tMatch
        with
            | _ -> false

---

Github for further info:

https://github.com/Kenneth-Posey/LearningFsharp/tree/master/FsharpTutorial/YeFsharpLibrary

The use of the function is in the module FsharpImaging.fs, it's tested by UnitTest.fs and it's located in ArrayFunctions.fs.

Answer 1

A few suggestions regarding the style:

1. There's no need for parentheses in the pattern matching blocks. Those are evaluated as tuples by the very fact that they are comma separated:

   match smallValue = largeValue, widthIndex < searchWidth with
   | true, true  -> WidthLoopRec heightIndex (widthIndex + 1)
   | true, false -> true 
   | false, _    -> false
   

   and:

    match isMatch , heightIndex < searchHeight with
    | true, true  -> HeightLoopRec (heightIndex + 1)
    | true, false -> true
    | false, _    -> false
   

2. In HeightLoopRec, there's no need for isMatch. You can use the result of calling WidthLoop directly inside the pattern matching (maybe with parentheses to make it more legible):

   match (WidthLoop heightIndex), heightIndex < searchHeight with
   

3. The function HeightLoop is not needed and can be removed and replaced by its contents, making HeightLoopRec the top level function. This is obvious by its signature (unit -> bool). It doesn't take anything as input, unlike its internal tail-recursive function whose signature is int -> bool.

4. WidthLoop can be inlined (let inline WidthLoop heightIndex =).

5. I think it would be better to handle the exceptions before getting into the actual computation. In fact, if the code base is done in F#, there should be no null values (as those would be replaced by option types). Within your code domain, illegal values should be made unrepresentable, as the famous motto goes.

   This should also account for out-of-range indexing. If a mathematical operation makes no sense, the typing itself should not allow it to be made.

   You could use FsCheck to test your code with random values to see that your code never raises exceptions. Logically, "no answer" should not be represented as false. If a function may return no value at all or a bool, then its return type should be bool option, where None would represent the lack of a valid result.

6. Your function name should probably reflect more clearly their intention. I'm not a mathematician, but I guess you would mean something like isRowContained (instead of WidthLoop), or whatever makes sense.