The Math of TypeScript's Types
Tags: typescript, functional, math
Published: 2021-10-02 23:24:47

I've been studying functional programming for a few years and in doing so I've learned a lot about types that I would not have otherwise. In particular, studying Haskell and related technology begets some interesting concepts. The one I want to talk about this time is "algebraic types".

From [wikipedia](https://en.wikipedia.org/wiki/Algebraic_data_type):
> In computer programming, especially functional programming and type theory, an algebraic data type is a kind of composite type, i.e., a type formed by combining other types.

If you've used TypeScript for a bit you've probably been exposed to some of these already.

## Sum Types

Let's say we have a short list of commands that an API will support, "list" and "pop". We can use string literal types to represent the valid values:

```ts
type ListCommand = 'list'
type PopCommand = 'pop'
```
Each of these types only have one value--the specific string that is valid. If we want a function that can take either command we can compose these types together using the `|` operator.

```ts
type ValidCommand = ListCommand | PopCommand

const performCommand = (command: ValidCommand) => 
```

The `|` type operator creates a sum type of the types to the left and right of it. What you should notice is that the sum adds the potential values together, i.e. ValidCommand accepts ListCommand plus PopCommand. This may be more apparent with bigger types:

```ts
type CommandOrFlags = ValidCommand | Flags
```

You'll remember that `Flags` had four valid values and `ValidCommand` has two. Thus `CommandOrFlags` has six (4 + 2).

So we can add types, can we multiply them too? Yes, indeed!

## Product Types

As you may have noticed, you can think of `|` operator for sum types as "or". Product types are the other half of that, the "and". So then we have to find data structures that represent a type having multiple values simultaneously. Tuple is a great candidate for that since it allows us to have different types at its indices.

```ts
type Flags = [boolean, boolean]
const flags: Flags = ?
```

How many potential values can be assigned to `flags`? 

With this small set we could list them out but we can use what we know about the individual types to figure it out with math.

The type `[boolean, boolean]` must have exactly two values and those values must be booleans. Booleans themselves have two potential values. If you know that tuples form a product type with the types they contain you just have to multiply `2 x 2` to know that the total inhabitants of the composed type is four.

Another way of encoding product types is to use an object:

```ts
type Point = {x: number; y: number}
```

So in a way you're already using them!

## Sum types are a monoid

Monoid is an interesting mathematical structure that is pretty simple. 

* **Composition**: Monoid is type with a combine operation that can join to values of the same monoid. `a o b = c` where `a` `b` and `c` are same type, and `o` is the operation.
* **Associativity**: The operation must be associative `(a o b) o c = a o (b o c)`
* **Unit**: operation must have a "unit" value that doesn't change the value it's composed with. `a o unit = unit o a = a`

As an example Arrays form a monoid where `concat` is the operation and `[]` is the unit:

```ts
// Composition
[1,2].concat([3,4])
// is same as
[1,2,3,4]

// Associativity
[1,2].concat([3,4]).concat([5,6)
// is the same as
[1,2].concat([3,4].concat([5,6]))

// Unit
[1,2].concat([])
// same as 
[].concat([1, 2])
// same as
[1, 2]
```

The thing I actually wanted to share is that types themselves form a monoid with `|` as the operation and `never` as the unit!

```ts
// Composition
type Foo = 1 | 2

// Associativity
type Bar = 1 | (2 | 3)
type Bar = (1 | 2) | 3

// Unit
type Baz = 1 | never
type Baz = never | 1
type Baz = 1
```

Mathematically there is also a monoid for product types but I haven't found a way to make it work in TypeScript.

## Getting more mileage out of sum types in TypeScript

In exploring usage of sum types you may run into some challenge in writing functions that use them:

```ts
type Error = string
type Message = string

type Response = Error | Message

const handleResponse = (resp: Response) => {
  // wait. How do I actually have different behavior
  // since both cases are strings at run-time???
}
```

A trick to make this work is to provide some extra data at runtime so that your code can discriminate between the members of the sum. This is called a discriminated union. 

```ts
type Error = {kind: 'Error'; message: string}
type Message = {kind: 'Message'; message: string}

type Response = Error | Message

const handleResponse = (resp: Response): string => {
  switch(resp.kind){
    case 'Error': {
      console.error(resp.message)
      return 'Fail'
    }
    case 'Message':
      return resp.message
  }
}
```

Switch is used here as poor man's pattern matching. TypeScript has good support for this technique and will make sure you have your cases covered if you leave off the default case.

You can even have empty types to union with states that have no other data:

```ts
type Error = {kind: 'Error'; message: string}
type Message = {kind: 'Message'; message: string}
type Pending = {kind: 'Pending'}

type Response = Error | Message | Pending

const handleResponse = (resp: Response): string => {
  switch (resp.kind) {
    case 'Error': {
      console.error(resp.message)
      return 'Fail'
    }
    case 'Message':
      return resp.message
  }
  // TS ERROR: Function lacks ending return statement and return type does not include 'undefined'.ts(2366)
}
```

Then to fix it you can just handle the case:

```ts
const handleResponse = (resp: Response): string => {
  switch (resp.kind) {
    case 'Error': {
      console.error(resp.message)
      return 'Fail'
    }
    case 'Message':
      return resp.message
    case 'Pending':
      return 'Pending'
  }
}
```

That's all for now. I hope this gives you new things to think about and you get a chance to use Sum types to better model your applications. 

Edit note: I'd like to give a special thanks to @Phantz for the extra knowledge they dropped in the comments!