{{ message }}

Instantly share code, notes, and snippets.

# tkersey/the-alegbra-of-typescript.md

Last active Jun 7, 2021
The Algebra of [Type,Script]

# Algebra

Symbols Operations Laws
0, 1, 2, x, y, z, ... +, –, x, ÷, ... 0 + x = x, ...

# Algebra

Symbols Operations Laws
Types (void, number, boolean, ...) Type constructors (Option, Either) ?

# Algebra

Symbols Operations Laws
Things Ways to make new things Rules the things follow

# `0`

``````type Void = never
``````

# `1`

``````type Unit = void
``````

# `2`

``````type Bool = False | True
``````

# `2`

``````type Bool = void | void
``````

# `3`

``````type Three = One | Two | Three
``````

# `+`

``````type Either<E, A> = Left<E> | Right<A>
``````

`E + A`

# `+`

How many values of type `Either<Bool, Three>` are there?

# `+`

`const values = [Left<False>, Left<True>, Right<One>, Right<Two>, Right<Three>]`

# Laws

`0 + X = X`

``````Either<Void,X> ≅ X
``````

`X + Y = Y + X`

``````Either<X,Y> ≅ Either<Y,X>
``````

# `×`

``````type Pair<F,S> = [F, S]
``````

`F × S`

# `×`

How many values of type `Pair<Bool, Three>` are there?

# `×`

`const values = [Pair<False,One>, Pair<False,Two>, Pair<False,Three>, Pair<True,One>, Pair<True,Two>, Pair<True,Three>]`

# Laws

`0 × X = 0`

``````Pair<Void,X> ≅ Void
``````

`1 × X = X`

``````Pair<Unit,X> ≅ X
``````

`X × Y ≅ Y × X`

``````Pair<X,Y> ≅ Pair<Y,X>
``````

# `R -> A`

``````interface Reader<R, A> {
(r: R): A
}
``````

`Aᴿ`

# `Aᴿ`

How many values of type `Boolᵀʰʳᵉᵉ` are there?

# `Aᴿ`

`Boolᵀʰʳᵉᵉ` `2³ = 8`

# Laws

`1ᴬ = 1`

``````A -> Unit ≅ Unit
``````

`A¹ = A`

``````Unit -> A ≅ A
``````

`(B × C)ᴬ = Bᴬ × Cᴬ`

``````A -> Pair<B,C> ≅ Pair<A -> B, A -> C>
``````

`Cᴮᴬ = (Cᴮ)ᴬ`

``````Pair<A,B> -> C ≅ A -> B -> C
``````

# Option

``````type Option<A> = None | Some<A>
``````

`1 + A`

# Lists

``````type List<X> = Nil | Cons<List<X>>
``````

# Lists

``````type List<X> = Nil | Cons<List<X>>
``````

`L(x) = 1 + x ∙ L(x)`

# Lists

``````type List<X> = Nil | Cons<List<X>>
``````

`L = 1 + x L`

# Lists

``````type List<X> = Nil | Cons<List<X>>
``````

`L = 1 + x L` `L = 1 + x (1 + x L)`

# Lists

``````type List<X> = Nil | Cons<List<X>>
``````

`L = 1 + x L` `L = 1 + x (1 + x L)` `L = 1 + x + x² (1 + x L)`

# Lists

``````type List<X> = Nil | Cons<List<X>>
``````

`L = 1 + x L` `L = 1 + x (1 + x L)` `L = 1 + x + x² (1 + x L)` `L = 1 + x + x² + x³ + x⁴ + ...`

# Magma

`A type with a (closed) binary operation`

# Magma

``````interface Magma<A> {
readonly concat: (x: A, y: A) => A
}
``````

`A × A -> A`

# Semigroup

`A magma where the operation is associative`

# Semigroup

``````interface Semigroup<A> extends Magma<A> {}
``````

`A × A -> A`

# Associativity

``````concat(x, concat(y, z)) = concat(concat(x, y), z)
``````

`A + (B + C) ≅ (A + B) + C` `A × (B × C) ≅ (A × B) × C` `A -> (B -> C) ≅ (A -> B) -> C`

# Monoid

`A semigroup with an identity element`

# Monoid

``````interface Monoid<A> extends Semigroup<A> {
}
``````

`A × A + A + 1 -> A`

# Identity

``````concat(x, empty) = concat(empty, x) = x
``````

`0 + X ≅ X` `1 × X ≅ X` `X -> X ≅ X`

# Monoid

``````const Sum: monoid<number> = {
empty: 0,
concat: (u: number, v: number) => u + v
}
``````
``````const Product: monoid<number> = {
empty: 1,
concat: (u: number, v: number) => u x v
}
``````