Functors in category theory, and also in its application to functional programming, can be seen as a kind of "structured" functions: Given two sets $A,B$, rather than just having a function $f:A\to B$, we have a functor $F$ which contains $f$, but additionally also maps morphisms on $A$ to morphisms on $B$ (i.e. maps not only $A$ to $B$ but also maps "structure on $A$" to "structure on $B$").

In the category theory of functional programming, objects $A,B$ are types and morphisms are functions $A\to B$ between types. That means functors map types $A,B$ to other types $X,Y$ and map functions $A\to B$ to functions $X\to Y$. Functors in functional programming can thus be seen as a mapping between datatypes that additionally also maps the functional structure on those data types.

My thought was: In the context of object-oriented programming, there really are more kinds of structure on datatypes than just functions between them. For example, given two types $Int$ and $Bool$, we can not only define functions $f:Int\to Bool$, but also things like $p:Int\times Bool$, or more complex datatypes like classes with private component classes.

Is there a generalization of functors to "mappings between datatypes that also preserve structure", where that doesn't need to be functorial? In particular I'm wondering whether such a concept is used in analyzing programming languages.


1 Answer 1


I guess no one else is going to answer this, so I'll take a crack.

First, there's nothing inherently 'functional' about categories, necessarily. For instance, you can make any monoid into a category, where you have one object, and then the arrows from that one object to itself are the elements of the monoid. The identity element is the identity arrow, and composition is monoid multiplication. Then functors between two monoids in this sense are homomorphisms between the monoids; they are functions that preserve identity and multiplication.

Categories are then generalizations of this to situations where the monoid values have types, and can only be multiplied together when the types correspond. The specifics of this work for functions, but it could be a lot of other things, too. You could try to devise a category where $Hom(X,Y) = X×Y$, and then functors from/to that category would be obligated to map from/to products.

However, it is also common to define additional structure beyond just being a category. For instance, even for 'functional programming,' you are usually talking about (at least) Cartesian closed categories. These are categories $C$ that have additional structure:

$$-×- : C × C → C$$ $$1 : C$$ $$[-,-] : C^{op} × C → C$$

Where $×$ forms binary products, $1$ is a terminal object, and $[-,-]$ forms exponentials, so:

$$C(X×Y,Z) \cong C(X, [Y,Z])$$

And when you have categories with additional structure like this, you also want to talk about functors that preserve that extra structure. So there are Cartesian closed functors between Cartesian closed categories that map products to products, terminal objects to terminal objects, and exponentials to exponentials.

So, yes, you can describe plenty of structure besides just $Hom$, and talk about maps that preserve all that structure (in various senses), not just functors.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.