Robby Pruzan 7/27/24

Types -> Sets

The TypeScript type system can be thought of as a purely functional language that operates over types. But what does it mean to operate over a type? For me, I find resolving types into the set of items it can construct very useful. This set would contain every real value that is assignable to that type.

Then TypeScript's core syntax is functionality to operate over items in any given set, just like how you might operate over a real set in a normal programming language.

Because TypeScript is a structural type system, as opposed to nominal, this "set" the type constructs can be more useful than the actual type definition itself (but not always).

If we think of each type as the set of literals- real values- it can construct, we could say a string is just the infinite set of every permutation of characters, or a number is the infinite set of every permutation of digits.

Once you start thinking about the type system as a proper functional programming language that is meant solely for processing sets, more advanced features can get a little easier.

This article will go through most of typescripts features through the lens of: types are the sets they can create and typescript is a functional programming language that operates on sets

Note I am not implying that sets and types are equivalent, they are not.

Breaking apart TypeScript primitives

Intersection (&)

Intersection (&) is a great example where this mental model helps you reason about the operation better. Given the following example

type Bar = { x: number };
type Baz = { y: number };
type Foo = Bar & Baz;

We are intersecting Bar and Baz. Your first though might be the intersection operation was applied the following way:

Where we identify the overlap between the 2 objects, and take that as a result. But... there is no overlap? The left hand side (LHS) solely has x, and the right hand side (RHS) solely has y, albeit both numbers. So why would the intersection result in a type where this is allowed:

let x: Foo = { x: 2, y: 2 };

An easier way to think about what is happening is to resolve the types Bar and Baz into the sets they construct, not what it looks like in text.

When we define a type of { y: number }, we can construct an infinite set of object literals that at least have the property y in them, where y is a number:

Note: Notice how I said "set of object types that at least have the property y in them". That's why properties other than y exist in some object types. If you had a variable that had type {y: number}, it wouldn't matter to you if the object had more properties than y inside of it, hence why TypeScript allows it.

Now that we know how to replace types with the sets they construct, intersections make a lot more sense:

Unions

Using the previous mental model we established, this is trivial, we just take the union of 2 sets to get our new set

type Foo = { x: number };
type Baz = { y: number };
type Bar = Foo | Baz;

Type Introspection

Because the TypeScript maintainers thought it would be convenient, they built primitives into the language to let us introspect these sets. For example, we can check if one set is the subset of another, and return a new set in the true/false case using the extends keywords.

type IntrospectFoo = number | null | string extends number
  ? "number | null | string constructs a set that is a subset of number"
  : "number | null | string constructs a set that is not a subset of number";

// IntrospectFoo = "number | null | string is not a subset of number"

Where we are checking if the LHS set of the extends keyword is a subset of the RHS set

This is quite powerful because we can arbitrarily nest these

type Foo = null
type IntrospectFoo = Foo extends number | null
  ? Foo extends null
    ? "Foo constructs a set that is a subset of null"
    : "Foo constructs a set that of number"
  : "Foo constructs a set that is not a subset of number | null";

// Result = "Foo constructs a set that is a subset of null"

But things get weird when we use type parameters and pass unions as type arguments. TypeScript makes the decision to perform the subset check for every member of the union individually when type parameters are used, as opposed to resolving the union to a constructed set first.

So, when slightly altering the previous example to use type parameters:

type IntrospectT<T> = T extends number | null
  ? T extends null
    ? "T constructs a set that is a subset of null"
    : "T constructs a set that of number"
  : "T constructs a set that is not a subset of number | null";
type Result = IntrospectT<number | string>;

Typescript will transform Result into:

type Result = IntrospectFoo<number> | IntrospectFoo<string>;

making Result resolve to:

"T constructs a set containing only number" | "T constructs a set with items not included in number | null";

Which is simply because this is more convenient for most operations. But, we can force TypeScript to not do this using tuple syntax

type IntrospectFoo<T> = [T] extends [number | null]
  ? T extends null
    ? "T constructs a set that is a subset of null"
    : "T constructs a set that of number"
  : "T constructs a set that is not a subset of number | null";
type Result = IntrospectFoo<number | string>;
// Result = "T constructs a set that is not a subset of number | null"

which is because we are no longer applying the conditional type on a union, we are applying it to a tuple which happens to have a union inside of it.

This edge case is important because it goes to show the mental model of always resolving types to the sets they construct immediately is not perfect.

Type mapping

In a normal programming language, you can iterate over a set (however that may be done in the language) to create a new set. For example, in python if you wanted to flatten a set of tuples, you may do the following:

nested_set = {(1,3,5,6),(1,2,3,8), (9,10,2,1)}
flattened_sed = {}
for tup in nested_set:
  for integer in tup:
    flattened_set.add(integer)

