What the Functor is a Monad

on Aug 8 2016

You don’t need to learn Category Theory or deep mathematics to understand Swift, but a basic understanding of some fundamental principles can go a long way. In this session, we’ll look at some often-mentioned ideas that will help you visualize what is going on with functional programming in Swift.

Introduction (0:00)

The first day of college I remember two things about my math professor. It was a very hot day and he leaned against the board and he told us what was coming in class. When he came away from the board there was a big sweat stain, which we all watched evaporate over time. He told us about functions and got us ready for calculus, and this was the first thing that he wrote on the board. And I was in love. It was a new language. “For every X there exists a unique Y, such that,” and so on. This language, this club that I was being welcomed into, I felt special, much like I do now. We’re going to talk today about functors and monads and what. Not why, but what.

Calculus (1:24)

I’m going to start with examples from different areas of math and then we’ll get back to programming. You might remember back to calculus and you were taught that the definition of the derivative was something like this, look familiar?

Someone in class however, would always know and tell the rest of the class, you don’t have to do that limit stuff, there’s a shortcut. But no, the professor said, you have to use the definition of derivative and you have to expand it and cancel the X cubes and factor things out and let the H go to zero and get the thing that we knew we were going to get just by using this shortcut all along.

There was someone in the back of the room and they would look at this formula and say, we don’t need to know this formula, we just need to have this collection of shortcuts like the derivative of a constant times a function is the constant on the derivative. And the derivative of a sum is the sum of the derivatives. And the derivative of a difference is the difference of the derivatives.

No, that’s not right, but we were on such a roll. It felt so good for a while. And so we had to return to the definition of the derivative and we had to prove things by saying, if we take the derivative of a constant times the function, we see that we can factor out that C, and what we get is the constant times the derivative. It’s not just because there’s a shortcut. We’re able to prove it. The same thing with a sum. The derivative of a sum, we can go ahead and regroup it, and split our limit, because the limits work with sums. Now we have proved that the derivative of a sum is the sum of the derivatives.

Underneath it all is the fact that we’re working with functions from real numbers to real numbers. We’re using the properties of real numbers, and the real numbers are a field. You might remember from school that you were taught that these were the nine field properties. In our proofs of the derivatives we actually used these.

We’re using things that we’ve abstracted and we’ve thought about in our proofs, and this is something we do all the time in mathematics and in programming. We classify and we think, well if the real numbers are a field, what can I prove about the real numbers? What can I apply back to my special case because I’m working within this world? I can look at this derivative of a product and say, well, if it’s not the product of the derivatives, what is it? And oh, my gosh, I don’t want to do this, and so I leave it as an exercise.

Express different (4:30)

Now in addition to looking for similarities and generalities, one of the things that we do in different fields of mathematics as we try to “think different” is we look at different ways of expressing things. Instead of looking at the definition of the derivative, sometimes it’s helpful to look at Leibniz’s approach.

Leibniz said, instead of looking at the derivative that way, letting H go to zero, let’s instead look at differentials because sometimes just changing this notation, changing this way of looking at things is going to help us get more of a mental picture. I can take the differential of F times G, and it’s F plus a little change times G plus a little change, minus what you would get if you multiplied F times G.

Now that looks a lot like the definition of the derivative, but the algebra’s not so messy. But that’s not all. If you stay with this model, and you multiply it out, you’ll see that after we cancel this F and G we’re getting pieces that actually have meaning to us. If we take this, we can draw this picture of F times G, and say, what happens if we change F a little bit and G a little bit. We get something like this.

This differential of F and G is that region outside, but that corresponds to that. And G times a little change in F corresponds to that. And this thing that we thought was our answer, this change in F times this change in G, is actually the insignificant piece. It’s the piece that goes away as my change in F and change in G gets small.

This is the product rule that you learned and loved. By changing the way we expressed it, the model became clear to us. That’s something we do a lot in programming: we go from using different words to using different pictures.

Geometry (6:37)

You did this in high school geometry, except you hated it because you had to do proofs. When you had two triangles that were equivalent, you took advantage of the fact that you could say, well these sides are the same, and these are the same, and these are the same, and the same for the angles that I can build up correspondences there as well.

These triangles are equivalent and yet, my Swift value-typed friends, they are not the same object, right? They’re equal. We know we implement equal when we have value types, but those are two different triangles. Geometry was preparing you for Swift.

