Pattern Matching in TypeScript with Record and Wildcard Patterns
Pattern matching allows programmers to compare data with defined structures to easily pick one of the available expressions. Many languages that are designed as ‘functional programming languages’ have built-in keywords for pattern matching. Well known examples are F# (match … with
) or Haskell (case … of
). One language that works very well with functional programming but lacks those features is TypeScript. In this article we will build a small library to add support for pattern matching to TypeScript. We will implement a lot of advanced features like record, wildcard and array patterns. We will also make sure that the type inference of TypeScript understands our patterns and narrows the types when ever possible.
The Basic Foundation
We start of with a builder API that mimics the syntax of the match keyword in F# (as shown above). This will serve as the foundation of the library on which we will build the more sophisticated features. The starting point is the match
function that we pass the input value for the patterns. This returns a builder on which we can call with
to add a pattern, can call otherwise
to set the fallback value and can call run
to find the matching pattern and execute its expression.
This implementation is at the moment nothing more than a (complicated) lookup table, but we will be adding all the promised features further down the line. Now we have drawn the first sketch down, we can continue with defining the additional requirements to expand the idea to a truly powerful tool.
Record Patterns
In modern applications data comes in a wide variety of complex data structures. A common application of pattern matching is checking if a given value matches a certain data structure. This is where pattern matching starts becoming more declarative than traditional if-statements for which the developer need to provide a list of conditions that imply the structure. For example, we could check how many dimensions a vector has by running a set of conditions:
The pattern matching way of doing this would be to define the structure of the vectors and execute the relevant expression based on those. An example of this is found below. Note that those patterns describe more that we did in our if statement. We don’t assume anymore that we have an x
and y
when we know that z
is present. This will lead to more predictable code and less cryptic errors when invalid data infiltrates our application and shows up at unexpected places.
For now we will use the number 1 to represent all numbers Later on we will add wildcard patterns to be able to match on all numbers.
Those patterns are called record patterns and they are the first addition we to our pattern matching. Record patterns allow us to create patterns that describe the structure of an object and will match when the input data matches that structure. A record pattern itself is an object where the values are the patterns for their respective keys. Nesting will be fully supported to allow the description of very complex objects.
To implement this feature we will introduce a new type Pattern<a>
that will describe the valid patterns for a given type a
. For now the implementation is the same as the Partial
type of the standard library, but we will also expand this type later on. At last we update the match_pattern
function to support objects.
Record patterns are very useful for parsing untyped data from external sources, especially when combined with wildcard patterns. I will show some examples of this later on.
Type Inference
The next feature is all about the flow based type system of TypeScript. One of the really good things about TypeScript is that it narrows types down whenever a condition rules out possible values. We would like this to also happen with our pattern matching as well. Let’s define an Option monad to show this in a practical example:
We what to make sure that the variant with the pattern matching is not giving a type error, just like the if-statement. This happens because the compiler has no way of figuring out that the pattern implies that the option is a Some and does contain a value.
Implementing this will require a new definition of the with
function to incorporate the type inference. Luckily TypeScript comes with a powerful type system that provides the tools we need to solve challenges like this. We will be using the typeof
operator to get the exact type of the pattern that the user provided and use Extract
to narrow down the type of a
. The code looks as follows:
We introduced a new generic type p
that has to be a subset of Pattern<a>
. Now we can use this stricter subset of p
to narrow down a
. The typeof
operator is used to force TypeScript to inference the type of the provided pattern, as we want the smallest possible subset and not the full Pattern<a>
type. The entire quality of our type inference depends on how good we are in narrowing down p
! With those changes our example with option will have the correct types inferred as proven by this screenshot:
While this solution adds a lot of power and safety to our library when dealing with typed (discriminated) unions, there is one major problem with using the Extract
type. If the input type of our pattern is any
(such as values from an API call) there will not be any type inference and the input type will be mapped to `any` (or never
in some cases). This means that in its current state the library is not usable for parsing untyped data. The following screenshot highlights the problem:
This behavior can be explained when we look to the definition of Extract
. It is defined as a extends b ? a : never
. Because the type returns a
(in our case any
), we will always get any
back when any
goes in. The solution to this problem is to make a custom extract type that first checks if b
extends a
before it goes through the same logic as Extract
. This means that when a
is any
, b
(the pattern) will be returned. The formal name of this is Least Upper Bound:
With this new LeastUpperBound
type we have type inference that works on both typed and untyped data. Now we can match on exact values, branches of unions and on the structure of untyped data.
Wildcard Patterns
A common task when building applications in TypeScript is loading and parsing data from external sources like a REST API. Every somewhat experienced developer will know the pain of debugging parsing logic that doesn’t fully check all cases and is riddled with assumptions. Let’s define an example to make this a more practical argument:
The very observant readers will have noticed that there is one typo that will cause this code to always return an Error
with undefined
inside. But for most developer this can lead to a few grey hairs before they discover why the application always shows an error even though nothing seems to be wrong with their code. If we could define record patterns that support wildcards for the primitive types we should be able to avoid those issues by writing code like this and get a meaningful error when the parsing fails:
Wildcard patterns are patterns that try to match the input value with a specific type. This is useful when we want to process data that is of an union type (like string | number
) or is not typed at all (like a response from an API call). We will introduce a handful of new patterns for this feature: String
, Number
and Boolean
that will match their corresponding primitive types. We will also make sure that this feature properly integrates with the type inference.
The first step is to update the type Pattern<a>
to allow the patterns to be used. For example, if the input type is `number` we want to allow a match on both a number
and Number
. For this we use conditional types to map a
to Pattern<a>
:
This allows us to write a pattern like { Id: Number }
to match the id with any number. The next step is to implement the actual matching in the match_pattern
function:
One last thing to do is undoing the modifications we made to a
before we use the patterns to narrow down the input type. For this we need to map the constructor types to their instance types. In this way a match on String
will give you a string
in the result, like you would expect. We also have to add this type to the with
function:
With record and wildcard patterns in place our library has grown to a powerful tool for dealing with parsing of data.
Array Patterns
The last feature we will be adding are array patterns. Array patterns allow us to check if all items in an array match a pattern. The pattern for an array will be defined as an array with 1 item: the pattern that will be used for all items.
We will again start by updating our types and update the implementation later on. To create the type for the array pattern we will use the infer
keyword to get the inner type of the array. With this type we will define a singleton array with a pattern for the inner type. The InvertPattern
type will use the same features to revert this process and make sure we still infer the correct types in the expression.
Note: this uses circular type definitions that are only supported in the latest releases of TypeScript.
Finally we update the match_pattern
function to check if the pattern is an array and execute the matching:
A very practical use case for this feature is parsing the data for an overview:
Conclusion
In this article we have seen how we can use TypeScript’ extensive type system to add completely new features to the language. We have also seen that pattern matching allows us to write code that is more declarative than writing a lot of conditions. This more abstract way of thinking allows us to describe complex parsing logic with simple, short and type safe patterns.
The complete source code can be found here. The library is also published on NPM. This is somewhat more extensive version than is shown here, but I couldn’t include everything in this article without making it way to long. Additional features worth noting are negated patterns (with negated type inference) and support for when
.