tkersey/algebra-of-swift-types.md

## algebra-of-swift-types.md

      
  Raw
  

              algebra-of-swift-types.md
            
          
    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)