Like value types we have two different triangles, but they are somehow the same, they are somehow equal. We could say that these two triangles are somehow the same. We had a different word for this in geometry, we called them similar. But one of the things that’s really important to us in math and in programming is to say, different things are the same in different ways. Maybe they’re the same because they’re equivalent and maybe they’re the same because they’re similar.

We can generalize in different ways. Let’s leave math for a second and look at the Three-card Monte. Now, on many street corners you will see people play the Three-card Monte. It’s a game that consists of three cards. One of them is the queen. They flip the cards over and they shuffle them around, and they invite you to find the queen. You know not to play, yes?

When I was in Berlin I was watching on street corners as they played a similar game with little match boxes. In one match box was a little marble, and they would flip those around the same way they would flip around cards and invite people to find the little marble underneath. If you go to any baseball stadium, at some time during the game they’ll show on the big scoreboard three caps. They’ll show you that underneath one of them is a baseball, and they’ll move the caps around, and then they’ll show you which one the baseball is under.

Although these are very different, you could argue that they’re the same. They’re the same idea. But someone who’s very literal would say, well it’s not the same, one of them is a queen of hearts, and one is a marble, and one is a baseball. The idea is that they are the same enough. This is where we’re headed with functors. When is something the same enough?

It turns out they’re the same enough if we can imagine a mapping between them that preserves certain things. Maybe this is too abstract for you because you feel like you should be typing code. You could do this as an optional perhaps, and a baseball cap could have none or some, in which case it has a baseball. Now with our new emojis we can drag these guys in and have a mapping here that says, these are the same. Or we could look at our boxes and say, instead of mapping it with an optional, maybe it’s a bool where we say it’s true if it contains a marble and it’s false if there’s nothing underneath. We have a tuple of bools and that maps across.

The idea is we’re trying to capture the sameness in our map between these different worlds. And I don’t mean a map in terms of a Swift map, although I will, I just mean a map in terms of a relation between these things.

Topology (10:31)

So another math field that some of you may have looked at is topology. You may have looked and said, well, I know that there are the same number of points between negative pi over two and pi over two as there are in the whole real number line. And you go, the same number of points, you’re out of your mind. You’re panicked because the screen wasn’t ready. But, no, we have this map between them that takes X to the tangent of X and each point over here maps to a unique point over there. Nothing is missed.

You might say, huh, that’s not really topology, that sort of analysis. Topology would say, I could take this circle missing the North Pole and I could map it to this real number line. The way I’m going to map it is I’m going to draw a line from that North Pole though any point on the circle and it’s going to hit a point on the line. That works for every point on the circle and every point on the line. You pick a point and I can tell you the relationship between them. There’s this one to one correspondence between this circle missing the North Pole and the whole real number line.

This is where it gets pretty. Imagine the real number line and add one point and it’s the same as the circle. Or imagine the circle, take away this point, and we can stretch it into the whole line. We can just imagine mapping that North Pole to infinity. And now this whole circle maps to the reals together with infinity. You could say, but plus or minus infinity. And I say, stop it.

I have to decide what neighborhoods look like in topology, what nearby points look like. If I have this point on the circle, points nearby that point on the circle and points nearby that on the line correspond, well, what happens at infinity? What does the neighborhood of infinity look like? It looks like pushing out in both directions. There is no plus and there is no minus. There is just infinity.

We do this a lot in math within the disciplines. We look for these abstractions. We look for the commonality. We look for what’s the same. The big leap in mathematics many years ago was, what if we look for this in different disciplines instead of in the same discipline? What if we’ve got different disciplines, and problems are hard in one, and easy in another. Or maybe the language that we used in one helps us understand things in another. If we start with this area where there are really hard problems, and we find some area that we know about, and some map between them, something that says, I know how to abstract some amount of sameness between them, and now the solutions and truths from this world transfer over to solutions and truths in this world.

We think of that as these two things, C and D, and this map between them. For every point in C we can map over that point. For every object in C, capital F maps to some point in D. For every function in C that takes X to the Y, we can map that function over. Capital F maps over objects and it maps over what we call arrows. It just has to obey two little rules, and that is if you have the identity function in C. It maps over to the identity function in D. If you have composition, composition F of G composed with F is what happens when I map over G and compose it with what I get when I map over F. Now C and D we call categories, and F, my friends, is what mathematicians call a functor.

