Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

The Algebra of Swift Types


Algebra

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

Algebra

Symbols Operations Laws
Types (Void, Int, Bool, ...) Type constructors (Optional, Either) ?

Algebra

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

Zero


0

enum Never {}

One


1

enum Unit {} # as type
let unit: Void = () # as value

Two


2

enum Bool {
  case true
  case false
}

2

enum Two {
  case one
  case two
}

Three


3

enum Three {
  case one
  case two
  case three
}

Addition


+

enum Either<L, R> {
  case left(L)
  case right(R)
}

L + R


+

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


+

# Either<Bool, Three>
.left(.false)
.left(.true)
.right(.one)
.right(.two),
.right(.three)

+ Laws


0 + X = X

Either<Never,X> ≅ X

X + Y = Y + X

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

Multiplication


×

(First, Second)

First × Second


×

struct Pair<First, Second> {
  let first: First
  let second: Second
}

×

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


×

# Pair<Bool, Three>
Pair(.false, .one)
Pair(.false, .two)
Pair(.false, .three)
Pair(.true, .one)
Pair(.true, .two)
Pair(.true, .three)

× Laws


0 × X = 0

Pair<Never,X> ≅ Never

1 × X = X

Pair<Unit,X> ≅ X

X × Y ≅ Y × X

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

Exponentiation


Aᴿ

struct Reader<R, A> {
  let run: (R) -> A
}

R -> A


Aᴿ

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


Aᴿ

Boolᵀʰʳᵉᵉ 2³ = 8


Aᴿ

# Set<(Three) -> Bool>
(false, false, false),
(false, false, true),
(false, true, true),
(false, true, false),
(true, true, true),
(true, true, false),
(true, false, false),
(true, false, true),

Aᴿ 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

Cᴮᴬ = (Cᴮ)ᴬ

(A,B) -> C ≅ A -> B -> C

Optional


Optional

struct Optional<A> {
  case none
  case some(A)
}

1 + A


Recursive Types


Lists


Lists

indirect enum List<A> {
  case empty
  case cons(A, List<A>)
}

List<A> = 1 + A × List<A>


Lists

List<A> = 1 + A × List<A>
List<A> - A × List<A> = 1

Lists

List<A> = 1 + A × List<A>
List<A> - A × List<A> = 1
List<A> × (1 - A) = 1

Lists

List<A> = 1 + A × List<A>
List<A> - A × List<A> = 1
List<A> × (1 - A) = 1
List<A> = 1 / (1 - A)

Lists

List<A> = 1 + A × List<A>
List<A> - A × List<A> = 1
List<A> × (1 - A) = 1
List<A> = 1 / (1 - A)

Lists

List<A> = 1 / (1 - A)
        = 1 + A + A×A + A×A×A + A×A×A×A + ...
        = 1 + A + A² + A³ + A⁴ + ...

Algebraic Structures


Magma


Magma

A type with a (closed) binary operation


Magma

protocol Magma {
  static func <> (lhs: Self, rhs: Self) -> Self
}

A × A -> A


Semigroup


Semigroup

A magma where the operation is associative


Semigroup

protocol Semigroup: Magma {}

A × A -> A


Laws


Associativity

a <> (b <> c) = (a <> b) <> c


---
# Monoid

---
# Monoid
`A semigroup with an identity element`

---
# Monoid

protocol Monoid: Semigroup { static var empty: Self { get } }


---
# Monoid
`A × A + 1 -> A`

---
# Laws

---
# Identity

a <> empty = empty <> a = a


---
# Monoid
---
# Sum

struct Sum<A: Numeric>: Monoid { let sum: A

init(_ sum: A) { self.sum = sum }

static func <> (lhs: Sum, rhs: Sum) -> Sum { self.init(lhs.sum + rhs.sum) }

static var empty: Sum { 0 } }


---
# Product

struct Product<A: Numeric>: Monoid { let product: A

init(_ product: A) { self.product = product }

static func <> (lhs: Product, rhs: Product) -> Product { self.init(lhs.product * rhs.product) }

static var empty: Product { 1 } }


---
# Endo(functor)

struct Endo { let call: (A) -> A

init(_ call: @escaping (A) -> A) { self.call = call }

static func <> (lhs: Endo, rhs: Endo) -> Endo { .init(lhs.call >>> rhs.call) }

static var empty: Endo { .init(id) } }

---

# Algebraic Structures
![](https://raw.githubusercontent.com/fantasyland/fantasy-land/master/figures/dependencies.png)

---
# [How abstract algebra solves data engineering](https://corecursive.com/050-sam-ritchie-portal-abstractions-2/)
> How the abstract algebra and probabilistic data structures help solve fast versus big data issues that many are struggling with.

---
# [algebradriven.design](https://algebradriven.design)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment