The Startup
Published in

The Startup

Pattern Matching in TypeScript with Record and Wildcard Patterns

Photo by Robert Anasch on Unsplash

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.

An example of pattern matching in F#

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.

The first sketch of the library

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.

An example of what using our library looks like

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:

Imperative style of validating a data structure

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.

How validating a data structure could look like with pattern matching

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.

Introducing the Pattern<a> type

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:

Extracting a value from an Option

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:

Type inference and pattern matching, a match made in heaven

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:

Type inference is like magic, except for it being real

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:

The parameter r is still of type any, as shown by the intellisense

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:

Least Upper Bound will make sure we always extract the most information from our patterns

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:

Example code for a blog page, like the one you are looking at now

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:

This will check all the properties and give an actual error when something is wrong

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>:

We use the built-in constructor functions as placeholders

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:

Note there is both a function and a type that is called typeof

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:

Keeping Pattern<a> and InvertPattern<a> in sync is very important when expanding this library

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.

The infer keyword is truly amazing when unboxing types

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:

For now we ignore empty arrays for the sake of keeping is simple

A very practical use case for this feature is parsing the data for an overview:

Here r does have the type of {Id: number, Title: string}[]

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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store