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?

Mark Seemann · Answer 1 · 2014-11-06T08:38:48.683

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

Gus · Accepted Answer · 2014-11-06T13:58:14.893

4

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.

edited Nov 06 '14 at 13:58

answered Nov 06 '14 at 09:36

Gus

25,839
2
51
76

Nice. I like the very simple approach. The only slightly annoying thing is that the list in the match expression *has* to be sorted—`AnyOrderOfFirst 3 [ Bar x ; Foo n ; Baz s ]` would never match. I also like that you could do something like '2 of the first 4 are `Foo`'s' with `AnyOrderOfFirst 4 [ Foo a ; Foo b ; _ ; _ ]`, but to do the same with `Bar`'s you'd have to write 3 cases different cases. – p.s.w.g Nov 06 '14 at 13:20
Yes, that's the drawback of this solution: the list in the match MUST be sorted and the sort order is the order in which the TAGs are declared in the DU. That should be always in sync. – Gus Nov 06 '14 at 13:26

Match List Items in Any Order

2 Answers2