Thank you for your detailed answer.
I surely agree that Functor consists of two parts, you can call them “type lift”
a => F(a)and function lift
f => map(f).
Yes, that’s what I was trying to get at. Thanks for describing it so eloquently.
I love your articles and learned a lot from them on the programming side, but being a professional mathematician, I wanted to help making this one even more precise to help the reader avoid any confusion.
Thank you! I really appreciate the effort. I think you’ve already helped me make it much better. Describing these things in a way that is both precise and easy to understand is a difficult challenge — something I’m sure you’ve figured out after making an attempt, yourself. At least I’m not saying “a functor is a burrito!” ;)
> A functor can map from category to category:
F a -> F b
This might confuse the reader thinking
F bare the categories and the arrow is the map between them. Whereas it is actually a function (morphism) between two “lifted types”.
I can see how that caused confusion. Here I was trying to give an example where
F a and
F b were being viewed as different categories themselves, but that’s a leap I shouldn’t have asked of the reader without a lot more background.
As I mentioned in my last response, as long as you obey the category laws, you can view objects, and even mappings between objects as categories. It’s categories all the way down (or it can be, anyway — as I understand it, this is how we get away with talking directly about objects inside categories… unlike set theory and objects in sets, reasoning on categories must address categories, not objects).
But now I see that may be a bit too much to throw at somebody, or perhaps I’m confused myself, if even a mathematician is getting confused by it.
In order to clarify, I’ve completely re-imagined the description of endofunctors to be more mathematically precise. I’d love your feedback on the proposed change:
An endofunctor is a functor that maps from a category back to the same category. Given two categories,
- A functor maps from category to category:
X -> Y
- An endofunctor maps from a category back to the same category:
X -> X
Ymay be the same category, so endofunctors are a kind of functor.
Y here reperesent categories.
In code, the definition of “endofunctor” gets a bit more slippery. The short version is “don’t worry about it.” Using functors is quite simple, and you won’t be missing much if you don’t wrap your head completely around the underlying category theory.
The detailed version depends on what we’re looking at as the category. In code, we are usually referring to the category of types and functions, where types are objects, and functions are morphisms between types. We’ll call this category
Within this category, every functor is also an endofunctor, because every function will map a type from the category
X back to another type from the category
Since all monads are also functors, this quote should start to make a little more sense:
“A monad is just a monoid in the category of endofunctors? What’s the problem?”
We’ll get to monoids and monads later.
Now for the confusion. You could also look at subcategories in the category of types and functions, in which case, mappings between types
C d (we'll say they come from categories
Z, respectively) would not qualify as endofunctors in
Z, but would qualify as endofunctors in the containing category (
In other words, the same mapping can be an endofunctor in
X, but not an endofunctor in
Ok, back to our discussion:
A functor is a mapping which preserves state. You need the lift and a map, or it’s not a functor.
This is a typo. I meant “preserves structure”, where structure is the graph of possible morphisms. In category theory, structure is represented by the possible compositions in the category. In other words, the morphisms and how they relate to each other represent the structure of a category (and functor).
In code, this just means, “return something you can map over”, which forms the primary distinction between a function
a -> b and a functor
F a ~> (a -> b) -> F b. (In case you’re unfamiliar with the squiggly arrow notation, a functor of
a takes a function from
b and returns a functor of
The only category laws are associativity and existence of identities. The functor law does not contain any associativity.
Hmm… it seems like we’re misunderstanding each other here. Let’s consult the category theory bible (Saunders Mac Lane). In “Category Theory for the Working Mathematician) Mac Lane describes a category as a graph of objects with arrows between objects mapping the graph structure, and a “metacategory” as a metagraph with the following operations (quoting now):
- Identity, which assigns to each object
ida = 1a : a -> a[using italic for subscript]
- Composition, which assigns to each pair
<g, f>of arrows with
dom g = cod fan arrow
g ∘ f : dom f -> cod g
The mandatory existence of these operations are commonly referred to as the “catogory laws”: Each object in each category must have both operations. Each category can also be viewed as elements within a containing category — thus all categories must also have those operations.
Unless I’m misunderstanding Mac Lane, it’s categories all the way down. Right?
Additionally, the laws are subject to axioms (quoting again, clarifications from me in square brackets):
- Associativity [on composition] must hold for composition whenever it makes sense (i.e, whenever the composites on either side are defined)
f ∘ (g ∘ h) = (f ∘ g) ∘ h
- Unit law. [on identity] For all arrows
f : a -> band
g : b -> c, composition with the identity arrow
idb ∘ f = f[left identity] and
g ∘ ida = g[right identity]
Similarly, functors must also support both identity and composition. The axioms for functors are different from categories, as you say, and are detailed in the original article. The point is that both are about identity and composition, as a high-level concept.
Perhaps the source of the confusion here is that the way we express identity and composition for functors is slightly different from the way we express it for categories. I should probably be careful with the generalizations so that people don’t take that to mean that they use identical abstractions.
However, if we’re too careful, people miss the forest for the trees. The point of categories is composition and the structure arising from the composition graph of the category. That’s the motivating factor behind category theory. It gives us an abstract way to reason about all sorts of interesting things.
The point of functors is to maintain structure between category morphisms.
Likewise, the essence of all software creation is composition. My failure to connect all the compositional dots is one of my biggest regrets in life. Having a better understanding of composition in general has made me a much better software developer.
Thanks again if you managed to get through all that. Apologies if I made any mathematical errors. Please feel free to correct me. =)