For some reason I’ve had a great amount of trouble learning category theory. I think a lot of that is that most of the literature sucks. But I don’t blame it, in fact I find it encouraging, because it indicates that there is a brain-rewiring involved: people who know category theory cannot teach it, because as a consequence of learning it, they are thinking in a fundamentally different way.
However, thanks to the Stanford Encyclopedia of Philosophy, a resource which consistently provides good intuition for mathematics when the literature is otherwise impenetrable, I think I finally get natural transformations.
I always heard that a natural transformation is “just like a polymorphic function”. I never really got that, especially since wikipedia said a natural transformation acted on functors but a function is a morphism (in Hask).
Let’s work in the context of an example. I’ll look at
concat :: [[a]] -> [a] because it has only one argument and only one type variable, so that will simplify things for us. Let’s also recognize that there are two functors appearing here:
 on the right and
° on the left.
Here’s the formal definition, which I wish to decode: A natural transformation η relates two functors (F and G) with identical source and target. It maps objects in the source category to morphisms in the target category. For every morphism in the source category, .
So here F is
° and G is
. Our natural transformation
concat must associate objects (types) to morphisms (functions) and satisfy the above equation. To expand that equation, let’s realize that
(f) (where  is the functor) is
map f and
map (map f). These are part of the definitions of these functors, and in Haskell correspond to the definition of
The equation is thus: for all functions
f :: x -> y,
concaty . map (map f) = map f . concatx. Holy smokes! That’s the free theorem for concat! (note: that paper was another that I never really grokked; maybe I’m grokking it now)
If I could go back to last week and help myself understand, I would have said: a polymorphic function in Haskell is a collection of morphisms in Hask, not a single one, and the equation above is what guarantees that it’s actually parametrically polymorphic (doesn’t care what type it is).
So the following pseudohaskell would not define a natural transformation:
concat' :: forall a. [[a]] -> [a] concat' | a ~ Int = const  | otherwise = concat
Because the equation fails to hold for, say,
show :: Int -> String:
concat'String . map (map f) /= map f . concat'Int because
concatInt = const . That makes sense, because
concat' is not parametrically polymorphic.
A question I have is what a polymorphic function is when it’s acting on type constructors that aren’t functors. Is that just a “polymorphic function” and doesn’t necessarily have a categorical parallel?
I guess the weirdest thing about category theory is how natural trasformation was defined. I think I have an intuition for what it is now, but I would never fathom defining it that way. Thinking of objects only as their relationships to other objects is a mind bender.