Lecture 38 - Chapter 3: Functors

John Baez · June 2018

Last time we saw a graph that could be used for designing databases:

This graph is not a database; it's just a kind of template for a database. Fong and Spivak call it a database schema. To create an actual database using this schema, you'd have to specify:

a set of employees
a set of departments
a set of strings (that is, strings of symbols)
a function mapping each employee to the department they work in
a function mapping each employee to their manager
a function mapping each department to its secretary
a function mapping each employee to their first name
a function mapping each department to its name.

You could do this using a table or spreadsheet, or some other way. See the start of Chapter 3 for more on this!

What does this have to do with category theory? A lot!

We've seen that this "database schema" is really a graph $G$. And we saw that from a graph we can get a category $\mathbf{Free}(G)$ called the "free category on $G$". This has nodes of the graph as objects and paths as morphisms.

So, our database schema gives a category $\mathbf{Free}(G)$. The objects in this category are things like $\textrm{Employee}$ and $\textrm{Department}$. The morphisms are things like $\textrm{WorksIn} : \textrm{Employee} \to \textrm{Department}$.

To get an actual database, we need to provide a set for each object of $\mathbf{Free}(G)$, and a function for each morphism of $\mathbf{Free}(G)$.

When we do this, we're providing some sort of map from the category $\mathbf{Free}(G)$ to the category $\textbf{Set}$. A map between categories is called a "functor": it sends objects to objects, and morphisms to morphisms... and it should also obey a few obvious rules, which I'll explain in a second.

But first, enjoy the beauty of this idea! A database schema is really a category, while an actual database is a functor from that category to $\textbf{Set}$. The database schema has "abstract" objects and morphisms like $\textrm{Employee}$ and $\textrm{WorksIn} : \textrm{Employee} \to \textrm{Department}$, while the functor makes these "concrete", turning them into actual sets and functions!

So what's a functor, exactly?

Definition. Given categories $\mathcal{C}$ and $\mathcal{D}$, a functor from $\mathcal{C}$ to $\mathcal{D}$, written $F: \mathcal{C} \to \mathcal{D} $, consists of:

A function sending objects of $\mathcal{C}$ to objects of $\mathcal{D}$. This is usually called $F$ as well, so we have $F: \mathrm{Ob}(\mathcal{C}) \to \mathrm{Ob}(\mathcal{D}) $.
For each pair of objects $x,y \in \mathrm{Ob}(\mathcal{C})$, a function sending each morphism $f: x \to y$ to a morphism $F(f) : F(x) \to F(y) $. As you can see, we're calling this function $F$ too! So, it's a function

$$ F: \mathcal{C}(x,y) \to \mathcal{D}(F(x),F(y)) .$$ Remember, $\mathcal{C}(x,y)$ is the set of morphisms from $x$ to $y$ in $\mathcal{C}$.

We demand that:

a) $F$ preserve composition: $F(g \circ f) = F(g) \circ F(f) $ whenever $f$ and $g$ are morphisms that can be composed in $\mathcal{C}$.

b) $F$ preserves identities: $F(1_x) = 1_{F(x)}$ whenever $x$ is an object of $\mathcal{C}$.

That's it!

It may freak you out that we're using $F$ to mean the functor, the function that describes what this functor does to objects, and all the functions that describe what $F$ does to morphisms. However, this turns out not to be a problem. It would be much worse to have separate notations for all these things. You should think of them all as a single package: $F$.

You may wonder about conditions a) and b). They seem to have shown up by magic. How do they arise in our study of databases?

Here's an example. Take $\mathcal{C} = \mathbf{Free}(G)$ and look at the morphisms $\textrm{WorksIn} : \textrm{Employee} \to \textrm{Department}$ and $\textrm{DepartmentName} : \textrm{Department} \to \textrm{String}$. Then choose a functor $F : \mathcal{C} \to \mathbf{Set}$. We must have

$$ F(\textrm{DepartmentName} \circ \textrm{WorksIn}) = F(\textrm{DepartmentName}) \circ F(\textrm{WorksIn}) .$$ Puzzle 109. What does this mean, in practical terms?

There's a lot more to say, but not now!

To read other lectures go here.

Keith E. Peterson · June 2018

Here's an example. Take $\mathcal{C} = \mathbf{Free}(G)$ and look at the morphisms $\textrm{WorksIn} : \textrm{Employee} \to \textrm{Department}$ and $\textrm{DepartmentName} : \textrm{Department} \to \textrm{String}$. Then choose a functor $F : \mathcal{C} \to \mathbf{Set}$. We must have
$$ F(\textrm{DepartmentName} \circ \textrm{WorksIn}) = F(\textrm{DepartmentName}) \circ F(\textrm{WorksIn}) .$$
Puzzle 109. What does this mean, in practical terms?

