Algebraic Data Types: Generics and Recursion

Episode #19 • Jun 11, 2018 • Subscriber-Only

Our third installment of algebraic data types explores how generics and recursive data types manifest themselves in algebra. This exploration allows us to construct a useful, precise type that can be useful in everyday programming.

Algebraic Data Types: Generics and Recursion
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

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!

This episode is for subscribers only.

Subscribe to Point-Free

Access this episode, plus all past and future episodes when you become a subscriber.

See plans and pricing

Already a subscriber? Log in

Exercises

  1. Define addition and multiplication on NaturalNumber:

    • func +(_ lhs: NaturalNumber, _ rhs: NaturalNumber) -> NaturalNumber
    • func *(_ lhs: NaturalNumber, _ rhs: NaturalNumber) -> NaturalNumber
  2. Implement the exp function on NaturalNumber that takes a number to a power:

    exp(_ base: NaturalNumber, _ power: NaturalNumber) -> NaturalNumber

  3. Conform NaturalNumber to the Comparable protocol.

  4. Implement min and max functions for NaturalNumber.

  5. 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.

  6. 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.

  7. Conform List and NonEmptyList to the ExpressibleByArrayLiteral protocol.

  8. Conform List to the Collection protocol.

  9. Conform each implementation of NonEmptyList to the Collection protocol.

  10. 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?

  11. 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.

Downloads