Building strongly typed vectors and matrices in TypeScript

Recently, I came across a problem where I had to generate primitive Pythagorean triples. Much to the wrath of several people, I’m gonna refer to them as PPT in this post. To solve the problem, I planned to use Berggren’s tree. While a lesser known method, it’s easy to deterministically generate exclusively primitive triples while also having an easy way to lazily generate and terminate.

Since it involves matrix multiplication, I thought it might be a good time to attempt some strongly typed matrices. Matrix multiplication AB is only defined for matrices A and B, when the number of columns of the matrix A is equal to the number of rows of matrix B. How cool would it be if we can let the types declare that clearly? Is that even possible in TypeScript?

Creating a strongly-typed vector

A vector is a fixed-length list of items of the same type

Why not use an array? Because arrays in JavaScript (and therefore in TypeScript) can be sparse, and have a dynamic length, whereas vectors are never sparse, and always have contiguous keys and fixed length. We can treat vectors as a special subset of arrays, so we can reuse the methods defined on arrays as and when needed. We can use a strongly-typed vector as a composable piece to build up to our strongly typed matrix. Let’s first create a few helper types to represent our vector.

Now that we can represent a tuple, we can use it to start representing vectors. We can also create a strict constraint that a vector will always have a static length. Since array sizes are dynamic, we need a way to allow conversion to a vector only when the size matches. That’s the first way to create a vector — attempting a conversion from an array:

This is useful, but not very handy. We need to allow people to quickly create vectors by hand, without having to create an array and then attempt a conversion and then do a null-check. Let’s add another helper:

Great! Now that we have the vec function, we are able to quickly create vectors of a fixed length without having to type it out or using as const which automatically adds a readonly attribute. Notice how our Unwrap<T> and Size<T> helpers come to help. Now that we have our strongly typed vectors, let’s try creating a strongly typed matrix.

Creating a strongly-typed matrix

It’s as simple as a vector of vectors, or is it?

A matrix is a 2D vector of numbers, with m rows, and n columns. There are a few special cases of matrices that we want to allow users to create, like a matrix of zeros, an identity matrix, and row and column vectors. Let’s attempt those:

Defining matrix transposition

Can we say a transpose swaps rows and columns?

Notice we haven’t written a way to create a column vector yet — that’s because we can write a transpose and get it for free. Let’s try that:

Notice how TypeScript understands that a transposed row is a column vector and doesn’t complain that they are different types. Remember we returned a row vector as the result of row ?

We’re scratching the surface of dependent types, where values are part of the type definitions. Here, the size of the vector is part of its type definition, and the size of the matrix is part of its type definition. This is included in Row and Column, and is used by transpose, expressing that it takes a Matrix<M, N> but returns a Matrix<N, M>. Which is how TypeScript understands, like us, that a column vector is just a transposed row vector. Neat!

Defining matrix multiplication

A matrix multiplication is only possible under a constraint

As I mentioned earlier, matrix multiplication AB is only defined for two matrices A and B if the number of columns of A is equal to the number of rows of B. AB and BA are not equal, in fact, they might not even have the same number of rows and columns! Let’s try defining that:

Notice how we communicate the constraint just using the types.

Generating PPTs

Oh, and I don’t mean power point presentations

Coming back to our problem, we have 3 matrices A, B, and C, each of which create a specific transform of the input PPT to create another unique PPT. The input PPT is in the form of a column vector. And we need to multiply that with these transforms. I wonder what we’ll get — but TypeScript should be able to tell us.

Before then, let’s look at the 3 matrices:

It looks like A and C are just matrix B, with a column multiplied by 1. Hmm, why don’t we support that operation? I leave the column multiplication as an exercise to the reader, as its sufficiently complex without being super annoying. As a hint, you can use elementary transforms. I’m gonna jump to where I ended up defining them.

Here’s a sample from my text editor:

Notice how the type of C is automatically inferred by TypeScript to be a matrix of 3 rows and 3 columns. Isn’t that really valuable? Let’s try the multiplication. Since our multiply function takes the array A last, let’s write our calling code:

Here’s my editor showing inferences by TypeScript on the types of `seed` and the result of our multiply call:

Since A is a 3x3 matrix, when it’s multiplied with our seed which is a 3x1 matrix, we get another 3x1 matrix back — another column vector, which is the next PPT. Notice that we used a type alias and TypeScript doesn’t reduce the Matrix<3, 1> into a Column<3>. This is because multiply is typed to return a Matrix<M, P>. But this information is still very useful!

Conclusion

All good things must come to an end

While solving a problem, we also dabbled a little with a tiny version of dependent types in TypeScript, and also ensured our matrix operations are better documented. We could’ve just used a 2D array, and not written a vector, and yet we created a strongly typed vector and well-defined matrix operations. All this to generate some PPTs.

Regardless of what problem we’re solving at the moment, there’s elegant ways to solve it, and useful abstractions to create and use.

Hopefully you’re able to appreciate strong types, and their use as documentation and tests a little bit more as a result of this post. Or maybe dependent types are interesting and you want to delve deeper. Or maybe this post got you interested in matrices again, or pythagorean triples, or even types, or TypeScript. Regardless, I hope you had as much fun reading this post as I had creating it.

Until next time!

If you liked things you see in this post and would like to make use of them, they are available on github at artfuldev/ts-vector and artfuldev/ts-matrix and also as npm packages. Feel free to contribute to these projects if you’d like. I just spun those up to back this post, so they’re in dire need of help!