A functor (14:23)

A functor maps objects to objects and arrows to arrows. It just has to obey those small, little rules. Now we have an idea of what functors are in Swift, and the ones we always hear about are optionals and an array. Arrays are functors. Optionals are functors.

What gets lost here is, what’s the category for these functors? The functor is a map between categories. The category’s actually Swift itself. We’re mapping things in Swift to things in Swift.

As an example, let’s look at the optional. In the optional, I have to map over objects. I have to map over arrows. Let’s look at objects. I have this functor that maps something to the optional something, for instance it’s going to take a string and map it to a optional string,. In particular, if I give it alt as a string, pandering to the crowd, it’s going to map it over to an optional alt. It’s going to wrap it, it’s going to be the sum alt and an int.

For instance three, that’s not pandering to the crowd, gets mapped to an optional three, and so my functor has to map objects to objects, but it also has to map functions to functions. It has to map arrows to arrows if I have a function from T to U. For example, string to an int, string to the length of the string, then this functor has to map my F to a function from F(T) to F(U). In the case of optionals, F(T) is optional T, and F(U) is optional U, and so F(F) is what we call map.

The way a map works here is you think about switching on self and there’s only two cases for an optional. It’s either none or it’s some. If it’s some, then we bind to the actual value and because it’s an actual value, F maps from an actual T to an actual U. We can return what we get when we wrap up F(X) and if it’s none, we return nil again. It maps a nil to a nil and if it’s an actually value we unwrap it, we map it over, and we wrap it again.

That’s what map looks like for optional. For array, it’s very similar. We have objects and so we’re going to map objects to objects. We’re going to map T to an array of type T. For instance, I’m going to map an int to an array of ints and so F(3) is just the array with a single element three in it.

I also have to map functions. I have to map my arrows over. So I have a function from T to U, it’s an array of T’s to an array of U’s, and this is again what we call map in Swift. I created an empty array in my target type and I go through every element in my starting array, and for each element I map it over. I append it to my target array and then that’s what I return.

In each case, an optional knows how to get inside of itself and an array knows how to get inside of itself. I’m unwrapping, mapping over, and then I’m rewrapping it. That’s the process that we go through. We have a function from T to U, map of F goes from F(T) to F(U) and all map does is it unwraps, it applies F, and it rewraps it.

Let’s go back to optionals. What if the function F itself is an optional? Imagine that I have a text entry page and I’m going to get to that text entry page from many different places in my work flow. What the save button does is different depending on how I get there. I’m going to pass the behavior forward as a closure. We did this in a objective C with blocks. We do this in Swift all the time but what’s really nice in Swift is we can make the save action be an optional.

What if someone forgot to pass it to us? My save action itself is an optional that takes whatever string people enter and does something. The entered text is an optional because maybe they didn’t enter anything. Maybe there’s a save or maybe there isn’t. Maybe there’s text or maybe there isn’t. In the case that you have given me the function and there is entered text that I know what to do, and if there isn’t a function, or there isn’t text, or both, then I just return null. Guard let is our friend. We see if there is a save, and if there is, we unwrap it where save is the function. If there’s entered text, where that’s our optional string, we unwrap. Otherwise our return should be returned nil. If there is something, I return save of my entered text.

Another way of writing this that you’ll see sometimes is save with this funky symbol and entered text from people who like to define custom operators. You’ll also see this called apply. This is common terminology from other languages and this is what is meant by an applicative functor. An applicative functor is when both the function and the thing it operates on are both wrapped. If I can unwrap both of them, then I apply it. If I can’t, then I go have lunch.

Now this is much less likely, but in an array it wouldn’t be an optional function. It would be an array of functions and I would be applying an array of functions to an array of input. The way I would do it is the same way we did it before. If we can get inside that array of functions, do it. If we can get inside that thing that we’re applying to, do it. Create our target empty, iterate through our functions, and inside of that loop iterate through all our elements. Build up our inner array for each function and each element apply it and return that. That’s just delightful.

Think of a table view where you’re going to do the same thing to each element of the table view, or collection view. When I have a function and my function itself is optional or my functions really an array of functions, all I’m saying is my function itself is wrapped. The thing I’m applying it to is wrapped and what I get when I used this, apply instead of map, is something that unwraps both F and T, applies F to T, and then rewraps the result. That’s the applicative functor.