In practical terms, it means that if we take any employee, finding their department they actually work in, and then finding the name of the department they work in (maybe you want to report them...), is the same taking the same employee, and directly finding out the department name they work in (as one operation instead of two).

Robert Figura · June 2018

Some thoughts about Puzzle 109: Suppose we had an employee record like this:

let r = new Employee in

Then we can apply our two functions and get a string:

departmentName(worksIn(r)) = "engineering"

What I find somewhat natural is to turn the functor F around (let me call that G), so we can find out the type of our data:

G(r) = Employee

Note that the value is a type, hence I had to write "=" rather than ":". However, because we're dealing with a functor, we can expect to get another G which can do this:

G(departmentName o worksIn) = Employee -> String

Edit: After writing my reply to Simon Willerton's response I felt the word "String" should start with an uppercase letter.

But that's not what F does. F cannot point to any specific record (none of the F's can do that). Instead it maps a schema to the set of all possible records conforming to the schema C.

I'm not sure if this makes a lot of sense, but I think it's about somethjng which might bug programmers who'd like to learn about category theory.

Simon Willerton · June 2018

Robert, here's a couple of points. Firstly, you can't apply $\text{WorksIn}$ to $r$. The new employee will be recorded in an database which has the shape of this graph, what you might call an instance of the pictured schema. As John said this means a functor $F\colon \mathcal{C}\to \textbf{Set}$. The functor $F$ is encoding your database. So the employee $r$ will be an element of the set $F(\text{Employee})$. This means that you cannot apply $\text{WorksIn}$ to $r$ as $\text{WorksIn}$ is a morphism in the abstract category $\mathcal{C}$. The set $F(\text{Employee})$ is your set of employees and you can apply $F(\text{WorksIn})$ to that.

The result beng that your equation should read

$$ F(\text{DepartmentName})(F(\text{WorksIn})(r)) = \text{"engineering"} $$ or more simply, because $F$ is a functor,

$$ F(\text{DepartmentName}\circ\text{WorksIn})(r) = \text{"engineering"}. $$

Simon Willerton · June 2018

Secondly, what do you mean by turn $F$ around? We have $F$ is a functor $F\colon \mathcal{C}\to \textbf{Set}$, so what type of thing do you mean by $G$ and how is it defined?

Anindya Bhattacharyya · June 2018

re puzzle 109 – I think the practical lesson is that any database is completely specified by what the functor does to the graph. Once we know that, we can extend it to the rest of category by using the two functor laws.

Keith E. Peterson · June 2018

Anindya Bhattacharyya wrote:

re puzzle 109 – I think the practical lesson is that any database is completely specified by what the functor does to the graph. Once we know that, we can extend it to the rest of category by using the two functor laws.

It's not so much that $F$ does something to the graph, but rather that it picks or instantiates out a bunch of sets and functions between them that 'look like' the graph in question. Such sets and their functions are called instances in the book (and by Simon Willerton) above.

Robert Figura · June 2018

Simon Willerton said:

Firstly, you can't apply WorksIn to r.

Right, that's why I used lowercase letters! I have to admit it's a bit subtile, so here's it explicitly:

\[ worksIn = F(WorksIn) \] or \[ WorksIn = G(worksIn) \]

Just as is the case with $F$ there is more than one $G$, one for every type of object we want to map. $G$ is similar to javascript's typeof builtin when applied to objects, but javascript's typeof cannot return function types. I would have liked to write $G = F^{op}$ but that doesn't seem right as $F$ doesn't reach all the way to particular data records, but $G$ does. I'm not quite sure and am probably slightly confused here, but it seems what the book calls 'instance' isn't what a programmer might call by that name.

I know that theoreticians don't want to touch data records directly, because they want to reason about things that hold irrespective of any concrete values. But programmers who "feel" the machine may want to understand things more bottom up.

It took me a long time to get the advantage of doing things completely abstract.

Jonathan Castello · June 2018

Keith wrote:

It's not so much that $F$ does something to the graph, but rather that it picks or instantiates out a bunch of sets and functions between them that 'look like' the graph in question. Such sets and their functions are called instances in the book (and by Simon Willerton) above.

I read Anindya's comment more in terms of what happens to the morphisms than what happens to the objects. The behavior of morphisms under the functor is fully determined by the behavior of the arrows in our database schema, which is only a presentation of a category and does not contain all morphisms. Like how a linear map between vector spaces is fully determined by its action on a basis.

Sure, the objects are important, because that's where our data ends up by way of the functor. But with respect to Puzzle 109, we can factor every morphism into a string of ground arrows from the schema, so the kinds of queries you can perform can be reduced to questions about the schema.

Keith E. Peterson · June 2018

Sure, the objects are important, because that's where our data ends up by way of the functor. But with respect to Puzzle 109, we can factor every morphism into a string of ground arrows from the schema, so the kinds of queries you can perform can be reduced to questions about the schema.