Our goal is to do this in TypeScript types. If we think of:

Array<number>

as the set of all permutations of arrays containing numbers:

We want to apply some transformation to select the numbers out of each item and place them in the set.

Instead of using imperative syntax, we can do this declaratively in typescript. For example:

type InsideArray<T> = T extends Array<infer R>
  ? R
  : "T is not a subset of Array<unknown>";
type TheNumberInside = InsideArray<Array<number>>;
// TheNumberInside = number

This statement does the following:

• Checks if T is a subset of the set Array<any> constructs (R does not exist yet, so we substitute it with any)
  • If it is, for each array in the set T constructs, place the items of every array into a new set called R'
    • Infer what type would construct R', and place that type inside R, where R is only available in the true branch
    • Return R as the final type
  • If it's not, provide an error message

Note This is not based on a spec of how infer is implemented, this is only a way to reason about how infer works with the mental model of sets

Visually we can describe this process as:

With this mental model, TypeScript using the word infer actually makes sense. It's automatically finding a type that would describe how to create the set we made- R`.

Type Transformation- mapped types

We just described how TypeScript allows us to check very precisely whether or not a set looks like something, and map them based on that. Though, it would be useful if we could be more expressive in what each item in a set, constructed by a type, looks like. If we can describe this set well, we can make whatever we want:

• SQL parser in TypeScript types
• GraphQL parser in TypeScript types

Mapped types are a good example of this, and have a very simple initial use, map over every item in the set to create an object type.

For example:

type OnlyBoolsAndNumbers = {
  [key: string]: boolean | number;
};

The last step would be done in our minds- mapping the object type back to a set

We can also map over a subset of strings:

type SetToMapOver = "string" | "bar";
type Foo = { [K in SetToMapOver]: K };

Here we map over the set ["string", "bar"] to create an object type => {string: "string", bar: "bar"} which then describes a set that can be constructed.

We can perform arbitrary type level computation on the key and value of the object type:

type SetToMapOver = "string" | "bar";
type FirstChacter<T> = T extends `${infer R}${infer _}` ? R : never;
type Foo = {
  [K in SetToMapOver as `IM A ${FirstChacter<K>}`]: FirstChacter<K>;
};

Note: never is the empty set- there exists no values in the set- so a value with type never can never be assigned anything

Now we mapped over the set ["string", "bar"] to create the new type =>

{["IM A s"]: "s", ["IM A b"]: "b"}

Repetitive logic

What if we wanted to perform some transformation to a set, but the transformation is quite difficult to represent. It needs to run its inner computation some arbitrary amount of times before moving to the next item. In a runtime programming language we would trivially reach for loops. But as TypeScript's type system is a functional language, we will reach for recursion

type FirstLetterUppercase<T extends string> =
  T extends `${infer R}${infer RestWord} ${infer RestSentence}`
    ? `${Uppercase<R>}${RestWord} ${FirstLetterUppercase<RestSentence>}` // recurssive call
    : T extends `${infer R}${infer RestWord}`
    ? `${Uppercase<R>}${RestWord}` // base case
    : never;
type UppercaseResult = FirstLetterUppercase<"upper case me">
// UppercaseResult = "Upper Case Me"

Now first... lol what. This may look insane, but it's really just dense code, it's not complicated. Lets write a TypeScript runtime version to expand what's happening:

const separateFirstWord = (t: string) => {
  const [firstWord, ...restWords] = t.split(" ");
  return [firstWord, restWords.join(" ")];
};
const firstLetterUppercase = (t: string): string => {
  if (t.length === 0) {
    // base case
    return "";
  }
  const [firstWord, restWords] = separateFirstWord(t);
  return `${firstWord[0].toUpperCase()}${firstWord.slice(1)} ${firstLetterUppercase(restWords)}`; // recursive call
};

We get the first word of the current sentence, upper case the words first letter, and then do the same for the rest of the words, concatenating them in the process.

Comparing the runtime example to the type level example:

• if statements to generate a base case are replaced with if subset checks (extends)
  • this looks a lot like an if statement because each of the sets made using infer (R, RestWord, RestSentence) only contain a single string literal
• splitting a sentence into the first word and the rest of the sentence, using destructuring, is replaced with infer mapping over 3 sets- ${infer R}${infer RestWord} ${infer RestSentence}
• function parameters are replaced with type parameters
• recursive function calls are replaced with recursive type instantiations

We have the ability to describe any computation using these abilities (the type system is turing complete).

Conclusion

If you are able to think of TypeScript as being a very expressive way to operate over sets, and using those sets to enforce strict compile time checks, you will most likely start to get more comfortable with advanced typescript features (if not already), allowing you catch more bugs early.

This mental model is not perfect, but it holds up pretty well even with some of TypeScript's most advanced features.