Match List Items in Any Order

Question

I'm still a novice when it comes to many areas of F#. I'm asking this question more out of curiosity than out of an actual business need. Is there any way to match the first n items in a list regardless of what order they appear? To clarify, consider the following example:

type MyEnum = 
    | Foo of int
    | Bar of float
    | Baz of string
let list = [ Foo 1 ; Bar 1.0 ; Baz "1" ]

Now, suppose I want to call some_func if the first two items in the list are a Foo and a Bar, in any order. It's fairly easy to just match the two possible permutations:

let result = 
    match list with
    | Foo n :: Bar x :: _ 
    | Bar x :: Foo n :: _ -> some_func n x
    | _ -> failwith "First 2 items must be Foo and Bar"

However, what if I need to call a function if the first 3 items are a Foo, Bar and Baz in any order? Using the same technique above would require me to write all 6 different permutations (or n! for n items). Ideally, I'd like to be able to do something along the lines of this:

let result = 
    match list with
    | (AnyOrder [ Foo n ; Bar x ; Baz s ]) :: _ -> some_func n x s
    | _ -> failwith "First 3 items must be Foo, Bar, and Baz"

Is there any way to accomplish this with an active pattern of some sort, without having to hard-code the different permutations?

Answer 1

Here's one attempt at solving the problem. It scores each union case using a bitmap, and checks that the sum of the scores is 7:

let (|AnyOrder|_|) s =
    let score = function | Foo _ -> 1 | Bar _ -> 2 | Baz _ -> 4
    let firstElementsWithScores =
        s
        |> Seq.truncate 3
        |> Seq.map (fun x -> x, score x)
        |> Seq.sortBy (fun (_, x) -> x)
        |> Seq.toList
    let sumOfScores =
        firstElementsWithScores |> List.sumBy (fun (_, x) -> x)
    if sumOfScores = 7
    then
        match firstElementsWithScores |> List.map fst with
        | [Foo x ; Bar y ; Baz z ] -> Some (x, y, z)
        | _ -> None
    else None

If the score is 7, it truncates the input list and sorts it, and then uses pattern matching against the truncated, scored list in order to create a tuple of the matching elements.

Here's one way to use it:

let checkMatches s =
    match s with
    | AnyOrder (x, y, z) -> [Foo x; Bar y; Baz z]
    | _ -> []

Some examples from FSI:

> checkMatches list;;
val it : MyEnum list = [Foo 1; Bar 1.0; Baz "1"]
> checkMatches [Foo 1; Bar 1.0; Foo 2];;
val it : MyEnum list = []
> checkMatches [Foo 1; Bar 1.0; Baz "1"; Foo 2];;
val it : MyEnum list = [Foo 1; Bar 1.0; Baz "1"]
> checkMatches [Foo 1; Bar 1.0; Bar 2.0; Foo 2];;
val it : MyEnum list = []
> checkMatches [Bar 1.0; Foo 1; Baz "2.0"; Foo 2];;
val it : MyEnum list = [Foo 1; Bar 1.0; Baz "2.0"]

AnyOrder is a partial active pattern with the signature

seq<MyEnum> -> (int * float * string) option

Answer 2

Very interesting case. The solution Mark proposed works fine, but the drawback is the function is not reusable, I mean is very specific to that DU.

Here's a generic solution, but the drawback here is you need to specify the list in the order the DU was created.

let (|AnyOrderOfFirst|) n = Seq.take n >> Seq.sort >> Seq.toList

let result = 
    match list with
    | AnyOrderOfFirst 3 [ Foo n ; Bar x ; Baz s ] -> some_func n x s
    | _ -> failwith "First 3 items must be Foo, Bar, and Baz"

If you change your DU changing the order of the TAGs and forget to reorder them also in the list it will never match.

If you want to go this generic way my advice is: create a Unit Test to assert the match is always working.