I'd argue that the objects, ($X \in \mathcal{C}$), aren't that important since they can be represented by identity morphisms $id_X$.

So basically, $F$ is 'like' a function, but instead of mapping between sets, as a function does, a functor maps between morphism, including the trivial idenities.

In this sense, all that matters is where morphisms end up, and where the objects end up comes out for free!

Jesus Lopez · June 2018

Hi Robert, the $G$ you propose to build in #2 is more easily said than done but is very interesting. The good way to do it is fastly viewed in this Spivak's slides where he spells the Grothendiek construction applied in this case. Your $G$ is his $\pi:Gr(I) \to \mathcal{C}$ of slide 53. What a pity that this seems not to be included in the book! Perhaps we can talk about it here a bit.

This idea allows one to describe catgorical intercourse between different strata of the type hierarchy!

Robert Figura · June 2018

Splendid find, Jesus, thank you! I'm afraid I never went deep enough into the woods to physically meet a construction named after Grothendieck! But now that you've invoked the master, it can't be long until we get the summoned help...

Page 51 may be a good entry point compare Spivak's slides. However, looking at the diagrams on that page I'm having trouble to understand the difference between Gr(I) and I. Mostly because of the label on the arrow (b1,b1,b2). Because of that it really looks as if the diagram I had all the info Gr(I) has.

Be that as it may, I like the intuition that π collapses messy reality to a clean model. Just like what you do when trying to find out what to solve (and how).

Puzzle rf4: I suppose Strata means layers. What lies above C? Are there any more below Gr(I)?

Keith E. Peterson · June 2018

In the slides Jesus linked, David Spivak states,

It offers the opportunity to deeply integrate programming and data.

If the database is written in XML, and the programming language you're using uses s-expressions (such as LISP or Scheme), XML statements can be easily translated into a subset of s-expressions called x-expressions, the above statement of integrating programming and data becomes quite simple.

In fact, the world wide web using Javascript as the scripting language of HTML/XHTML web pages instead of LISP or Scheme, is, in my opinion, a hugely missed opportunity.

Ryan Wisnesky · June 2018

