Unlock This Episode
Our Free plan includes 1 subscriber-only episode of your choice, plus weekly updates from our newsletter.
Introduction
We’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!
Subscribe to Point-Free
Access this episode, plus all past and future episodes when you become a subscriber.
Already a subscriber? Log in
Exercises
Define addition and multiplication on
NaturalNumber
:func +(_ lhs: NaturalNumber, _ rhs: NaturalNumber) -> NaturalNumber
func *(_ lhs: NaturalNumber, _ rhs: NaturalNumber) -> NaturalNumber
Implement the
exp
function onNaturalNumber
that takes a number to a power:exp(_ base: NaturalNumber, _ power: NaturalNumber) -> NaturalNumber
Conform
NaturalNumber
to theComparable
protocol.Implement
min
andmax
functions forNaturalNumber
.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? Writeto
andfrom
functions between those types showing how to travel back-and-forth between them.Conform
List
andNonEmptyList
to theExpressibleByArrayLiteral
protocol.Conform
List
to theCollection
protocol.Conform each implementation of
NonEmptyList
to theCollection
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>
andFix<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” ofList
. 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.