Javier Casas

A random walk through computer science

Type Families in Typescript

One of these things you eventually learn in Haskell is (Indexed) Type Families. The basic concept of a Type Family is the idea that you can have functions at the type level, I/E a function that accepts a type as parameter, and returns a type as a result.

-- Totally not valid Haskell, but this is the idea
g :: Type -> Type
g Int = Bool
g _ = Char

In the example above, if we call g String, we would get the type Char as a result. Even though we would really want to do this directly (the Dependent Haskell guys are working on it), there is a specific syntax and bunch of extensions to be able to do:

type family G a where
  G Int = Bool
  G a   = Char

This does pretty much the same, except that it's not actually a function, but a type. You write:

myVariable :: G Int  -- this is Bool
myVariable = True

But, with this, we have the basics of type-level functions. We write a function G which accepts a type as parameter, and returns another type as result. And we implement this type-level function by enumerating the different cases in pattern-matching fashion.

Well, you can do this in Typescript too!

Conditional types in Typescript

On Typescript 2.8, the team introduced Conditional Types, with the syntax:

T extends U ? X : Y

The idea is that if T is assignable to U (T is U or a subtype of U), then the resulting type will be X, otherwise Y. This is all we need to construct type families: a type-level if. If this is not clear enough for you, let's work out the magic:

Deconstructing pattern matching

Pattern matching is a powerful set of syntactic sugar that allows you to write very little code to mean a lot. It is intended to implement deep testing of the structure and values of a given data, and it does it by trying to match the data with potential candidates:

case value of
  Just [x1, 5, x3] -> do_something
  Just (x:xs) -> do_something_else
  Just _ -> do_this_instead
  Nothing -> do_a_different_thing

The code above is very obvious on what it does, but it's also very deep. Let's go over the details:

The first branch states if value is a Just, and that Just contains a list of exactly three elements, and the second element is 5, then go and name the first element x1 and the third element x3, and call do_something.

The second branch states if we haven't matched the first branch, and value is a Just, and that Just contains a list with at least an element, then go and name the first element of the list x, and the rest of the list xs, and call do_something_else.

The third branch states if we haven't matched neither the first or the second branch, and value is a Just, then call do_this_instead.

The fourth branch states if we haven't matched neither the first, or the second, or the third branch, and value is a Nothing, then call do_a_different_thing.

All of this in this small case statement. But this tells us how can we reconstruct our case statement into plain old conditionals. We try to match on the pattern by constructing a condition that represents the pattern, and assigning bindings to the variables that have been bound by the pattern match:

const value: null | Array<number> = ...
if(value !== null && value.length === 3 && value[1] === 5) {
  // branch for Just [x1:5:x3]
  const x1 = value[0];
  const x3 = value[2];
  do_something()
} else if (value !== null && value.length > 0) {
  // branch for Just (x:xs)
  const x = value[0];
  const xs = value.slice(1);
  do_something_else()
} else if (value !== null) {
  // branch for Just _
  do_this_instead()
} else if (value === null) {
  // branch for Nothing
  do_a_different_thing()
}

As you can see, the TypeScript version is significantly more verbose, but that doesn't stop us from using the same principle to construct pattern matching wherever we need.

Type-level pattern matching in Typescript: constructing Type Families

Now that we know how to construct conditional types, and how to transform pattern matching into a bunch of conditionals, we are in a position to construct Type Families. Let's go back to our previous example:

type family G a where
  G Int = Bool
  G a   = Char

So if a is an Int, the resulting type is a Bool, otherwise, the resulting type is a Char. Let's do this in Typescript:

type G<A> = A extends number ? boolean : string;

I had to substitute number for Int and string for Char because Typescript doesn't have these types, but you get the general idea: for each branch in the Type Family, construct a nested conditional type, like:

type G<A> = A extends Type1 ? Result1 :
            A extends Type2 ? Result2 :
            ...
            A extends Typen ? Resultn :
            Otherwise;

Wherever we need a type wildcard, we can substitute with A extends any that will match every type, and if we need to check multiple type variables, we can nest conditionals, although this tends to get hairy sooner than later.

Conclusion

With this, we have one of the most important elements of type-level computation: the type-level function. Brace yourselves for type-level Turing-completeness abuses!

Back to index