Symbols | Operations | Laws |
---|---|---|
0, 1, 2, x, y, z, ... | +, –, x, ÷, ... | 0 + x = x, ... |
Symbols | Operations | Laws |
---|---|---|
Types (void, number, boolean, ...) | Type constructors (Option, Either) | ? |
Symbols | Operations | Laws |
---|---|---|
Things | Ways to make new things | Rules the things follow |
type Void = never
type Unit = void
type Bool = False | True
type Bool = void | void
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>]
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>]
0 × X = 0
Pair<Void,X> ≅ Void
1 × X = X
Pair<Unit,X> ≅ X
X × Y ≅ Y × X
Pair<X,Y> ≅ Pair<Y,X>
interface Reader<R, A> {
(r: R): A
}
Aᴿ
How many values of type Boolᵀʰʳᵉᵉ
are there?
Boolᵀʰʳᵉᵉ
2³ = 8
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
type Option<A> = None | Some<A>
1 + A
type List<X> = Nil | Cons<List<X>>
type List<X> = Nil | Cons<List<X>>
L(x) = 1 + x ∙ L(x)
type List<X> = Nil | Cons<List<X>>
L = 1 + x L
type List<X> = Nil | Cons<List<X>>
L = 1 + x L
L = 1 + x (1 + x L)
type List<X> = Nil | Cons<List<X>>
L = 1 + x L
L = 1 + x (1 + x L)
L = 1 + x + x² (1 + x L)
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⁴ + ...
A type with a (closed) binary operation
interface Magma<A> {
readonly concat: (x: A, y: A) => A
}
A × A -> A
A magma where the operation is associative
interface Semigroup<A> extends Magma<A> {}
A × A -> A
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
A semigroup with an identity element
interface Monoid<A> extends Semigroup<A> {
readonly empty: A
}
A × A + A + 1 -> A
concat(x, empty) = concat(empty, x) = x
0 + X ≅ X
1 × X ≅ X
X -> X ≅ X
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
}