What is a functor?

Functors are an operation that has a structure preserving property. But what is that? Are these things practical? Does it have anything to do with the real world? Of course! To be useful, it must derive from real-world things we see all around us. This one is an assembly line. How? That's what this episode is all about.

Transcript

Eric Normand: What is a functor? By the end of this episode, I hope that you have a good understanding of this very useful idea and how it relates to the real world.

My name is Eric Normand and I help people thrive with Functional Programming.

Functor is an interesting idea. It's a concept from category theory. It is used often in languages like Pascal and Scala where the communities do a lot of category theory stuff in their programs.

Let's go over what it is. Like some of the other algebraic ideas that we've gone over like associativity, monoid, communitivity, those kinds of things, this functor is about operations over a certain type that the operation has a structure-preserving property. We're going to go over what structure preserving means.

You'll often find that the operation is called map or F-map.

In Scala, the idea of functor is translated into mappable, I believe. It's a mappable interface, a mappable...What do they call them? Case class or something like that. I'm not a Scala person so don't take my word for that.

A good example that you're probably familiar with is mapping over a list. That is a functor. Map over a list is a functor. Now, what is that? What does that mean? Let's use a metaphor. It's a metaphor. It's not a metaphor, but let's call it metaphor for right now.

Imagine that you are the manager of a factory. In this factory, you have an assembly line. Just to make it concrete, you're making toy cars. In the car manufacturing process, there are steps that you have to follow in a certain order. You can lay out your assembly line to do those steps.

When you're doing factory management, you want to optimize the time it takes to make a car because the more cars you can make in a day, the cheaper they will be. You can service more customers.

You can start to play around with things. You see that there's a worker here on the one part of the assembly line, and they are adding the body of the car. There's a chassis, they add the body. Then they pass that to a person who adds the wheels.

Then they pass it to the next person. Maybe they pass it by hand, or there's a conveyor belt or something. Regardless, person A adds the body, then person B adds the wheels. Now, you could say, "Let's do an experiment. What if the same person adds the body and then the wheels?" You eliminate a person. You get rid of one person by combining these two jobs into one.

Now, the question is, you're doing this experiment to see if it's faster, if it's more efficient. It might be. It might not be.

It's a good assumption, but you're assuming that the car will still be made correctly. That this person who is adding a body and then the wheels is doing the same work as two people where the first person adds the body and the second person adds the wheels.

It's the same work. You're going to get the same car at the end. That is the structure-preserving property. That somebody doing two jobs in a row themselves is the same as two people doing the first job and the second job, respectively. That's all the structure-preserving property is.

Now, let's translate this into mapping over a list. Let's say you have a list of strings. You have two operations to do on these strings. The first is you have to trim the white space off the front and the back, so basically calling that trim. Then the second operation is to uppercase them, very straightforward.

You can write what we might call a pipeline. You take the list of strings then you map trim over that, and then you map uppercase over that. The string values will flow through two different operations. One is trim. The next one, uppercase.

I could say that's inefficient because you're making this intermediate list. The first map is making a totally new list, or array, or whatever it is in your language. It's making a totally new list, and then that list is just thrown away right away after it gets passed to the second map. You've made some waste.

Because of the structure-preserving property, you can do this — you can say, "Well, we're only going to do one map. We're going to make a new function for the map." You pass enough function to map. This function is going to do both trim and uppercase.

It's going to take that as the string. It's going to trim it, and then uppercase it, and then return it. You only run map one time. We also believe, just intuitively, that this is going to give us the same answer at the end with less waste. This is the structure preservation property.

More formally, I could say that map of F on map of G of some list is the same as map of F composed with G over the list. It's that function composition. We'll talk about that in another episode. That's basically what we do. We made a new function that does both operations. That's structure preservation right there. That's it. That's all it is.

You could also extend it and say there's the idea that if I map the identity over the identity function over a list, then I get that same list out. That's an important property. Basically what you're saying is I have some neutral operation that does nothing to it. It shouldn't change anything. This as a metaphor, I like to look at this like in a factory.

I can put my car or my partially built car on a conveyor belt. That conveyor belt does nothing to the car except move it. It does not change the car in any way. That is like a neutral step. I can add conveyor belts between any two workers as much as I want. As long as those conveyor belts don't damage the car or change the car in some way, I can just put conveyor belts between things.

That is part of the structure preservation. I said that it's kind of like a metaphor. It's not really a metaphor. This is the structure preservation property that just exists naturally in an assembly line.

That's why it works. That's one of the reasons why assembly lines are so powerful. You get the same car out at the end, and you can manipulate how the work gets done. How small tasks you're making.

I can give small tasks to all these people on the assembly line, or I can give bigger tasks to each person on the assembly line. As long as the tasks happens in the same order, I get the same answer. That's pretty cool.

This is what functional programmers find cool about the structure preservation property and functors.

Let's look at some other functors that you might not think of. We've got lists. Lists are functors because you can map, so map over list is functors. Now you might have, in your language, an idea of a maybe value or an optional value. That is also a functor. Even if you don't have the idea, you might have something very much like it.

I know in JavaScript, in Python, in Clojure, we've got this value that represents no value, so nil, or null, or nothing, or none. It has different names. You could squint and say, "Well, all values in these languages are actually optional." They could be null, right? It's well known that you get null-pointer exceptions and stuff if you don't treat it like it's optional, if you don't check.

You can write an operation that's like map. It's going to have this structure preservation property that takes the value. It does the check, is it null? If it is, it just returns null. If it's not, it calls a function on it. That's passed in.

Some function F, that gets called on it. It's going to have the same property, the same property that if I have a value and I map F on it. That's a special map. It's like a maybe map. It's going to call maybe-map with F on this value, and then I call maybe-map with G on that value. It's the same as composing them with a single maybe-map.

That's another common functor that you might have. Any collection could be a functor. In Clojure, we generally don't treat things like that. Like a set, we have map over a set, but it treats it like a sequence. It picks some order to traverse the set in and maps over it that way. Then it returns a sequence.

But you could have a map that's just for sets, that takes a set and returns a set. Now you got to make sure that whatever you do, preserve that structure-preserving property. One way you could lose the structure-preserving property is sets have this interesting thing that they get rid of duplicates.

If you have a bunch of strings and you trim them, you might lose some strings. The count will go down because now you have duplicates because you trimmed them. They're now equal. What does that do? That might lose that property, that structure preservation, but maybe not. It really depends on the operations and the values that you've got in those sets.

That's functor. It's an operation over a type. Usually, it's called a map. That's why in Scala, it's called mappable. Map over a list is a functor. This property, like most category theory properties, it does show up in the real world. This is what math is. It's descriptions of the real world.

Sometimes they get really abstract, but they all derive from things we experience in the world. That thing that is very common is factory work with an assembly line has this property of preserving the structure of the car, or let's say the structure of the work is preserved.

Even if you split the tasks up into smaller bits or you combine them together, you still have the same car being made in this assembly line.

That's all I have. If you would like to see video, audio, or text versions of this episode, you can go to lispcast.com/podcast. You can subscribe there. You can listen to other episodes.

You can find ways to contact me if you want to ask a question because I love answering questions on the podcast. I'd love to hear what do you think about this. If you're into this, give me feedback about the topics you want to listen to, the kinds of formats you want. It's all there.

I'll see you later. Or you'll see me, or one of those. You'll hear me. Whatever, see you later.