Mappings That Preserve Structure

A partial order as a category. Objects are the elements; there is one arrow $a\to b$ exactly when $a\le b$. Composition is transitivity, identities are reflexivity, and associativity is automatic because any two arrows with the same source and target are equal. The concept hierarchy of the knowledge-representation unit is a category in this sense, and a monotone map between two such orders is precisely a functor.

Lists with map. Objects are types, arrows are functions, and the list constructor with map is a functor when map id = id and map (g . f) = map g . map f. Both hold for the standard implementation. A variant that reverses the list while mapping type-checks identically and breaks the first law, since mapping the identity would reverse.

A monoid as a one-object category. One object, one arrow per element, composition is the monoid operation. Associativity of the category is associativity of the monoid; the identity arrow is the unit. A functor between two such categories is exactly a monoid homomorphism. The categorical laws reduce to the algebraic ones with nothing left over.

A mapping that collapses everything. Send every object of $\mathcal{C}$ to a single object $X$ and every arrow to ${\mathrm{id}}_X$. The identity law holds because every identity is sent to ${\mathrm{id}}_X$, which is the identity at the only object in the image. The composition law holds because both sides reduce to the same arrow whatever was composed: $F(g\circ f)={\mathrm{id}}_X$, and $F(g)\circ F(f)={\mathrm{id}}_X\circ {\mathrm{id}}_X={\mathrm{id}}_X$. So this is a functor. It is uninformative and entirely legitimate, which shows that satisfying the laws is a minimum rather than a merit.

reverse on lists as a natural transformation. For each type $T$, reverse maps a list of $T$ to a list of $T$. Naturality says map f . reverse = reverse . map f, which holds because reversing rearranges positions without examining elements. Contrast sort, which inspects elements: map f . sort and sort . map f differ as soon as f does not preserve the ordering, so sort is not natural.

---

The first three are cases where familiar structures turn out to be categories and familiar maps turn out to be functors, so the laws recover what was already known. The fourth shows the laws are a floor, not a distinction. The fifth is the one that bites: two functions of the same type, one natural and one not, distinguished by an equation rather than by their signatures.

$F$ against $G$, on the same category.

The first four rows are identical. Only the fifth comparison separates them, and it is the only row that could not be settled by inspection.

The typing condition against the composition law.

A mapping sending $f:A\to B$ to an arrow $X\to Z$ when $F(B)=Y$ fails the typing condition, and the composite $F(g)\circ F(f)$ is then not even defined. There is nothing to check. That is a malformed candidate. A mapping passing the typing condition and failing composition is a well-formed candidate that is false, which is the more instructive failure and the harder one to spot.

Collapsing against contradicting.

$F$ sends two objects to one and a non-identity arrow to an identity, losing information, and remains a functor. $G$ assigns to $gf$ something incompatible with its assignments to $f$ and $g$. Losing information is permitted; being inconsistent about composites is not.

reverse against sort.

Both have the same shape: for each type, a function from lists of that type to lists of that type. reverse satisfies map f . reverse = reverse . map f because it moves elements without looking at them. sort does not, because it compares them, so mapping first can change the order it produces. Identical signatures, different answers to an equation.

A drawn square against a commuting square.

Every naturality square can be drawn: the four arrows exist and their endpoints match by construction. Whether the two routes are the same arrow is a separate question, settled by evaluating both. Drawing establishes that the question is well posed, not that the answer is yes.

A check that could fail against one that could not.

Verifying naturality between two constant functors gives agreement at every arrow, and both routes reduce to the same arrow whatever the transformation, so no assignment could have failed. Verifying between functors that act differently on arrows is a check with a possible negative outcome. Only the second is evidence.

That a mapping is a functor once it sends objects to objects and arrows to arrows with matching sources and targets. Those conditions make it a candidate; the composition law decides. In the worked example a mapping $G$ sends every object somewhere sensible and gives every arrow correct endpoints, yet $G(g\circ f)={\mathrm{id}}_Y$ while $G(g)\circ G(f)={\mathrm{id}}_Y\circ h=h$. The two differ, so $G$ is not a functor, and nothing about the object map or the endpoints revealed it. The same holds in programming: a type constructor with a map that type-checks may still break map (g . f) = map g . map f, because the compiler enforces the types and not the laws.

That drawing the naturality square establishes naturality. Every such square can be drawn: the arrows ${\alpha }_A$, ${\alpha }_B$, $F(f)$ and $G(f)$ exist by definition and their endpoints always line up. What naturality asserts is that the two routes around the square are the same arrow, ${\alpha }_B\circ F(f)=G(f)\circ {\alpha }_A$, and that is an equation to be evaluated at every arrow of the source category rather than a property of the picture. A transformation can satisfy the equation at several arrows and fail at another, so a check is incomplete until each arrow has been examined. Verifying it on a case where both functors are constant confirms the mechanics of the check and tests nothing, since every square then reduces to the same equation.