Elegant pattern matching on nested tuples of arbitrary length

Question

I'm developing a composable functional UI library in F#, and I ran into a situation where I need to be able to create "collections" of items of heterogenous types. I don't want to accomplish this by resorting to dynamic programming and casting everything to obj (technically possible here, esp. since I'm compiling with Fable). Instead I want to retain as much type safety as possible.

The solution I came up with is to create a simple custom operator %%% that builds tuples and then use it as follows:

let x = 4 %%% "string" %%% () %%% 2.4

This produces a value with following type:

val x: (((int * string) * unit) * float)

The resulting types seem a bit messy (especially as the number of values increases), but it ensures strong type safety for my scenario and will (ideally) be somewhat hidden to users of the library.

But I'm trying to figure out an elegant way to pattern match with these nested tuple types, since the library users will sometimes need to write functions on these values. Obviously this could be done manually like,

match x with
| (((a,b),c),d) -> ...

and the compiler infers the correct types for a, b, c, and d. However, I don't want the user to have to worry about all that nesting. I'd love to be able to do something like,

match x with
| a %%% b %%% c %%% d -> ...

and have the compiler just figure everything out. Is there a way to accomplish something like that with F# using active patterns (or some other feature)?

EDIT:

I should clarify that I'm not trying to match on tuple values of unknown "arity" at runtime. I only want to do this when the number (and types) of elements is known at compile time. If I was doing the former, I'd be fine with a dynamic approach.

For now, I've created active patterns:

let (|Tuple2|) = function | (a,b)-> (a,b)
let (|Tuple3|) = function | ((a,b),c) -> (a,b,c)
let (|Tuple4|) = function | (((a,b),c),d) -> (a,b,c,d)
...

Which can be used like this:

let x = 4 %%% "string" %%% () %%% 2.4
let y = match x with | Tuple4 (a,b,c,d) -> ...

This is probably the best that can be done, and it's really not that bad for users (just have to count the "arity" of the tuple and then use the right TupleN pattern). However it still bugs me because it just doesn't seem as elegant as it could be. You don't have to specify the number of elements when creating x, why should you have to do so when matching on it? Seems asymmetric to me, but I don't see a way to avoid it.

Are there deeper reasons why my original idea won't work in F# (or statically typed languages in general)? Are there any functional languages where it would be possible?

Answer 1

Mark Seeman has given you the correct answer. I'm instead going to do something completely different, and show you why the thing you're trying to do with complex tuples won't actually work, even if you try the "hard-coded patterns for each possible number of items" approach that you don't like. Here are a number of attempts at implementing your idea, which won't work:

Attempt #1

First, let's try to write a function that will recursively throw away all the tail elements of the tuple until it's down to the first pair, then return that pair. In other words, something like List.take 2. If this works, we could apply a similar technique to extracting other parts of the complex tuple. But this won't work, and the reason why is very instructive. Here's the function:

let rec decompose tuple =
    match tuple with
    | ((a,b),c) -> decompose (a,b)
    | (a,b) -> (a,b)

If I type that function into a good F# IDE (I use VS Code with the Ionide plugin), I'll see a red squiggly under the a in the recursive decompose (a,b) call. That is because the compiler is throwing the following error at that point:

Type mismatch. Expecting a
    'a * 'b
but given a
    'a
The resulting type would be infinite when unifying ''a' and ''a * 'b'

This is the first clue as to why this won't work. When I hover over the tuple argument in VS Code, Ionide shows me the type that F# has inferred for tuple:

val tuple : ('a * 'b) * 'b

Wait, what? Why a 'b for the final part of that composed tuple? Shouldn't it be ('a * 'b) * 'c? Well, that's because of the following match line:

| ((a,b),c) -> decompose (a,b)

Here we are saying that the tuple argument and its types must be of a shape that can match this line. Therefore, tuple must be a 2-tuple, since we're passing a 2-tuple in as the parameter to decompose in this particular call. And therefore, the second part of that 2-tuple must match the type of b, otherwise it would be a type error to call decompose with (a,b) as a parameter. Therefore, c in the pattern (the second part of the 2-tuple) and b in the pattern (the second part of the "inner" 2-tuple) must have the same type, and that's why the type of decompose is constrained to ('a * 'b) * 'b instead of ('a * 'b) * 'c.

If that made sense, then we can move on to why the type mismatch error is happening. Because now, we need to match the a part of the recursive decompose (a,b) call. Since the tuple we pass to decompose must match its type signature, that means that a must match the first part of the 2-tuple, and we already know (since the tuple parameter must be capable of matching the ((a,b),c) pattern in the match statement, otherwise that statement wouldn't compile) that the first part of the 2-tuple is itself another 2-tuple, of type 'a * 'b. Right?

Well, and that's the problem. We know that the first part of decompose's parameter must be a 2-tuple, of type 'a * 'b. But the match pattern has also constrained the parameter a to be of type 'a, because we're matching something with type ('a * 'b) * 'b against ((a,b),c). So one part of the line forces a to have type 'a, and the other part forces it to have the type ('a * 'b). These two types cannot be reconciled, and so the type system throws a compile error.

Attempt #2

But wait! What about active patterns? Maybe they can save us? Well, let's take a look at another thing I tried, which I thought was going to work. And when it failed, it actually taught me more about F#'s type system, and why what you want isn't going to be possible. We'll talk about why in a moment; but first, here's the code:

let (|Tuple2|_|) t =
    match t with
    | (a,b) -> Some (a,b)
    | _ -> None

let (|Tuple3|_|) t =
    match t with
    | ((a,b),c) -> Some (a,b,c)
    | _ -> None

let (|Tuple4|_|) t =
    match t with
    | (((a,b),c),d) -> Some (a,b,c,d)
    | _ -> None

let (|Tuple5|_|) t =
    match t with
    | ((((a,b),c),d),e) -> Some (a,b,c,d,e)
    | _ -> None

Type that into your IDE, and you'll see an encouraging sign. It compiles! And if you hover over the t parameter in each of these active patterns, you'll see that F# has determined the correct "shape" for t in each one. So now, we should be able to do something like this, right?

let (%%%) a b = (a,b)

let complicated = 5 %%% "foo" %%% true %%% [1;2;3]

let result =
    match complicated with
    | Tuple5 (a,b,c,d,e) -> sprintf "5-tuple of (%A,%A,%A,%A,%A)" a b c d e
    | Tuple4 (a,b,c,d) -> sprintf "4-tuple of (%A,%A,%A,%A)" a b c d
    | Tuple3 (a,b,c) -> sprintf "3-tuple of (%A,%A,%A)" a b c
    | Tuple2 (a,b) -> sprintf "2-tuple of (%A,%A)" a b
    | _ -> "Not matched"

(Note the order: since ALL your complex tuples are 2-tuples, with a complex tuple as the first part of the 2-tuple, the Tuple2 pattern would match any such tuple if it were first.)

This seems promising, but it also won't work. Type (or paste) that into your IDE and you'll see a red squiggly under the Tuple5 (a,b,c,d,e) pattern (the first pattern of the match statement). I'll tell you what the error is in a minute, but first, let's hover over the definition of complicated and make sure that it's correct:

val complicated : ((int * string) * bool) * int list

Yes, that looks correct. So since that can't possibly match the Tuple5 active pattern, why doesn't that active pattern just return None and let you move on to the Tuple4 pattern (which would work)? Well, let's look at the error:

Type mismatch. Expecting a
    ((int * string) * bool) * int list -> 'a option
but given a
    ((('b * 'c) * 'd) * 'e) * 'f -> ('b * 'c * 'd * 'e * 'f) option
The type 'int' does not match the type ''a * 'b'

There's no 'a in either of the two mismatched types. Where did the 'a come from? Well, if you specifically hover over the word Tuple5 in that line, you'll see Tuple5's type signature:

active recognizer Tuple5: ((('a * 'b) * 'c) * 'd) * 'e -> ('a * 'b * 'c * 'd * 'e) option

That's where the 'a came from. But more importantly, the error message is telling you that the first part of complicated, an int, can't match a 2-tuple. Why would it be trying to do so? Again, because match expressions must match the type of the thing they're matching, and therefore they constrain that type. Just as we saw with the decompose function, it's happening here too. You can see it better by changing the let result variable into a function, like so:

let showArity t =
    match t with
    | Tuple5 (a,b,c,d,e) -> sprintf "5-tuple of (%A,%A,%A,%A,%A)" a b c d e
    | Tuple4 (a,b,c,d) -> sprintf "4-tuple of (%A,%A,%A,%A)" a b c d
    | Tuple3 (a,b,c) -> sprintf "3-tuple of (%A,%A,%A)" a b c
    | Tuple2 (a,b) -> sprintf "2-tuple of (%A,%A)" a b
    | _ -> "Not matched"

showArity complicated

The showArity function compiles without error now; you might be tempted to rejoice, but you'll see that it can't be called with the complicated value we defined earlier, and that you get the same type mismatch error (where, ultimately, int can't match 'a * 'b). But why does showArity compile without error? Well, hover over the type of its t argument:

val t : ((('a * 'b) * 'c) * 'd) * 'e

So t has been constrained to be what I'll call a "complex 5-tuple" (which is really still just a 2-tuple, remember) by that first Tuple5 pattern. And the other Tuple4, Tuple3 and Tuple2 patterns will match because they actually are matching 2-tuples in reality. To show that, delete the Tuple5 line from the showArity function and look at its result when you run showArity complicated in F# Interactive (you'll have to re-run the definition of showArity as well). You'll get:

"4-tuple of (5,"foo",true,[1; 2; 3])"

Looks good, but wait: now delete the Tuple4 line, and re-run the definition of showArity, as well as the showArity complicated line. This time, it produces:

"3-tuple of ((5, "foo"),true,[1; 2; 3])"

See how it matched, but didn't decompose the "innermost" tuple (of int * string)? That's why you needed the ordering correct. Run it one more time with only the Tuple2 line remaining, and you'll get:

"2-tuple of (((5, "foo"), true),[1; 2; 3])"

So this approach won't work either: you can't actually determine the "fake arity" of a complex tuple. ("Fake arity" in scare quotes because the arity of all these tuples is really 2, but we're trying to treat them as if they're 3- or 4- or 5-tuples). Because any pattern whose "fake arity" is less than that of the complex tuple you're handing it will still match, but it won't have decomposed some part of the complex tuple. While any pattern whose "fake arity" is greater than that of the complex tuple you're handing it just won't compile, since it creates a type mismatch between on the innermost part of the tuple you're matching against.

I hope reading through all of this has given you a better understanding of the intricacies of F#'s type system; I know that writing it has certainly taught me a lot.

Answer 2

It looks like you're attempting to build up a semantic model of some sort, although it's not entirely clear to me exactly what it is.

As John Palmer hints, a way this is often done in statically typed functional programming languages is to define a type to hold the heterogeneous values of the model. In this case, it could be something like this:

type Model =
| Integer of int
| Text of string
| Nothing
| Float of float

(Apologies for the vague naming, but as stated, it's not clear to me exactly what you're trying to model.)

You can now build up values of this type:

let x = [Integer 4; Text "string"; Nothing; Float 2.4]

In this case, the type of x is Model list. You now have a data type you can trivially pattern match on:

match x with
| [Integer i; Text s; Nothing; Float f] -> ...

If you can come up with better names than the ones I chose here, this may even make the API useful and intuitive.