# Testing whether a matrix contains a submatrix

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.

• Was there a problem with the solution I posted here? Also yay, no more prefixes :) – mjolka Aug 6 '14 at 23:19
• 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. – Ken Aug 6 '14 at 23:20
• 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. – Dan Lyons Aug 6 '14 at 23:27
• 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. – Ken Aug 6 '14 at 23:33

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.