How to pattern match this efficiently?

Question

I would like to match an integer array against the following pseudo patterns: where a means these numbers are the equal or 0 (i.e. assume any number "equals" 0)

[| a; a; a; a; a; |]          // matches [| 1; 1; 0; 0; 1 |]
[| a; a; a; not a; a; |]      // matches [| 3; 3; 0; 2; 3 |]
[| a; a; not a; a; a; |]      // matches [| 4; 4; 2; 0; 4 |]
[| a; not a; a; a; not a; |]  // matches [| 1; 2; 0; 0; 3 |]
[| a; a; a; not a; a; |]      // matches [| 1; 1; 0; 4; 1 |]
[| not a; a; a; a; a; |]      // matches [| 5; 1; 0; 1; 1 |]

How do I do this?

Answer 1

In your examples, the first element of the array is always a you can match on a boolean array:

match Array.map (fun x -> x = Array.get arr 0 || x = 0) arr with
| [| true; true; true; true; true; |] -> ... // matches [| 1; 1; 0; 0; 1 |]
| [| true; true; true; false; true; |] -> ... // matches [| 3; 3; 0; 2; 3 |]
| [| true; true; false; true; true; |] -> ... // matches [| 4; 4; 2; 0; 4 |]
| [| true; false; true; true; false; |] -> ... // matches [| 1; 2; 0; 0; 3 |]
| [| true; true; true; false; true; |] -> ... // matches [| 1; 1; 0; 4; 1 |]
| _ -> ...

This will create a temporary array, but it isn't a big deal with arrays of small sizes.

UPDATE:

If the first a is in another column, you simply project on that column and do another pattern matching (there are at most 5 matches for 5 columns).

match Array.map (fun x -> x = Array.get arr 1 || x = 0) arr with
| [| false; true; true; true; true; |] -> ... // matches [| 5; 1; 0; 1; 1 |]
| ...

That said, when the number and the complexity of pseudo-patterns grow, it's better to use functions instead of pattern matching.

Answer 2

You can define an active pattern that is parameterized by a pattern that you want to detect. In your example, you write these patterns using a pseudo-syntax with array containing either a or not a, but you could quite easily write them as actual arrays that contain the same value when you want to have matching values in the input. For example, something like:

[| 'a'; 'a'; 'b'; 'a'; 'a'; |]

It could even be a string as in @bytebuster's solution (you can convert string to char[] using the ToCharArray method). Then you can define active pattern:

let inline (|ArrayPattern|_|) pattern input =
  let matches =
    Array.zip pattern input
    |> Seq.groupBy fst 
    |> Seq.forall (fun (_, values) -> 
        let cases = values |> Seq.map snd |> set
        Set.count (cases - Set.singleton 0) <= 1)
  if matches then Some() else None  

I guess this is essentially the same as what @bytebuster implements. Here, I group the elements of the input array by their corresponding key in the pattern and then use set operations to check that there is at most one non-zero value for each group.

To use it, you can now match an int[] against ArrayPattern [| ... |] where the array parameter specifies the specific pattern you're looking for:

match [| 1; 1; 2; 0; 1 |] with 
| ArrayPattern [| 'a'; 'a'; 'b'; 'a'; 'a'; |] -> printfn "match"
| _ -> printfn "not"