Video #9: Algebraic Data Types: Exponents

Episode: Video #9 Date: Mar 26, 2018 Access: Members Only 🔒 URL: https://www.pointfree.co/episodes/ep9-algebraic-data-types-exponents

Description

We continue our explorations into algebra and the Swift type system. We show that exponents correspond to functions in Swift, and that by using the properties of exponents we can better understand what makes some functions more complex than others.

Video

Cloudflare Stream video ID: 80561ec520e647f7dfed18bf46cc7055 Local file: video_9_algebraic-data-types-exponents.mp4 *(download with --video 9)*

Transcript

— 0:05

In the last episode on algebraic data types we started to get a glimpse of what it means to see algebraic structure in the Swift type system. We saw that forming structs corresponds to a kind of multiplication of the types inside the struct. Then we saw that forming enums corresponded to a kind of summation of all the types on the inside. And finally we used this intuition to figure how to properly model a datatype so that impossible states are not representable, and enforced by the compiler.

— 0:44

In this episode we are we are going to look at the next piece of algebra that is not captured by just plain sums and products: exponentiation. We will see that it helps build our intuition for how function arrows act with respect to other constructions, and even allow us to understand what makes a function more or less complicated. A correction

— 1:05

Before we get to that, we have a correction from our last episode on algebraic data types. At the end of the episode we showed that the callback for URLSession takes a data type that expands to the following: (Data + 1) * (URLResponse + 1) * (Error + 1) = Data * URLResponse * Error + Data * URLResponse + URLResponse * Error + Data * Error + Data + URLResponse + Error + 1 We refactored this into a much simpler form. URLResponse * Data + Error We identified either a URLResponse and Data , or an Error , as being the only valid possibilities, and everything else should never happen. The reasoning was that there are two cases: you get a response from the server, in which you get some Data , or you never get a response because the request couldn’t be sent, in which case you get an Error value.

— 1:56

However, one of our viewers, Ole Begemann , remarked that it’s possible to both get a response and no data if the connection is terminated after receiving the headers, say in a long download request. We looked up the docs to find out what Apple says and found this very loaded paragraph: Note If the request completes successfully, the data parameter of the completion handler block contains the resource data, and the error parameter is nil . If the request fails, the data parameter is nil and the error parameter contains information about the failure. If a response from the server is received, regardless of whether the request completes successfully or fails, the response parameter contains that information.

— 2:38

By deconstructing this logic it seems possible that response can be non- nil regardless of what comes back for data and error , but we can at least read that data and error are mutually exclusive. So instead the two summands of the above expression that we actually want are: (URLResponse + 1) * (Data + Error) = URLResponse * Data + URLResponse * Error + Data + Error So we’ve at least reduced the original 8 summands to just 4, although the Data case is a little troubling. Is it really possible to deliver Data without a URLResponse ? Maybe we only want to have: URLResponse * Data + URLResponse * Error + Error That seems reasonable, but the documentation doesn’t say so we can make that assumption. To be safe let’s only use the first one.

— 3:40

In types, what we’re looking at is this: (URLResponse?, Result<Data, Error>)

— 3:52

And if we want to handle each case exhaustively, it looks like this: switch (response, result) { case let (.some(response), .success(data)): case let (.some(response), .failed(error)): case let (.none, .success(data)): case let (.none, .failed(error)): }

— 4:05

The biggest takeaway from this correction reaffirms the fact that the API for dataTask is complicated and requires a careful reading of the documentation to understand what values are possible, and even then it seems we don’t have the full story. If instead we embraced a proper datatype for modeling the valid states so that invalid states are not representable we wouldn’t even need documentation. And it’s interesting that we could use algebra as a high level language for discussing this problem and diving more deeply into its intricacies.

— 4:45

OK, with that out of the way, back to our regularly scheduled programming… Exponents

— 4:50

There is an operation in algebra known as exponentiation. It can be viewed as a higher-order multiplication in that it lets us express very large products compactly.

— 5:01

Say for example you wanted to multiply 2 with itself 100 times. We can express this using an exponent. 2^100 Which we can think of as an abbreviation for this already-abbreviated multiplication: 2*2*2*...*2

— 5:15

We have a pow function at our disposal to try this out. pow(2, 100) // 1267650600228229401496703205376

— 5:25

The 2 is known as the base and the 100 is known as the exponent. Functions

— 5:30

We know how multiplication looks like in the type system, so what does exponentiation look like? What construction is at our disposal that allows us to do a kind of “higher order” construction with types.

— 5:40

Let’s consider a simple, concrete case. Given this enum of three cases: enum Three { case one, two, three } What would it mean to take Bool to the Three power? Bool^Three

— 6:02

How can we make sense of this? Well, we can expand out Three into a sum of 1 ’s: Bool^(1 + 1 + 1) Leveraging the properties of exponents, we can distribute it further: Bool^1 * Bool^1 * Bool^1

— 6:24

This multiplication has 3 terms, each one can be thought of as tagged by a value from Three . So, picking a value from this is equivalent to assigning Bool for each value in Three . This is precisely what a function does! (Three) -> Bool

— 6:56

This is how we will define exponentiation in types, it’s just functions! We can show an equivalence using the following notation. A^B = (B) -> A The function notation kind of flips things around: the base is the output of the function, while the exponent is the input. We’ll cover that soon.

— 7:21

We can even list out all the possible implementations of (Three) -> Bool , but it’s kinda cumbersome: func f1(_ x: Three) -> Bool { switch x { case .one: return true case .two: return true case .three: return true } } func f2(_ x: Three) -> Bool { switch x { case .one: return false case .two: return true case .three: return true } } func f3(_ x: Three) -> Bool { switch x { case .one: return true case .two: return false case .three: return true } } func f4(_ x: Three) -> Bool { switch x { case .one: return true case .two: return true case .three: return false } } func f5(_ x: Three) -> Bool { switch x { case .one: return false case .two: return false case .three: return true } } func f6(_ x: Three) -> Bool { switch x { case .one: return false case .two: return true case .three: return false } } func f7(_ x: Three) -> Bool { switch x { case .one: return true case .two: return false case .three: return false } } func f8(_ x: Three) -> Bool { switch x { case .one: return false case .two: return false case .three: return false } }

— 7:39

That’s a lot! It checks out, though, when we plug our numbers in: // 2^3 = 8 pow(2, 3) // 8

— 7:52

It’s important to mention that this correspondence only makes sense when talking about pure, side-effect free functions. These are the functions we are actually counting. The ones with side effects cannot be counted, because there are infinitely many of em! func foo1(_ x: Three) -> Bool { print("hello") return true } func foo2(_ x: Three) -> Bool { print("world") return false } func foo3(_ x: Three) -> Bool { URLSession.shared.dataTask( with: URL(string: "https://www.pointfree.co")! ) .resume() return true } Properties

— 8:37

What’s nice about having this dedicated notation is that we can now explore the properties of exponents and see how they translate to the function world. Property #1

— 8:58

For example, if the base of an exponent is also an exponent, we can just multiply the exponents: // (a^b)^c = a^(b * c)

— 9:14

Let’s test this out. let a = 2 let b = 3 let c = 4 pow(pow(a, b), c) == pow(a, b * c) // true This would have been difficult to see if we’d stuck with the notation of multiplication.

— 9:30

Let’s convert this to function arrows. We can first swap out the ^ for a backwards function arrow. // (a^b)^c = a^(b * c) // (a <- b) <- c = a <- b * c Then we can flip the arrow. // c -> (b -> a) = (b * c) -> a And finally, in the Swift type system: (C) -> (B) -> A = (B, C) -> A

— 10:12

This is saying that if you have a function that returns a function, it’s the same as a function that takes two arguments: they’re equivalent. And this is precisely what curry does! It bridges the world of two-argument functions to the world of functions of that returns a function.

— 10:38

We defined curry previously . func curry<A, B, C>(_ f: @escaping (A, B) -> C) -> (A) -> (B) -> C { return { a in { b in f(a, b) } } }

— 10:57

We should be able to come up with a function that goes the other way. Let’s call it uncurry . func uncurry<A, B, C>(_ f: @escaping (A) -> (B) -> C) -> (A, B) -> C { return { a, b in f(a)(b) } }

— 11:24

These functions are inverses of each other and establish the equivalence of the two function types, which means they an undo one another! For example: String.init(data:encoding:) // (Data, String.Encoding) -> String? curry(String.init(data:encoding:)) // (Data) -> (String.Encoding) -> String? uncurry(curry(String.init(data:encoding:))) // (Data, String.Encoding) -> String?

— 12:10

Amazing! It’s nice to see that the algebra of types dictates why function currying is a thing, and that it’s not something we just invented because we thought it was cool. Property #2

— 12:32

Another property is that anything to the 1st power leaves the base unchanged: // a^1 = a pow(a, 1) == a // true pow(b, 1) == b // true pow(c, 1) == c // true

— 12:49

What does that look like in types? Let’s translate the function, stepwise. // a^1 = a // a <- 1 = a // 1 -> a = a

— 13:10

Finally, in types. (Void) -> A = A

— 13:21

We can even define an explicit equivalence between these two types. First, a function from (Void) -> A to A . func to<A>(_ f: (Void) -> A) -> A { return f(()) } We get a little warning for using Void as an argument, but let’s persevere in the name of algebra.

— 13:58

Now let’s define a function that goes in the reverse direction func from<A>(_ a: A) -> (Void) -> A { return { _ in a } }

— 14:14

This is our old friend zurry , and a new friend, unzurry ! Since Void is equivalent to () , we can get back to that definition. func zurry<A>(_ f: () -> A) -> A { return f() } func unzurry<A>(_ a: A) -> () -> A { return { a } } Kinda interesting to see how we stumbled upon a fundamental property of exponents through our earlier need to enhance function composition. Property #3

— 14:57

Let’s look at another property of exponents. Anything to the 0th power is 1 : // a^0 = 1 pow(a, 0) == 1 // true pow(b, 0) == 1 // true pow(c, 0) == 1 // true What’s strange is that this even holds true when the base is zero: pow(0, 0) == 1 // true

— 15:29

This should feel reminiscent of the fact that the empty struct contains one value or the product of an empty array of integers is 1.

— 15:42

What does this look like in types? // a^0 = 1 // a <- 0 = 1 // 0 -> a = 1 (Never) -> A = Void

— 16:09

Very strange! This says that although Never is uninhabited, that is contains no values, the type of functions from Never to any other type is inhabited with precisely one function!

— 16:27