But there’s more. What if instead of F being a map from to T to U, or F being a wrapped map from T to U, what if F takes a T and returns in the case of optionals? And optional U, or in the case of arrays, it takes a T and it returns an array of U’s? In other words, it takes a T and returns a wrapped version of U. I can’t use map because remember: map unwraps, applies F, and rewraps. In this case it would unwrap my optional T, apply F of that, and then get a U question mark and then rewrap that. In other words, I’d end up with wrapping it twice. I’d end up with a optional optional or I’d end up with an array of arrays.

That brings us to the world of monads. That brings us to the world of flatMap. flatMap says, if you’re in this world where you have a T and you end up with a wrap value of U then you can apply this to a wrap value T and get a singly wrapped value of U.

The way we do this using flatMap, which is sometimes called bind, is we unwrap our T and we apply our F. In the case of an optional this would be enough, but in the case of an array, I have this array of things and I applied and now I have unwrapped my array. I have this group of arrays sitting out there naked. I have to rewrap them in an array. Now I have an array of arrays. My last step is to unwrap the inner arrays.

Now you could imagine doing this with optionals too but the last two steps are unnecessary. This step is called join. Join is the essential thing of being a functor. It’s the ability to take this doubly-wrapped thing and get at that inner layer. That’s essential with other properties of being a monad. That’s the key to it all and it helps make flatMap work.

You use it already/Conclusion (25:13)

You use this all the time in Swift. Here’s a contrived example and then I’ll show you another one.

Imagine that I have an array of strings, odds and evens. I have a dictionary where odds is the first key for an array of ints one, three, five, and evens is the second key for an array two, four, six. If I don’t flatMap it, what I get when I ask a dictionary for a value for keys is an optional. Remember, if you ask in Swift, a dictionary gives me the value that corresponds to this key. It’s saying it could possibly be nil and I can’t guarantee there will be something, so it will be an optional.

This first flatMap gets rid of the optional. I get looking up in the dictionary and what I get is an array of arrays. The way you get rid of this inner array is you flatMap it again. Now let’s sort it because this is out of order. Now that I’ve sorted it, let’s double each element.

How do we know when to use flatMap and when to use map? The answer is what you are asking it to do. In the first case, I’m asking you to do something that returns a wrapped value. Remember when F maps from T to a wrap value of U, I have to balance it with a flatMap. In the last case, I’m not rewrapping it.

The idea here is to look for balance. We use this all the time. The fact that an array and an optional in Swift is not only a functor, but they are monads, allows us to do this balancing act. We even do it in a much nicer case which is optional chaining.

You’ve see where we have these examples where we chain a bunch of things and sometimes we use the question marks and sometimes we don’t. It’s the same question, do we use map or flatMap? When do we use the question marks and when don’t we? We use the question marks when they could return nil and we’re saying if it’s not nil, unwrap it and keep going. This is a place that you use monads all the time. It’s all about balance.

Believe it or not, this brings us back to calculus and our definition that F prime of X equals this because it turns out that’s an awful lot of assumptions here that we don’t pay attention to because we learned there was a shortcut. And implicit in this definition is F(X) has to exist. The function has to be defined at F, and not only that, the limit as I get close to X has to exist. Not only that but the limit as I get close to X has to equal F(X), and that’s what we mean by continuous. You might remember, I can’t even take a derivative if the function isn’t defined or isn’t continuous; and that derivative existing means that the limit from the left of us exists, and the limit from the right must exist, and they must be equal.

The point is, there’s an awful lot of assumptions that we have forgotten that we make and it’s the same when we use these things in Swift. We forget about all the things that we’re assuming along the way and we think, well, I know how to take the derivative of something. It turns out we do use this all the time in real life. Although, you don’t explicitly need to understand these things.

If you understand functor, applicative functor, and monad, it’s going to change the way you write code. You’re going to structure your code differently. You’re going to see context. You’re going to see how to set things up so that they do chain nicely. It’s going to inform your API design. It should remind you of something that you did when you were in object-oriented programming, and that is design patterns.

You didn’t have to know design patterns to write good object-oriented code, but it helped. It was the same role if you happen to know the visitor pattern or the state pattern or the template pattern. The more you knew, the more you could look at your code and say: this would be beneficial if I refactored it in this direction. Although you don’t need to know these things explicitly, they are going to help your code.