The AQL tool (http://categoricaldata.net/aql.html) implements David Spivak's schemas-as-categories idea in working software. One of AQL's built-in examples is roughly the example from this thread:

schema S = literal { entities Employee Department foreign_keys manager : Employee -> Employee worksIn : Employee -> Department secretary : Department -> Employee path_equations manager.worksIn = worksIn secretary.worksIn = id_Department attributes first last : Employee -> string name : Department -> string } instance I = literal : S { generators a b c : Employee m s : Department equations first(a) = Al first(b) = Bob last(b) = Bo first(c) = Carl name(m) = Math name(s) = CS age(a) = age(c) manager(a) = b manager(b) = b manager(c) = c worksIn(a) = m worksIn(b) = m worksIn(c) = s secretary(s) = c secretary(m) = b secretary(worksIn(a)) = manager(a) worksIn(a) = worksIn(manager(a)) } AQL's connections to functional programming and database theory are significant and are discussed in a series of papers available at http://categoricaldata.net/fql.html . For example, the query language obtained from delta/sigma/pi can be written using 'SQL-ish' notation, and reasoning about schemas and functors requires use of automated theorem proving methods (e.g., Knuth-Bendix completion).

The AQL project is currently recruiting people who have backgrounds in - category theory - type theory / functional programming - automated theorem proving - database internals / SQL at scale

If you are interested in participating, please let me know (ryan@catinf.com)

MatthewDoty · June 2018

Do you have a git repository?

(sorry to be a dumb code monkey but I usually start looking at the code/test fixtures to understand a new technology like this)

Owen Biesel · June 2018

Robert Figura wrote:

Page 51 may be a good entry point compare Spivak's slides. However, looking at the diagrams on that page I'm having trouble to understand the difference between Gr(I) and I. Mostly because of the label on the arrow (b1,b1,b2). Because of that it really looks as if the diagram I had all the info Gr(I) has.

You're right, Gr(I) has exactly the same information as I, but they're different kinds of mathematical objects. I is a functor from C to Set, while Gr(I) is its own category. In Spivak's pictures on slide 51, the pictures for C and Gr(I) represent categories, where the arrows are just abstract morphisms, while the picture for I itself consists of sets with arrows labeled by functions: a diagram in Set with shape C. Roughly speaking, Gr(I) is the category you get by starting with C, making I(c) copies of each object c in C, and then connecting up those objects by morphisms according to the functions I(f) for each morphism in f. More precisely, objects of Gr(I) are pairs (c, x) where c is an object of C and x is an element of I(c); the set of morphisms from (c, x) to (d, y) is the set of morphisms f in C(c,d) such that I(f): I(c) -> I(d) sends x to y.

Puzzle: Use the precise definition to construct the category Gr(I) for the functor I in Spivak's slide, and show that, up to relabeling, it matches the picture given there for Gr(I).

You can think of the difference between Gr(I) and I as the difference between a subset B of a set A and its characteristic function f from A to {0,1}, which sends an element to 1 if it is in B or to 0 if not. Here, Gr(I) is analogous to the subset B, while I is analogous to the characteristic function f.

Puzzle: Show that this is more than an analogy: If you start with a subset B of A, form its characteristic function f : A -> {0,1}, and then think of f as a functor I from the discrete category A to Set sending each element to a 0- or 1-element set, then Gr(I) is a discrete category with object set B.

(I would label my puzzles but I've lost track of whether the personal numbering "OB1, OB2, etc." is supposed to reset in each thread or if I should be keeping track of how many puzzles I've posted total.)

Owen Biesel · June 2018

I'm intrigued by slide 55: a "semi-instance" of the schema with category C is interpreted as a functor D to C—based on the example, this makes sense to me. But he goes on to say that from such a semi-instance we can construct an "instance", a functor I from C to Set where Gr(I) is somehow a "fixed" version of D. Can we work out how to do that?

Jesus Lopez · June 2018

Thanks Owen, you explained it pointedly.

Intuitively, the category of elements, that specializes the Grothendiek construction (as if he hasn't construed anything more!) would respond to the question "how do I turn arrows in a plain old Venn diagram picture of a function between sets into morphisms in a good category? (here I write two functions to spice it up).

Venn diagram

Since we have a concrete category $I:\mathcal{C} \to Set$, the objects can be viewed ("correspond") to actual sets, and the morphisms to functions. So if $\mathcal{C}$ has objects say $S, T, U$, and morphisms $f, g$, then $Gr(I)$ will have, for its objects, the disjoint union of all the sets that correspond to the objects of $\mathcal{C}$. Hence the objects of $Gr(I)$ form a soup of all the elements of the objects of $\mathcal{C}$, with their object filiation flattened and forgotten, but then regained by means of $\pi:Gr(I) \to \mathcal{C}$.

Here is what $\pi$ does to the objects and morphisms of $Gr(I)$, painted with dashed arrows.

gro-const

The category of elements is an incomplete part of the story, the end product is the functor $\pi$, that says how $Gr(I)$ sits on top of $\mathcal{C}$. $\pi$ organizes the data.

Owen Biesel · June 2018

Nice pictures! The two-layer one makes it clear how Gr(I), C, and pi are related.

John Baez · June 2018

Unimportant comment: I'm changing the title of this lecture to "Functors", since that's the most important concept introduced here. The next lecture will be called "Databases", since we'll do more with databases there.

Fredrick Eisele · June 2018

Do you have a git repository?

Yes.

https://github.com/CategoricalData/fql

Cheuk Man Hwang · June 2018

I am not a programmer so I may be saying something silly...

Puzzle 109 In practical terms, does it mean if you want to write a function to retrieve the name of the department that an instance of the Employee data works in as a string type, do not write a new function. If you have already written a function that retrieves the department data of the employee instance and another function that retrieves the department name of any instance of the department data as a string type, simply declare your "employee to department name" function as the composition of these two. That should allow you to better analyze the integrity of your database using category theory.

Robert Figura · June 2018

Thank you very much, Owen, for making crystal clear that the functor I is simply a more complete way to specify the whole dataset Gr(I), as it also includes how the data relates to our schema C.

I've learned something, and I'll mention the Grothendieck construction next time I relate data with a schema!

Also, I've just decided to enumerate my puzzles per lecture, simply mentioning the lecture number to make things abundantly clear. So that should have been puzzle rf38.1.

Keith E. Peterson · June 2018

I JUST REALIZED SOMETHING!!!

Claim: Associativity comes from functor composition.

Proof: Given any functor $F: \mathcal{C} \to \mathcal{D}$, we can produce the following,

\[ F(f(g(x)) \\ = F((f \circ g)(x))\\ = F(f \circ g) \circ F(x) \\ = F(f)\circ F(g \circ x) \\ = F(f\circ g \circ x) \]

Now as you can plainly see, if you set $F$ to $Id_\mathcal{C}$, you'll get associativity in the category for free. Q.E.D.

Bartosz Milewski · July 2018

Keith: I presume $f$ and $g$ are morphisms, but what is $x$? The notation $f(g(x))$ suggests functions, where $x$ is an element of a set; and if you define composition of functions this way, it's automatically associative.

Keith E. Peterson · July 2018

Yes, $x$ is a set in this case.

Azimuth Forum

Howdy, Stranger!

Categories

Lecture 38 - Chapter 3: Functors

Comments