How on earth could that be? Well, to show the equivalence of these types we need to cook up functions going each way. First, from (Never) -> A to Void . func to<A>(_ f: (Never) -> A) -> Void { return () } The first one was really easy. We didn’t even need to know anything about f . The only thing we can do is return the a value in Void , which is easy enough. The other one however is strange. func from<A>(_ x: Void) -> (Never) -> A { <#???#> } How can we define the body of this function? Well, let’s take some steps and see what happens.

— 17:22

Well, we know we need to return a function (Never) -> A , so let’s just start with a stub of that: func from<A>(_ x: Void) -> (Never) -> A { return { never in <#???#> } }

— 17:32

Now we have this never value. We know it can never be inhabited and so this function can never be run, but that doesn’t mean we can’t define functions that work with values in Never , even if those values can’t exist! But how do we define this function?

— 17:47

Remember that Never is an enum. It has no cases, but it’s still an enum! And what do we usually do with enums? We switch over them! Let’s switch over never and see what comes next. func from<A>(_ x: Void) -> (Never) -> A { return { never in switch never { } } }

— 18:07

What the heck!? That compiles!? Is that really the implementation of this function?

— 18:20

It is! Recall that Swift has special knowledge when it comes to destructuring enums and return paths of functions.

— 18:51

For example, consider this function: func isInt(_ x: Either<Int, String>) -> Bool { switch x { case .left: return true case .right: return false } // No return needed here } A return was not needed outside the switch because Swift knows you handled all the cases. That is what is happening with switch never . Swift knows you handled all the cases, there just happens to be no cases!

— 19:26

Some languages even they give this function a name! They call it absurd . func absurd<A>(_ never: Never) -> A { switch never {} }

— 19:45

Absurd indeed! How could we possibly make use of this function?

— 19:51

The Result type has a common operation that takes two functions as input. One goes from the Value parameter to A , and the other goes from the Error parameter to A . It allows us to “fold” a Result of two types into a single type A . Let’s define it. extension Result { func fold<A>( ifSuccess: (Value) -> A, ifFailure: (Error) -> A ) -> A { switch self { case let .success(value): return ifSuccess(value) case let .failure(error): return ifFailure(error) } } }

— 20:27

How could we use this function? Let’s say we had a result that contains an integer value, or a string as an error message. let result: Result<Int, String> = .success(2)

— 20:51

What if we want to fold that result into a string, for example, to display to the user. result.fold( ifSuccess: { _ in "OK" }, ifFailure: { _ in "Something went wrong" } ) // "OK"

— 21:17

A nice thing about the Result type is we can plug Never into the error type parameter and get the concept of a result that cannot fail. let infallibleResult: Result<Int, Never> = .success(2) When we try to fold this value, we even see a familiar function in the autocomplete! infallibleResult.fold( ifSuccess: <# (Int) -> A #>, ifFailure: <# (Never) -> A #> ) On success, we can return a success message again, and on failure, the only thing we can plug in here is absurd ! infallibleResult.fold( ifSuccess: { _ in "OK" }, ifFailure: absurd )

— 21:58

Now we have a little helper function that we can use to plug into these situations, and it even has a fun little syntax that screams at us: this code path is absurd !

— 22:15

There’s one caveat to this. It only compiles in Xcode 9.3 and Swift 4.1. Prior to that this function crashes the compiler, but at some point it was fixed. The algebra of in-out

— 22:41

We can even provide algebraic interpretations of Swift-specific annotations that decorate functions. One we’ve already seen from the episode on side effects in which we showed that functions of the form (A) -> A are equivalent to functions (inout A) -> Void . (A) -> A = (inout A) -> Void We even defined these functions. func to<A>(_ f: @escaping (A) -> A) -> ((inout A) -> Void) { return { a in a = f(a) } } func from<A>(_ f: @escaping (inout A) -> Void) -> ((A) -> A) { return { a in var copy = a f(&copy) return copy } } Recognizing this allow us to move between two worlds: one where a function has an inout argument and the other which has a type appear on the left and right side of the function arrow.

— 23:31

For example we can take the function: (A, B) -> A And refactor it to: (inout A, B) -> Void This is a pretty nice intuition to build, as it allows us to make performance optimizations with Swift’s mutability system.

— 23:53

We can go the other direction with this function: (A, inout B) -> C By transforming it into: (A, B) -> (C, B)

— 24:18

This is a really high level transformation that can affect the performance of our everyday code. It’s nice that we can use algebra to wipe away the complexity. The algebra of throws

— 24:28

Another Swift annotation is throws , which marks a function as being capable of not returning a value at all, but “emitting” an error that must be explicitly caught.

— 24:42

For example, Data has an initializer that throws : Data.init(from:) // (Decoder) throws -> Data

— 24:55

Such functions are equivalent to augmenting the return type to accommodate for this: (A) throws -> B = (A) -> Result<B, Error> Let’s define a function that shows this equivalence. func to<A, B>(_ f: @escaping (A) throws -> B) -> (A) -> Result<B, Error> { return { a in do { return .success(try f(a)) } catch { return .failure(error) } } }

— 26:22

What about the inverse? func from<A, B>(_ f: @escaping (A) -> Result<B, Error>) -> (A) throws -> B { return { a in switch f(a) { case let .failure(error): throw error case let .right(b): return b } } }

— 27:13

Seeing equivalence in the abstract as to and from is nice, but it’s even nicer that we end up with functions that have names and uses, like curry and zurry ! Let’s name these functions unthrow and `throwing. func unthrow<A, B>(_ f: @escaping (A) throws -> B) -> (A) -> Result<B, Error> { return { a in do { return .success(try f(a)) } catch { return .failure(error) } } } func throwing<A, B>(_ f: @escaping (A) -> Result<B, Error>) -> (A) throws -> B { return { a in switch f(a) { case let .failure(error): throw error case let .right(b): return b } } }

— 27:45

And now we can take a throwing function, like our Data initializer, and convert between these two worlds freely: Data.init(from:) // (Decoder) throws -> Data unthrow(Data.init(from:)) // (Decoder) -> Either<Error, Data> throwing(unthrow(Data.init(from:))) // (Decoder) throws -> Data What’s the point?

— 28:07

So we’ve now interpreted functions algebraically, it’s just exponentiation. But that led us to defining that really weird function from Never to A , which still seems absurd, and then it led us to thinking of inout and throws algebraically, but what’s the point? How does that help us in everyday code?

— 28:35

Yeah it totally does! We’ve seen previously that understanding types form an algebraic perspective allow us to wipe away the complexity inherit in the domain and just focus on how the types are constructed. It helped us immensely with structs and enums, and now we get to do it with functions.

— 28:58

For example, here’s another property of exponents: // a^(b+c) = a^b * a^c pow(a, b + c) == pow(a, b) * pow(a, c) In words, taking something to the power of a sum is the product of the powers. That is, exponents distribute over addition but at the cost of switch + to *.

— 29:19

In the type world this corresponds to an equivalence between two types of functions. Let’s translate these properties to function signatures. // a^(b + c) == a^b * a^c // a <- (b + c) == (a <- b) * (a <- c) // (b + c) -> a == (b -> a) * (c -> a) (Either<B, C>) -> A == ((B) -> A, (C) -> A)

— 30:00

Here are the equivalence functions spelled out. We’ve left the bodies unimplemented as exercises. func to<A, B, C>(_ f: @escaping (Either<B, C>) -> A) -> ((B) -> A, (C) -> A) { fatalError("exercise for the viewer") } func from<A, B, C>(_ f: ((B) -> A, (C) -> A)) -> (Either<B, C>) -> A { fatalError("exercise for the viewer") }

— 30:31

This is telling us that a function that takes an Either is secretly really two functions in disguise: one that operates on the left value and one that operates on the right value. This means that augmenting the input of a function by adding enums cases does not really increase complexity that much because we can ultimately break it down into smaller units. And in fact the compiler enforces this for you, but adding cases means the switch inside your function is going to break, and the only way to appease the compiler is to handle those new cases.

— 31:10

There’s another similar property of exponents: // (a * b)^c = a^c * b^c pow(a * b, c) == pow(a, c) * pow(b, c) This is saying that a product to a power is the product of the powers.

— 31:28

In the type world this corresponds to: // (a * b)^c = a^c * b^c // (a * b) <- c = (a <- c) * (b <- c) // c -> (a * b) = (c -> a) * (c -> b) (C) -> (A, B) = ((C) -> A, (C) -> B)

— 31:57

These functions are equivalent, which means we should be able to define functions to prove it. func to<A, B, C>(_ f: @escaping (C) -> (A, B)) -> ((C) -> A, (C) -> B) { fatalError("exercise for the viewer") } func from<A, B, C>(_ f: ((C) -> A, (C) -> B)) -> (C) -> (A, B) { fatalError("exercise for the viewer") }

— 32:05

This is telling us that a function into a pair or tuple is the same as a pair of functions mapping into each side of the pair. This means that augmenting the return type of a function by adding additional fields also does not really increase the complexity of this function because you can again break it down into smaller understandable units. And in fact the compiler enforces this for you because you must consider those additional fields in order to construct a value to return!

— 33:01

Perhaps even more interesting, there are certain “non-properties” of exponents that can also be enlightening. For example, when people first learn of exponents and their properties they are sometimes mistaken to believe: // a^(b * c) = a^b * a^c pow(a, b * c) == pow(a, b) * pow(a, c) // false This is not true algebraically, and therefore not true in the types! The types say this: // a^(b * c) != a^b * a^c // a <- (b * c) != (a <- b) * (a <- c) // (b * c) -> a != (b -> a) * (c -> a) (B, C) -> A != ((B) -> A, (C) -> A)

— 34:38

So, a function from a pair does not further simplify in anyway. This means augmenting the input of a function by adding fields does lead to a more complex function in that there is more data sitting there that you must deal with, but nothing is forcing you to do anything with it and there is no natural way of carving it into smaller pieces.

— 35:26

Another non-property that may seem reasonable at first but is in fact wrong: // (a + b)^c != a^c + b^c pow(a + b, c) != pow(a, c) + pow(b, c)

— 35:55

This means the following types are also not equivalent: // (a + b)^c != a^c + b^c // (a + b) <- c != (a <- c) + (b <- c) // c -> (a + b) != (c -> a) + (c -> b) (C) -> Either<A, B> != Either<(C) -> A, (C) -> B> So a function into an either does not further simplify in anyway. This means augmenting the output of a function by adding cases leads to a more complex function in that there more cases to consider but nothing is forcing you to consider those cases, and there is not natural way to break it down into smaller units. In particular, this shows why functions that return a Result type or throws are naturally more complex than other functions, and it’s specially because they are of the form (A) -> Result<B, E> , which algebraically is (B + E)^A , which does not simplify anymore. That’s powerful!

— 37:31

Here we’ve seen that not only do the properties of exponents help us, but the non-properties of exponents help us as well! If we didn’t know the algebra and those properties, how would we even know to check for such non-properties!? By considering the algebra, it forces us to think about functions at such a high level that we can see where the complexity comes from by just looking at their types.

— 38:02

There’s more algebra to come! We’ll explore the algebra of generic types and recursive data types in a future episode. Stay tuned! Downloads Sample code 0009-algebraic-data-types-pt-2 Point-Free A hub for advanced Swift programming. Brought to you by Brandon Williams and Stephen Celis . Content Become a member The Point-Free Way Beta previews Gifts Videos Collections Free clips Blog More About Us Community Slack Mastodon Twitter BlueSky GitHub Contact Us Privacy Policy © 2026 Point-Free, Inc. All rights are reserved for the videos and transcripts on this site. All other content is licensed under CC BY-NC-SA 4.0 , and the underlying source code to run this site is licensed under the MIT License .