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.

• mjolka: Was there a problem with the solution I posted here? Also yay, no more prefixes :)
• Ken: Not as far as I know, and thanks for that. I just needed to learn tail recursion and this was a good way to do it. I'm going to implement your slice method as an alternative later on.
• Dan Lyons: Joining the declarations of start height/width makes sense because of tuple decomposition, but I'm not sure I would join the search height/width declarations.
• Ken: Yeah, I keep swinging back and forth with my opinion on that, but for now I think I'm leaving it just because it lines up nicely with the tuple unpacking.

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.