The Summer 2017 Mathematics A To Z: Functor


Gaurish gives me another topic for today. I’m now no longer sure whether Gaurish hopes me to become a topology blogger or a category theory blogger. I have the last laugh, though. I’ve wanted to get better-versed in both fields and there’s nothing like explaining something to learn about it.

Summer 2017 Mathematics A to Z, featuring a coati (it's kind of the Latin American raccoon) looking over alphabet blocks, with a lot of equations in the background.
Art courtesy of Thomas K Dye, creator of the web comic Newshounds. He has a Patreon for those able to support his work. He’s also open for commissions, starting from US$10.

Functor.

So, category theory. It’s a foundational field. It talks about stuff that’s terribly abstract. This means it’s powerful, but it can be hard to think of interesting examples. I’ll try, though.

It starts with categories. These have three parts. The first part is a set of things. (There always is.) The second part is a collection of matches between pairs of things in the set. They’re called morphisms. The third part is a rule that lets us combine two morphisms into a new, third one. That is. Suppose ‘a’, ‘b’, and ‘c’ are things in the set. Then there’s a morphism that matches a \rightarrow b , and a morphism that matches b \rightarrow c . And we can combine them into another morphism that matches a \rightarrow c . So we have a set of things, and a set of things we can do with those things. And the set of things we can do is itself a group.

This describes a lot of stuff. Group theory fits seamlessly into this description. Most of what we do with numbers is a kind of group theory. Vector spaces do too. Most of what we do with analysis has vector spaces underneath it. Topology does too. Most of what we do with geometry is an expression of topology. So you see why category theory is so foundational.

Functors enter our picture when we have two categories. Or more. They’re about the ways we can match up categories. But let’s start with two categories. One of them I’ll name ‘C’, and the other, ‘D’. A functor has to match everything that’s in the set of ‘C’ to something that’s in the set of ‘D’.

And it does more. It has to match every morphism between things in ‘C’ to some other morphism, between corresponding things in ‘D’. It’s got to do it in a way that satisfies that combining, too. That is, suppose that ‘f’ and ‘g’ are morphisms for ‘C’. And that ‘f’ and ‘g’ combine to make ‘h’. Then, the functor has to match ‘f’ and ‘g’ and ‘h’ to some morphisms for ‘D’. The combination of whatever ‘f’ matches to and whatever ‘g’ matches to has to be whatever ‘h’ matches to.

This might sound to you like a homomorphism. If it does, I admire your memory or mathematical prowess. Functors are about matching one thing to another in a way that preserves structure. Structure is the way that sets of things can interact. We naturally look for stuff made up of different things that have the same structure. Yes, functors are themselves a category. That is, you can make a brand-new category whose set of things are the functors between two other categories. This is a good spot to pause while the dizziness passes.

There are two kingdoms of functor. You tell them apart by what they do with the morphisms. Here again I’m going to need my categories ‘C’ and ‘D’. I need a morphism for ‘C’. I’ll call that ‘f’. ‘f’ has to match something in the set of ‘C’ to something in the set of ‘C’. Let me call the first something ‘a’, and the second something ‘b’. That’s all right so far? Thank you.

Let me call my functor ‘F’. ‘F’ matches all the elements in ‘C’ to elements in ‘D’. And it matches all the morphisms on the elements in ‘C’ to morphisms on the elmenets in ‘D’. So if I write ‘F(a)’, what I mean is look at the element ‘a’ in the set for ‘C’. Then look at what element in the set for ‘D’ the functor matches with ‘a’. If I write ‘F(b)’, what I mean is look at the element ‘b’ in the set for ‘C’. Then pick out whatever element in the set for ‘D’ gets matched to ‘b’. If I write ‘F(f)’, what I mean is to look at the morphism ‘f’ between elements in ‘C’. Then pick out whatever morphism between elements in ‘D’ that that gets matched with.

Here’s where I’m going with this. Suppose my morphism ‘f’ matches ‘a’ to ‘b’. Does the functor of that morphism, ‘F(f)’, match ‘F(a)’ to ‘F(b)’? Of course, you say, what else could it do? And the answer is: why couldn’t it match ‘F(b)’ to ‘F(a)’?

No, it doesn’t break everything. Not if you’re consistent about swapping the order of the matchings. The normal everyday order, the one you’d thought couldn’t have an alternative, is a “covariant functor”. The crosswise order, this second thought, is a “contravariant functor”. Covariant and contravariant are distinctions that weave through much of mathematics. They particularly appear through tensors and the geometry they imply. In that introduction they tend to be difficult, even mean, creations, since in regular old Euclidean space they don’t mean anything different. They’re different for non-Euclidean spaces, and that’s important and valuable. The covariant versus contravariant difference is easier to grasp here.

Functors work their way into computer science. The avenue here is in functional programming. That’s a method of programming in which instead of the normal long list of commands, you write a single line of code that holds like fourteen “->” symbols that makes the computer stop and catch fire when it encounters a bug. The advantage is that when you have the code debugged it’s quite speedy and memory-efficient. The disadvantage is if you have to alter the function later, it’s easiest to throw everything out and start from scratch, beginning from vacuum-tube-based computing machines. But it works well while it does. You just have to get the hang of it.

Advertisements

Author: Joseph Nebus

I was born 198 years to the day after Johnny Appleseed. The differences between us do not end there.

10 thoughts on “The Summer 2017 Mathematics A To Z: Functor”

  1. Can you suggest a nice introductory book on category theory for beginners? What I understand is that they generalize the notions defined concretely in algebra (which were motivated by arithmetic), but I lack any concrete understanding.

    Liked by 1 person

  2. “Categories for the Working Mathematician” by Mac Lane is good and foundational (recommended for serious readers). Another book “Cakes, Custard and Category Theory” by Eugenia Cheng is accessible even to laymen.

    Like

  3. May I ask a computer science question ;-) ? I tried to understand how this functor from category theory would be mapped onto (Ha – another level of mapping!! ;-)) a functor in C++ but was not very successful. In this discussion https://stackoverflow.com/questions/356950/c-functors-and-their-uses somebody says that a functor in category theory ‘has nothing to do with the C++ concept of functor’.

    Would you agree? Or if not, can you maybe explain how an ‘implementation’ of your functor example would look like in C++ (or some pseudo-code in some language…). Or keep that in mind for a future post if you ever want to return to that subject!

    Anyway: I really enjoy this series!!

    Like

    1. Hoo, boy, that’s a good question. I’m afraid I don’t have proper computer science training; what I do know is what I’ve picked up trying to do specific problems. In my defense, many of them lately have been database-related stuff that can benefit from these tools. Any time I need to impress the boss, I do a crash course of reading Stack Overflow for a couple weeks and rewrite some core bit of code until it breaks differently. But I will try, with the warning that I am speaking outside my actual proper training.

      To me, I see a reasonably straightforward connection between category-theory functors and C++ functors. We can look at functors as ways to match unary functions to other unary functions. This seems to me a good bit of what we’d do with C++ functors, describing ways to manipulate data without needing to know much about what the data is. If I may offer a counterbalancing Stack Overflow thread, https://stackoverflow.com/questions/2030863/in-functional-programming-what-is-a-functor has several people who seem to know what they’re talking about arguing in favor of programming-functors being enough like category-theory-functors to be enlightening.

      My understanding is that the functors of programming language Haskell are more obviously category-theory functors. But I haven’t done anything in Haskell, so I can’t say what is particularly good about doing this.

      Liked by 1 person

      1. Thanks, that was very helpful! Reading this discussion on Stack Overflow reminded me of Lisp – and then I googled for Lisp + Functors … https://en.wikipedia.org/wiki/Function_object#In_Lisp_and_Scheme – think I got it now: Quote from Wikipedia: “Many uses of functors in languages like C++ are simply emulations of the missing closure constructor. Since the programmer cannot directly construct a closure, they must define a class that has all of the necessary state variables, and also a member function.”
        It’s funny that the concept of closure feels rather natural in Lisp – not that complicated, or at least less complicated than the explanations of Functor sound…

        Like

Please Write Something Good

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s