The Algebra of [Type,Script]

the-alegbra-of-typescript.md

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

Zero

0

type Void = never

One

1

type Unit = void

Two

2

type Bool = False | True

2

type Bool = void | void

Three

3

type Three = One | Two | Three

Addition

+

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>

Multiplication

×

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>

Exponentiation

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

Option

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

1 + A

Recursive Types

Lists

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⁴ + ...

Algebraic Structures

Magma

Magma

A type with a (closed) binary operation

Magma

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

A × A -> A

Semigroup

Semigroup

A magma where the operation is associative

Semigroup

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

A × A -> A

Laws

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

Monoid

A semigroup with an identity element

Monoid

interface Monoid<A> extends Semigroup<A> {
  readonly empty: A
}

A × A + A + 1 -> A

Laws

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
}

Algebraic Structures

algebradriven.design

fp-ts