A video series exploring functional programming and Swift.

This episode is for subscribers only. To access it, and all past and future episodes, become a subscriber today!

See subscription optionsorLog inSign up for our weekly newsletter to be notified of new episodes, and unlock access to any subscriber-only episode of your choosing!

Sign up for free episodeWe’ve now had two episodes dedicated to exploring the relationship between algebra and the Swift type system. Let’s do a quick recap:

In the first episode we showed that addition and multiplication that we all know from algebra have a very real and direct correspondence to enums and structs in Swift. Specifically, a struct is like the product of all the types inside, and an enum is like the sum of all the types inside. This had a very real world application in allowing us to refactor data types so that values that we know should not be possible to exist are provably unrepresentable by the compiler.

Then, in the second episode, we showed that exponentials that we all know from algebra, that is take `b`

to the `a`

power, directly corresponds to functions from a type `A`

into a type `B`

. This was amazing because we could then take all the properties we know about exponentials and transport them over to the world of types. This allowed us to understand how making small changes to the inputs and outputs of a function affect the overall complexity of the function.

Well, today we are exploring the next piece of bridging algebra to Swift types. We are going to explore how generics and recursive data types fit into algebra. Turns out, like most things we do on this show, there is a very beautiful interpretation of these things in the algebra world. And we get to use a whole body of knowledge from algebra in order to better understand the Swift type system.

Let’s get started by looking at generics!

👋 Hey there! Does this episode sound interesting? Well, then you may want to subscribe so that you get access to this episodes and more!

Define addition and multiplication on

`NaturalNumber`

:`func +(_ lhs: NaturalNumber, _ rhs: NaturalNumber) -> NaturalNumber`

`func *(_ lhs: NaturalNumber, _ rhs: NaturalNumber) -> NaturalNumber`

Implement the

`exp`

function on`NaturalNumber`

that takes a number to a power:`exp(_ base: NaturalNumber, _ power: NaturalNumber) -> NaturalNumber`

Conform

`NaturalNumber`

to the`Comparable`

protocol.Implement

`min`

and`max`

functions for`NaturalNumber`

.How could you implement

*all*integers (both positive and negative) as an algebraic data type? Define all of the above functions and conformances on that type.What familiar type is

`List<Void>`

equivalent to? Write`to`

and`from`

functions between those types showing how to travel back-and-forth between them.Conform

`List`

and`NonEmptyList`

to the`ExpressibleByArrayLiteral`

protocol.Conform

`List`

to the`Collection`

protocol.Conform each implementation of

`NonEmptyList`

to the`Collection`

protocol.Consider the type

`enum List<A, B> { cae empty; case cons(A, B) }`

. It’s kinda like list without recursion, where the recursive part has just been replaced with another generic. Now consider the strange type:`enum Fix<A> { case fix(ListF<A, Fix<A>>) }`

Construct a few values of this type. What other type does

`Fix`

seem to resemble?Construct an explicit mapping between the

`List<A>`

and`Fix<A>`

types by implementing:`func to<A>(_ list: List<A>) -> Fix<A>`

`func from<A>(_ fix: Fix<A>) -> List<A>`

The type

`Fix`

is known as the “fixed-point” of`List`

. It is more generic than just dealing with lists, but unfortunately Swift does not have the type feature (higher-kinded types) to allow us to express this.

Introduction

00:05

Generics as function

01:36

Recursion in data types

07:57

Recursion in data types with generics

15:45

What’s the point?

28:31